9 ms·
Donald Knuth’s Algorithm D, its implementation in Hacker’s Delight and elsewhere
- chjj 6y agoI'd encourage people to also read Niels Möller and Torbjörn Granlund's division paper: https://gmplib.org/~tege/division-paper.pdf https://gmplib.org/~tege/division-paper.pdf It offers a modification to Knuth's algorithm D which avoids all hardware division by utilizing an approximate reciprocal. The 3-by-2 division is particularly interesting as it allows you to skip the quotient loop (D3). It's a nice little optimization that I've spent some time tinkering with in my own code. This technique is notably used in GMP and other arbitrary precision integer libraries.
- remcob 6y agoIIRC, I tried this method, but did not see any performance improvement. The method replaces a single `divq` instruction with a table lookup and several multiplications. On modern processors this is no longer a worthwhile trade off.
- chjj 6y agoThe 2-by-1 and 3-by-2 division functions described in the paper result in a very measurable speedup in my code. I think you're confusing those with the reciprocal calculation itself (which can be computed with a lookup table). I agree that part doesn't really lend itself to any significant performance benefit and is probably better calculated with a single hardware division instead. I feel it necessary to point out that the 3-by-2 division actually has multiple benefits which are easy to miss: 1. The quotient loop can be skipped as I mentioned. 2. The "Add back" step is less likely to be triggered. 3. Since a 2-word remainder is computed with the division, you can skip 2 iterations on the multiply+subtract step. My reimplementation of GMP documents both the 2-by-1 and 3-by-2 divisions pretty thoroughly[1][2]. [1] https://github.com/bcoin-org/libtorsion/blob/master/src/mpi.c#L2711 https://github.com/bcoin-org/libtorsion/blob/master/src/mpi.... [2] https://github.com/bcoin-org/libtorsion/blob/master/src/mpi.c#L2872 https://github.com/bcoin-org/libtorsion/blob/master/src/mpi....
- zmodem 6y agoI had not seen that GMP reimplementation before, but it looks very readable. Thanks! I used the Möller & Granlund paper for a portable implementation of 2-by-1 division [1], and on my machine (which is admittedly not exactly new) it runs much faster than the DIV instruction. [1] https://www.hanshq.net/eprime.html#div https://www.hanshq.net/eprime.html#div
- mratsim 6y agoThe 3-by-2 division is from Burnikel and Ziegler [1][2] with a nice comparison from Hasselstrom between division approaches. OpenSSL has introduced another 3 by 2, but this one is written with constant-time concerns for cryptography [4] [1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.565&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.... [2]: https://github.com/status-im/nim-stint/blob/bae3fc6/stint/private/uint_div.nim#L19-L45 https://github.com/status-im/nim-stint/blob/bae3fc6/stint/pr... [3]: http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Hasselstrom2003.pdf http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Hass... [4]: https://github.com/openssl/openssl/pull/7589 https://github.com/openssl/openssl/pull/7589
- pansa2 6y agoSo, Golang and V8 both use this algorithm when you choose to use an arbitrary-precision integer type. In Python (and Ruby?), all integers are arbitrary-precision - do those languages also use this algorithm for division?
- dragonwriter 6y ago> In Python (and Ruby?), all integers are arbitrary-precision IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user. I'd imagine that they different low-level operations are involved depending on the internal type.
- TylerE 6y ago"Normal" ints in Python are certainly native. You don't get bignums until you need them. I think, on 32bit platforms (though we're about 10 years removed from actual expirence) they'd go int -> long -> bignum as needed.
- toolslive 6y agobut... are they unboxed?
- AlexanderDhoore 6y agoIn python everything is boxed. EDIT See https://news.ycombinator.com/item?id=12418985 https://news.ycombinator.com/item?id=12418985
- pansa2 6y agoNothing is unboxed in CPython. Other implementations differ - for example, MicroPython supports several encodings for unboxed values. https://github.com/micropython/micropython/blob/4fc2866f45692b05829d71b636724e690b786307/py/mpconfig.h#L68 https://github.com/micropython/micropython/blob/4fc2866f4569...
- 6y ago
- remcob 6y agoHere is my optimized in-place Rust implementation [1]. It is a very tricky algorithm to get right. There are many edge cases that only happen for ~2^-64 fractions of the input space, so hard to find even with fuzz-testing. Best strategy is to implement it for small limbs first, and fuzz that well. [1] https://github.com/0xProject/OpenZKP/blob/master/algebra/u256/src/arch/generic/knuth_division.rs#L89 https://github.com/0xProject/OpenZKP/blob/master/algebra/u25...
- svat 6y agoJust a note about the name of the algorithm: Knuth's The Art of Computer Programming indeed uses letters for algorithms, but the intended convention is that, for example, this algorithm be called "Algorithm 4.3.1D" (that's the name used in "Appendix C — Index to Algorithms and Theorems"). From page 2 of Volume 1 of TAOCP: > The format above illustrates the style in which all of the algorithms throughout this book will be presented. Each algorithm we consider has been given an identifying letter (E in the preceding example), and the steps of the algorithm are identified by this letter followed by a number (E1, E2, E3). The chapters are divided into numbered sections; within a section the algorithms are designated by letter only, but when algorithms are referred to in other sections, the appropriate section number is attached. For example, we are now in Section 1.1; within this section Euclid’s algorithm is called Algorithm E, while in later sections it is referred to as Algorithm 1.1E. In the case of this particular "Algorithm D", the letter "D" is chosen probably because it's an algorithm for "Division of nonnegative integers" (it follows algorithms "A", "S" and "M" for you-can-guess-what); indeed the same volume also has another "Algorithm D (Factoring with sieves)" (=Algorithm 4.5.4D), and an "Algorithm D (Division of polynomials over a field)" (=Algorithm 4.6.1D). I think that, as several times in the same section it's referred to simply as "Algorithm D" (for example), this convention is not very obvious unless one has looked at either the second page of the first volume, or the appendix. Or I guess within a certain field a particular section of TAOCP is implicit, so it's clear from context.
- sipu261988 6y agoUseful and authentic Contents or information, my authentic website is similar to your wesite and we request for backlink's exchange. <a> https://www.newsindia24live.com/category/latest-politics-news-live/ https://www.newsindia24live.com/category/latest-politics-new... </a>
- stellalo 6y agoLooks like the links to the book are broken in the article. The book in question is this: https://en.m.wikipedia.org/wiki/Hacker%27s_Delight https://en.m.wikipedia.org/wiki/Hacker%27s_Delight
- nullc 6y agoThe book's website went down recently but it's on archive.org: https://web.archive.org/web/20181106040121/https://www.hackersdelight.org/ https://web.archive.org/web/20181106040121/https://www.hacke...
- nickcw 6y agoI have implemented this algorithm twice, once in ARM assembly and once in C. In some ways the assembly implementation was easier as you aren't forever fighting with the compiler to get it to generate the correct instructions. The 32 X 32 to 64 bit multiply is one example. There isn't a way of expressing that in C - you do a 64 X 64 bit multiply of 32 bit variables casted to 64 bits and hope the compiler gets the hint that it should be doing a 32 X 32 to 64 bit multiply not a 64 X 64 bit multiply. This of course involves reading the assembly output. The other thing you'd like is addition with carry. It is possible to express this in C and have the compiler recognise what you are doing and generate the correct instructions but it is a pain! I noted the other day that zig has @addWithOverflow which is a step in the right direction. I can see why the Author of the article found so many things to criticize in the algorithm studied, but I think they are mostly an artifact of the fact that C (and most high level languages) is a poor choice for low level arithmetic.
- haberman 6y ago> I noted the other day that zig has @addWithOverflow which is a step in the right direction. This seems reasonably easy to implement in C: #include <stdint.h> typedef struct { uint64_t val; uint64_t carry; } Result; Result addWithOverflow(uint64_t x, uint64_t y) { Result res = {x + y, x + y < x}; return res; } On GCC and Clang this does the right thing (grabs the carry flag): https://godbolt.org/z/dzP3TPGTW https://godbolt.org/z/dzP3TPGTW I agree a dedicated intrinsic like in Zig is even better, but it is nice that modern compilers make it reasonably straightforward to get the desired code even without dedicated intrinsics.
- nickcw 6y ago@addWithOverflow is easy to implement in C, but you still need to look at the assembler code to see if the compiler did the right thing. I don't like that tension between C code you've arranged in just the right way and hoping that it continues to generate the assembler output it did once. I guess a portable set of compiler intrinsics it what is really needed to solve this problem. There is an x86 intrinsic for 32 x 32 -> 64 bit multiply now-a-days https://docs.microsoft.com/en-us/cpp/intrinsics/emul-emulu?view=msvc-160 https://docs.microsoft.com/en-us/cpp/intrinsics/emul-emulu?v... And one for 32 + 32 -> 32 + carry also. Though I don't know how portable __emulu is.. does it work on ARM for instance?
- taylortx 6y agoIt seems rather petty to criticize the use of uint64_t in the 64-bit versions in multiple places when the original does the same: 32-bit version: const unsigned b = 65536; // Number base (16 bits). unsigned un1, un0, // Norm. dividend LSD's. vn1, vn0, // Norm. divisor digits. q1, q0, // Quotient digits. un32, un21, un10,// Dividend digit pairs. rhat; // A remainder. So a properly adapted 64-bit version should use uint64_t and a 32-bit number base. I did not attempt to follow the author's arguments why he advocates for 32-bit variables or why that deviation from the original would be correct. Using 64-bit does not seem to be any bottleneck at all here, so why bother.
- tangus 6y agoBut why? The Hacker's Delight author justifies it: >Several of the variables below could be "short," but having them fullwords gives better code on gcc/Intel. But does the same happen in the "adapted" code? Does forcing 64 bit variables on a 32 bit architecture give better code? Wouldn't it have been better to just leave the compiler to choose the best appropriate size? (I guess you do that by just declaring the variable as unsigned? I'm no C guru...) Also, the fact that all of them renamed the variable un32 to un64 tells you that they didn't have the slightest idea about what they were doing :D
- fjfaase 6y agoVery interesting exposition and comments. I think it shows one of the 'weaknesses' of TAOCP is that it does not formalize or at least make explicit the relationship between the available operations and the final functionality of the algorithm. In that sense the TAOCP remains a receipe book and not something that is 'executable' in the sense of being able to generate algorithms tailored to the available operations (and their performance) or at least to be used in a tool that could support the synthesizes or verification of algorithms.
- enriquto 6y agoThis is my favorite algorithm ever, and the first serious one that I tried (and failed) to implement in my life when I was a teen. I remember dearly implementing the first three algorithms (A, S, M) in the nasm assembler on my debian "hamm". Then I tried for many weeks to get D right, but never managed to be sure all the cases worked. These algorithms are probably easier to implement in assembly than in a higher-level language.