Donald Knuth’s Algorithm D, its implementation in Hacker’s Delight and elsewhere

• OpenZKP

  2 622 0.0 Rust

  OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems.

  

Here 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/u25...

• libtorsion

  2 23 0.0 C

  C crypto library

  

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....

[2] https://github.com/bcoin-org/libtorsion/blob/master/src/mpi....

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• CPython

  1,314 59,658 10.0 Python

  The Python programming language

  

> IIRC, both (well, CPython and MRI) internally use distinct “small integer” and “big integer" representations, but that is transparent to the user.

This seems to be correct for MRI. Before Ruby 2.4, both `Fixnum` and `Bignum` were exposed to the programmer. In 2016 these were unified into `Integer` from the programmer's point of view, but with "no internal representation change" [0].

> "Normal" ints in Python are certainly native. You don't get bignums until you need them.

However, I don't think this is true for current versions of Python. As part of the 2.x => 3.0 transition, Python underwent a similar unification of integer types. Python 2.x exposes both `int` and `long`, and Python 3.x has only `int`. However, internally, 3.x's `int` is represented by `PyLongObject` and the old `PyIntObject` has been removed. Even the small integer cache (which holds the values -5 to 256) was changed from holding `PyIntObject`s in 2.x [1] to hold `PyLongObject`s [2].

So it looks like in Python 3.x, all integers are arbitrary-precision. I believe this was a significant contributor to early versions of Python 3.x being slower than 2.x.

[0] https://rubykaigi.org/2016/presentations/tanaka_akr.html

[1] https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3...

[2] https://github.com/python/cpython/blob/39f643614d03748a5fad4...

• go

  2,075 119,718 10.0 Go

  The Go programming language

  

Thanks, I missed that the Go code in the article was only performing a "128-bit / 64-bit" division.

However, based on this comment [0], it looks like Go does use Knuth's algorithm when dividing arbitrary-precision integers.

[0] https://github.com/golang/go/blob/2e94401277128f9e08e3319903...

• nim-stint

  3 77 7.0 Nim

  Stack-based arbitrary-precision integers - Fast and portable with natural syntax for resource-restricted devices.

  

• SaaSHub

  www.saashub.com featured

  SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives

  

Suggest a related project