News for hackers. Stuff that matters.
Re:Rust: 128 bit integers preparing to be released by cesarb on Sunday December 04, 2016 @08:14AM (#13099869)
One example I know of is the Poly1305 MAC algorithm, which at its core multiplies two numbers and reduces the result modulo 2^130-5. The C implementation at https://github.com/floodyberry/poly1305-donna shows three ways to represent the 130-bit numbers during the calculation: as ten 13-bit limbs, as five 26-bit limbs, or as two 44-bit limbs plus one 42-bit limb. In the middle of the multiplication, before the carries are propagated, you need twice the number of bits: the first option needs 26 bits, which can be done with a 16x16->32 bit multiplication. The second option needs 52 bits, which can be done with a 32x32->64 bit multiplication. The last option, however, needs 88 bits, which won't fit in 64 bits; you need a 128-bit integer, so you can do a 64x64->128 bit multiplication.

At least on x86-64, the 64x64->128 bit multiplication is a single instruction, like the 32x32->64 bit and the 16x16->32 bit multiplications. Doing the calculation with only three limbs is clearly faster than doing it with five limbs; to start with, using 3 limbs you need 9 multiplies, while with 5 limbs you have to do 25 multiplies. The carry propagation and reduction steps also take time proportional to the number of limbs.

There are no comments on this comment yet.