Brian - 1 year ago 64
Java Question

# Recursive Division without multiplication, mod, or division in Java

I have to write a recursive algorithm for a project that divides an arbitrarily long integer, by another integer which is a single digit long (1-9). I was able to write an algorithm that does this in a loop. Now, I'm having issues coming up with the logic on how to do it recursively, mainly as my non-recursive version does the brute force approach of continuously subtracting, which overflows the stack pretty quickly. I've read several articles online about a "shift and subtract" algorithm, but I can't find any code examples on how to implement this. I'm using BigIntegers for the numbers, so I'm not quite sure how the alignment would work, since I'm not allowed to use any kind of multiplication, mod, or division. That's really where I'm stuck, and can't figure out what to do. This is what I was able to come up with so far:

``````// class fields
private String numerator;
private BigInteger number;
private int denominator;
private BigInteger denom; // copy of denominator

private BigInteger divideHelper()
{
if(denominator == 0)
{
throw new ArithmeticException("Division by 0.");
}
if(denominator == 1)
{
return number;
}
if(denominator == 2)
{
return number.shiftRight(1);
}
if(denominator == 4)
{
return number.shiftRight(2);
}
if(denominator == 8)
{
return number.shiftRight(3);
}

return divide(number, denom);
}

private BigInteger divide(BigInteger n, BigInteger d)
{
BigInteger quotient = BigInteger.ONE;

if(n.compareTo(d) == 0)
{
return BigInteger.ONE;
}
else if(n.compareTo(d) < 0)
{
return BigInteger.ZERO;
}

while(d.compareTo(n) <= 0)
{
d = d.shiftLeft(1);
quotient = quotient.shiftLeft(1);
}

}

private String divide()
{
if(denominator == 1)
{
return this.numerator;
}

StringItr numerator = new StringItr(this.numerator);
StringBuilder result = new StringBuilder();
int storage = 0,
temp = 0;

for(int i = 0; i < this.numerator.length(); i++)
{
temp = numerator.nextInt();

if(storage > 0)
{
temp += storage;
storage = 0;
}

if(temp < denominator && temp > 0)
{
for(int j = 0; j < 10; j++)
{
storage += temp;
}
result.append(0);
}
else
{
for(int j = 0;;j++)
{
if(temp > 0)
{
if(j == 0)
{
j++;
}
temp -= denominator;
}
if(temp == 0)
{
result.append(j);
break;
}

else if(temp < denominator)
{
result.append(j);
for(int a = 0; a < 10; a++)
{
storage += temp;
}
break;
}
}
}
}

if(result.charAt(0) == '0')
{
result.deleteCharAt(0);
}

return result.toString();
}
``````

Any help or pointers on where to start would be amazing, thanks in advance!