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

[Francisco Olarte <folarte@...>]

Eduardo...

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

I'm not soo sure I've fully understand your library, but I'm under the
impression you store the numbers as an array of 32 bit words. That's a
number in base B=2^32. But It seems you operate with them as a bit
string.

To work with this kind of things  what is normally done is to, assume
you have native multiplication and division on elements ( which it
seems you can ) operate on base B natively as much as possible. I
mean, have a function LSudivmod(L num, S denom)=>L quot, S rem ( I'm
using L for Long numbers, S for shorts ) which can be done in a single
pass, and, to convert to base 10, use the larger usable denominator (
that would be 10^9 for B=2^32 ). This way you can extract nine digits
in every pass.

Similarly for long division, it seems to me you are doing bit a time
division, where you can do it directly in base 32, just do it the same
way you do it when you divide by hand, word aligning, so you can
entirely avoid partial word shifts. You may have to do a little
"search" on each base-B digit of the quotient,  the same you do in
decimal in base 10 directly in your head, but as you can code a
multiply-substract without temporary storage it should be much faster.

Another thing. Multiprecision libraries have normally several
different representations for the numbers, like u32 array when they
are used for unsigned arithmetic + bit ops but base-10^n ( 10000 for
machines where you have u16xu16=u32, 10_000_000_000 where you have
32*32=64 ), many times with sign-magnitude representation among other
things to speed up the decimal printing. You may want to consider
having a conversion to decimal function but making the default
tostring() format hexadecimal, which would preserve the round trip
value when printing numbers but is much faster.

Francisco Olarte.