Recursive division using an array of large inters of base 2^64

Question

I need to be able to divide two large integers A and B and get a resulting quotient Q and remainder R. I have found a lot of posts about "just doing division like in grade school" but don't see how this applies to this case, where the base is 2^64.

For example, say I had the number A made of a_2 = 120, a_1 = 2, and a_0 = 240, with a_2 corresponding to 2^(64*2), a_1 to 2^(64*1), etc. and I want to divide it by B, with b_1 = 1300 and b_0 equal to 3.

How would I go about doing this?

Thanks

See http://stackoverflow.com/questions/4018321/calculating-modulo-for-large-number — phatfingers, Nov 14 '11 at 14:59

phatfingers · Answer 1 · 2011-11-14T21:09:18.310

The Java BigInteger class has a divideAndRemainder(BigInteger val) method that returns (Q,R) as an array.

Example:

BigInteger a=new BigInteger("2").pow("128").multiply("120").add(new BigInteger("2").pow("64").multiply("2")).add(new BigInteger("240"));
BigInteger b=new BigInteger("2").pow("64").multiply("1300").add(new BigInteger("3"));
BigInteger[] qr=a.divideAndRemainder(b);

Although that's not quite what you're asking for, is it?

I haven't done what you're asking, but I've peeked at other solutions. The math is essentially the same whether you use large numbers or not, so for the purpose of learning the technique, I would suggest that you learn with a small machine word size and then apply the knowledge to the 64-bit version. That'll make it easier to model and verify.

If I (now) understand what you're asking, you could have a sequence of 4-bit numbers (hex) and an 8-bit processor that can do mod,div,add,multiply operations. How do you break it into chunks to solve division of numbers of arbitrary widths?

For example, you can verify that in decimal, 1441/3=480r1. In your 8-bit machine, you want (Q,R), for the equation ( 0x05a1 / 0x3 ). You can calculate left to right, taking the remainder and applying it to the high-order nybble of the next digit. So, you calculate 0x5/0x3=1r2, then 0x2a/0x3=er0, then 0x01/0x3=0r1. The sequence "1e0" from the results matches your expected value (0x1e0=480) and the last remainder matches the 1 you would expect.

Extrapolating to 64 bits, you would use the same technique, but process in 32-bit chunks so you can place the prior remainder in the high-order half of your word.

Recursive division using an array of large inters of base 2^64

1 Answers1