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

[Martin <dyngeccetor8@...>]

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