6

What is the fastest way to divide two 256-bit integers? They are represented as an array of 26-bit words, each stored in 32-bit integers. I have access to a 64-bit type if that's useful.

It seems like fast division methods in the literature all assume we are dividing a 2n-word number by an n-word number. Is there some simple transformation or folklore that lets me generalize these methods to arbitrary numbers?

13
  • 5
    find a existing bigInt divide and optimize for your case? Jul 15, 2015 at 15:30
  • 3
    Java's digs down to "Uses Algorithm D in Knuth section 4.3.1. Many optimizations to that algorithm have been adapted from the Colin Plumb C library" (from here)
    – user40980
    Jul 15, 2015 at 15:38
  • 1
    ... I assume you looked at the code in BigInteger that I linked above. Is there a reason that didn't work for you?
    – user40980
    Jul 28, 2015 at 19:40
  • 1
    I'd like to point out that you are (likely) a math or cs phd student (according to your SE profile). Programmers.SE tends to be the much more pragmatic industry programmers rather than the designers of new algorithms or deep understanding of existing ones. If its in the standard library - there are other problems and deadlines to be had rather than worrying about reimplemeting the wheel (until the profiler says that its not rolling fast enough). You might have better luck asking on CS.SE or TCS.SE.
    – user40980
    Jul 28, 2015 at 19:55
  • 2
    Is the problem in efficient unpacking the 26-bit words?
    – 9000
    Jul 28, 2015 at 19:56

1 Answer 1

2

The first thing you should do is test if divider and dividend are equal, in which case the result is 1, if the divider is bigger than than the dividend, in which case the result is 0 and if the divider is zero, in which case the result is undefined.

Then if both values are small enough to fit a 64 bit integer, you convert both to 64 bit and make a normal 64 bit integer division, like:

int256_from_64(int265_to_64(intA) / int265_to_64(intB))

And if you have fast methods that "divide 2n-word number by an n-word number", you can use them in case the divider is 128 bit or less, as then you are dividing a 256 by a 128 bit number (just expand one to 256 and the other one to 128).

If both are above 128 bit, you can either pretend the first one to be 512 and again use a "divide 2n-word number by an n-word number"-method (this time it will be 512 and 256) or you implement division by hand which is not that horribly slow if you don't want to crunch billions of numbers a second.

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

Source: https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_(unsigned)_with_remainder

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.