mratsim
commented
2 years ago Since the limbs attribute of BigInt type is private, it might be complex to make another arithmetic library on top of this one (less optimizations on big integers due to less access to the internal representation).
I don't think there are low-level optimizations in a number-theory that require exposing the internal backend. All optimizations should be captured in:
- using uint64 as the base type
- Addition/substraction using add with carry and/or assembly
- Multiplication using assembly with Karatsuba for larger number of limbs
- Offering functions with signatures
proc add(r: var BigInt, a, b: BigInt)that allows algorithm implementers to reuse buffers. Those function should properly deal with aliasing.
For low-level optimizations, most of them are implemented in Constantine, though it deals with fixed size unsigned integers which are way simpler https://github.com/mratsim/constantine/tree/7d29cb9/constantine/math/arithmetic
konsumlamm
dlesnoff
Miller-Rabin test is a polynomial probabilistic test to determine wheter an integer is prime. It is way faster than deterministic algorithm (even if they are polynomial) primality test.
Here are some implementations of what I would like : Miller-Rabin test in Nim, by @mratsim : https://github.com/mratsim/nim-project-euler/blob/master/src/lib/primes.nim GMP optimized version : https://gmplib.org/repo/gmp/file/tip/mpz/millerrabin.c
A primality test can then lead to algorithms for factoring integers, finding the next prime, improve prime sieving … Another question this issue raises, is what do we want from this library to do ? Should it also be an arithmetic library ? Since the
limbsattribute ofBigInttype is private, it might be complex to make another arithmetic library on top of this one (less optimizations on big integers due to less access to the internal representation).