3 ms·
The 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 reciproc
by chjj 6y ago
The 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