[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: [ANN] lua-bint - Arbitrary precision integer arithmetic library in pure Lua**
**From**: Andrew Gierth <andrew@...>
**Date**: Sat, 11 Jul 2020 09:21:54 +0100

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