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

[Andrew Gierth <andrew@...>]

>>>>> "Eduardo" == Eduardo Bart <edub4rt@gmail.com> writes:

 Eduardo> What I would like to optimize more is the conversion from base
 Eduardo> 2 to base 10 in the library, it is used when printing big
 Eduardo> numbers in base 10 as string. My `tobase` function calls too
 Eduardo> many times `udivmod` (unsigned integer division with modulus)
 Eduardo> for really large integers (8192 bits or so) and this make
 Eduardo> tostring very slow for big numbers. If you have any ideas how
 Eduardo> I could optimize that base conversion (or perhaps udivmod) I
 Eduardo> would appreciate it.

There are two standard tricks for this (and you should use both).

First, don't repeatedly divide by the base. Instead, precompute powers
of the base (I'll assume 10 for example purposes): 10^2, 10^4, 10^8,
10^16, etc., up to a value that's close to (but less than) half of the
input bits. That way, the remainder after dividing by that largest size
will always fit in half the bits, and no more than three (often only
two) such full-length divisions are needed to break the input into
convenient chunks, which you then divide into halves, etc.

Second, don't use division at all (except possibly for that first step,
if you don't want to have to deal with doing an N*N->2N bit multiply, or
a "high half" multiply which will suffice). Instead, do division by
way of multiplication by scaled reciprocal (which you can precompute).

-- 
Andrew.