Brian Brian - 1 month ago 6
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);
}

return quotient.add(divide(n.subtract(d),denom));
}

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!

Answer

You are on the right track! If I were you, I would search for examples in other languages in which bit-shifting is more common (c for example). It then shouldn't be too much trouble to convert the code for bit-shifting in C into Java code. Take a look at this answer, and this one for example.