Re: [ANN] lua-bint - Arbitrary precision integer arithmetic library in pure Lua

[Andrew Gierth <andrew@...>]

>>>>> "Philippe" == Philippe Verdy <verdyp@gmail.com> writes:

 Philippe> Peecomputing scaled reciprocal is unfeasible for large words.
 Philippe> Your lookup table for example with 32-bit words would have
 Philippe> 2^32 entries (excluding the reciprocal of 0). That lookup
 Philippe> would be enormous.

You only need to precompute the divisor, so only values B^(2^n) for a
small range of n and whatever values of B you actually want to optimize
for (usually only 10, since 8 and 16 are better handled with bit shifts
and using other bases is vanishingly rare).

Any compiler worth the name these days does this as a matter of course -
look at the code generated for, say, n / 100000000U in C where n is a
uint64_t, and you'll see it does a multiply by 12379400392853802749 and
a 90-bit right-shift on the 128-bit product. The multiplier there is
ceil(2^90 / 100000000), with the scaling factor chosen so that the
product requires no more than 128 bits and always truncates to the
correct result (this isn't possible for all divisors, but usually is for
ones that you care about).

-- 
Andrew.