4

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?

  • 5
    find a existing bigInt divide and optimize for your case? – ratchet freak Jul 15 '15 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 '15 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 '15 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 '15 at 19:55
  • 2
    Is the problem in efficient unpacking the 26-bit words? – 9000 Jul 28 '15 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.