7 ms·
Just an FYI for anyone reading: It's not the multiplicative inverse of 10 modulo 2^64. Multiplying by it only works if the number is divisible by 10. What it's
by mvanotti 12y ago
Just an FYI for anyone reading: It's not the multiplicative inverse of 10 modulo 2^64. Multiplying by it only works if the number is divisible by 10.
What it's happening here is something more clever:
let z be: (2^67 + 2)/10.
2^67 isn't divisible by 10 (that's why we add 2).
z = 14757395258967641293L
Now, I claim that
n/10 = floor(z * n/ 2^67)
z is an integer, but it represents the exact division of
(2^67 + 2)/10
we distribute the n:
(n * 2^67)/10 + 2 * n/10
we distribute the 2^67 division:
(n * 2^67)/(10 * 2^67) + 2 * n / (10 * 2^67)
simplify the terms:
n/10 + n/(10 * 2^66) [1]
Now:
floor(x/d + c) == floor(x/d) if c < 1/d
we want to take floor of that number[1], but as
n/(10 * 2^66) < 1/10
(the maximum value for n is 2^64 - 1), it follows that
floor(z * n / 2^67) = n/10.
That's what the code is doing:
0xcccccccccccccccd is 14757395258967641293L
the multiplication of z * n fits in 128 bits, and the mul instruction stores the higher 64 bits of $rax * $rdx into $rdx.
We need to divide by 2^67, whichs is shift 3 67 bits to the right. If we take the higher part (rdx) we get the higher 64 bits, and then we shift 3 bits to the right (shr $0x3, %rax) and that's our answer :).
Cool trick.