arithmetic-operations-for / naturals-big-endian Goto Github PK

In particular _mul

With the current implementation of @aureooms/js-integer.

x = ZZ.from(1); for ( let i = 1 ; i <= 10000 ; ++i ) x = x.mul( ZZ.from(i) ) ;
> x.div(x).toString()
ReferenceError: _imul_limb is not defined
    at _dc_div (/home/aureooms/dev/js/algorithms/arithmetic/js-integer/node_modules/@aureooms/js-integer-big-endian/lib/1-new/arithmetic/div/_dc_div.js:65:3)
    at _div (/home/aureooms/dev/js/algorithms/arithmetic/js-integer/node_modules/@aureooms/js-integer-big-endian/lib/2-api/_div.js:22:27)
    at Integer.divmod (/home/aureooms/dev/js/algorithms/arithmetic/js-integer/lib/Integer.js:145:33)
    at Integer.div (/home/aureooms/dev/js/algorithms/arithmetic/js-integer/lib/Integer.js:120:16)
    at repl:1:3
    at ContextifyScript.Script.runInThisContext (vm.js:23:33)
    at REPLServer.defaultEval (repl.js:336:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:533:10)

Compute the result of [1, 0, 0, 0] - [ x , y , z ] = increment_with_wrap([ r-1-x , r-1-y , r-1-z ]).

Currently the code computes carry as C = ... < .... Should use something to convert the result to an int before using C. Otherwise C type changes from Number to Boolean in the middle of the execution...
See https://stackoverflow.com/questions/7820683/convert-boolean-result-into-number-integer

e.g. bit to digit (log is base 10 log)

N = number of bits
X = number of digits

2^n = 10^x
log(2^n) = x
n * log(2) = x
X = log(2)*n
X = n * ln(2)/ln(10)

• _convert_ultra_slow can be discarded

Karatsuba's algorithm can be simplified for squaring.

(A1 * b + A0)^2 = A1^2 b^2 + 2 A1 A0 b + A0^2

Which yields three multiplications of half the size without any complicated rearrangement. Two of the recursive multiplications are squares. The multiplication by 2 is a limb multiplication (or a shift in base 2) Constant factors should be smaller because of all that.

knuth's and euclid's, e.g.

1. repeat until a = 0
   a, b = abs( a − b ), min( a, b )
   strip factors of 2 from a

2. repeat until a = 0
   a, b = abs( a − b ), min( a, b )
   a = a / 2 if even
   b = b / 2 if even

3. function gcd( a, b )
   if b = 0
   return a
   else
   return gcd( b, a mod b )

4. function gcd( a, b )
   while b ≠ 0
   t = b
   b = a mod b
   a = t
   return a

5. function gcd( a, b )
   repeat
   if a = 0
   return b
   b = a mod b
   if b = 0
   return a
   a = b mod a

I suggest js-integer-arithmetic-big-endian ?

Find a way to return new bounds for arrays when they shrink. In division algorithms for example.

See https://asmjs.org/spec/latest/#introduction.

There is an error with this repository's Renovate configuration that needs to be fixed. As a precaution, Renovate will stop PRs until it is resolved.

Error type: undefined. Note: this is a nested preset so please contact the preset author if you are unable to fix it yourself.

simply convert r's complement -> divide -> convert r's complement should work (where r is the radix)

Find an elegant way to allow truncated quotients (i.e. |C| < |A|), currently all algorithms require that |A| = |C| where A is the dividend/remainder and C is the quotient. This would allow to avoid a lot of memory allocation and back and fort copying.

CLRS mentions a divide and conquer approach to convert from radix a to radix b:

• split number x in two halves y and z such that x = y * a^n + z.
• compute base b representations Y and Z of each half recursively.
• return Y * a^n + Z with one multiplication, one addition, and a repeated squaring to obtain a^n in base b.

This issue provides visibility into Renovate updates and their statuses. Learn more

Open

These updates have all been created already. Click a checkbox below to force a retry/rebase of any.

• ⬆️ deps: Upgrade dependency xo to v0.45.0

• Check this box to trigger a request for Renovate to run again on this repository

Should add random 27 x 27 bits operands on byte arrays tests for mul and karatusba. Could extend to other operations like add or div.

the goal is to have the correct answer on 53 bits using byte arrays (UInt8Array).

See make-github-pseudonymous-again/js-integer#20

Conversion can still be fast when bases have a common power. A bit of shifting needs to be done but this is pretty similar to the fast conversion methods already implemented.

At least check that a[-1] and a[a.length] have not been written to. See https://v8.dev/blog/elements-kinds

Version 3.1.1 of @aureooms/js-itertools just got published.

</td>

This version is covered by your current version range and after updating it in your project the build failed.

As @aureooms/js-itertools is “only” a devDependency of this project it might not break production or downstream projects, but “only” your build or test tools – preventing new deploys or publishes.

I recommend you give this issue a high priority. I’m sure you can resolve this 💪

Your Greenkeeper Bot 🌴

Implement r's complement neg (2's complement generalized to any radix), it would allow to have 'smart' negative values in any base or at least make the methods of alu behave like C on primitive types for bases 2^n.

See http://www.cs.uwm.edu/~cs151/Bacon/Lecture/HTML/ch03s09.html if lost.

Should try to use _div_limb instead of _div for the large-to-small case.

Some bounds must be wrongly computed. The number of recursions is way too high and causes stack overflows.

Add a wrapper method for each recursive multiplication method, e.g:

function _mullarge ( ... ) {
    if input is large : _karatsuba ( ... ) ;
    else : _mulsmall ( ... ) ;
}
etc...

That way we avoid redundant size tests since operands size decreases at each step.

should be placed in neg/neg.js