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

Thanks for pointing me to the method of Knuth's Art of Computer Programming
and preparing a concept code for it, this method looks like to be what I was looking for the division algorithm.
The algorithm you did with just the naive method of finding the quotient
looks like it will be more inefficient than the bit division I am doing at the moment
because I have to use a large base (2^32) and will take lots of iterations in the naive function,
however with `get_quotient_digit_advanced` implemented using the Knuth's algorithm
I see the potential to be more efficient, I'm going to research and play with it later.

Em seg., 13 de jul. de 2020 às 01:33, Martin <dyngeccetor8@disroot.org> escreveu:

On 2020-07-11 10:23 a.m., Francisco Olarte wrote:
> Similarly for long division, it seems to me you are doing bit a time
> division

I agree, for me it looks like bit division for bit-packed long numbers:

https://github.com/edubart/lua-bint/blob/master/bint.lua#L1089

I think, the more large BASE you have, the better. Ideally BASE should
be machine register size.

For division there is a method to guess quotient digit with error no
more than two units by dividing first two digits of numerator by first
digit of denominator. But you should scale both numer and denom before
that by BASE / (greatest_denom_digit + 1). And correct results
afterwards by dividing this scale factor before function return.

This method is presented in Knuth's Art of Computer Programming,
4.3.1, Algorithm D, Division of nonnegative integers. (But quite hard
to understand and expressed badly, IMHO.)

As a side note, your project reminded me my 15-year old project in
Delphi, I had mood and a couple of hours to implement simple division
of long numbers in Lua. There naive algorithm used for calculating
next quotient digit, which requires near BASE / 2 long subtractions.
But there is stub function for Knuth's algorithm.

Gist is:

https://gist.github.com/martin-eden/f015c1f08872a59ae8c1294524bb904a

Test run:

$lua5.3 long_div.lua
BASE 10
long_div_mod(8_7_9_3, 2_7_7) = 3_1, 2_0_6

(I'm not going to hijack this thread, but feel that creating new
theme with "[ANN]" is way too much while still wish to keep mention
of snippet.)

-- Martin