misc bigint, bignum #478

Open timotheecour opened 3 years ago

links

https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software

nim

c, c++

TomsFastMath

libtom https://www.libtom.net/TomsFastMath/

hebimath

suiginsoft/hebimath: arbitrary precision arithmetic library

v8

gmp

languages using gmp through ffi:

julia, haskell(ghc)

bsdnt

wbhart/bsdnt: BSD Licensed Bignum Library

I will look into this feature.

@xflywind what's your proposed approach?

What I have in mind is something like std/nre which wraps pcre library in a user friendly (YMMV) API.

Key features:

zero compromise on performance (otherwise people will eventually just use something else)
wrap into a friendly API, don't re-implement
std/jsbigints is a good start for API interface, but details can be discussed
if ever needed, partial re-implementations of underlying importc procs could be done, but this wouldn't be "in a vacuum", thanks to other wrapped APIs.
a pure nim re-implementation is IMO not an attractive approach, because performance is almost guaranteed to be sub-par, unless massive efforts are put into it (aka likely to become a dead project)

notes

VM: top-level (ie, not intermediate) vmops can be used, no need to worry about CT too much
licensing (refs https://github.com/bluescarni/mppp/issues/266)

The mp++ code itself is licensed under the MPL-2.0 license, but of course mp++ has a dependency on GMP. I am not a lawyer, but given that GMP is used in commercial computer algebra systems (Mathematica, Maple, ...) I am assuming there are no licensing conflicts with MPL-2.0 (of course as long as you are picking the LGPL in GMP's dual-iicense scheme).

LGPL could be a problem depending on use cases but if we can provide a fixed nim interface that allows swapping in different underlying libraries (gmp, mp++, a partial nim re-implementation, etc) then the licensing issue kind of goes away: the user would then be able to swap in a (supported) library of their choosing, depending on performance vs licensing terms.

scope

we could start with just bigints, but make the design extensible to all the features that mp++ offers (refs https://github.com/bluescarni/mppp)

Do you have seen this library? http://www.libtom.net

https://github.com/libtom/libtommath

All LibTom Projects are either under WTFPL or The Unlicense and free for all purposes

There are many license friendly libraries in this list https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software

It seems that the bignum implementation on V8 is not too complex too https://github.com/v8/v8/blob/master/src/numbers/bignum.cc

Python/Erlang/PHP C implementation Zig - Pure zig implementation https://tiehu.is/blog/zig2.html Crystal - GMP

Or we could provide backend switch options(Pure Nim and GMP) like haskell https://gitlab.haskell.org/ghc/ghc/-/tree/master/libraries/ghc-bignum/src/GHC/Num

https://gitlab.haskell.org/ghc/ghc/-/wikis/replacing-gmp-notes?version_id=34fc3735a0d1691071342c5459a9284dc2fe5760

I would like Pure-Nim implementation like D(https://dlang.org/phobos/std_bigint.html)

Performance is optimized for numbers below ~1000 decimal digits. For X86 machines, highly optimised assembly routines are used.

Some random benchmarks https://news.ycombinator.com/item?id=6990233

thanks for the links! https://www.libtom.net/TomsFastMath/ should be used instead of libtommath though

It is a port of LibTomMath with optional support for inline assembler multipliers Uses similar API as LibTomMath makes porting easy Faster than OpenSSL on the AMD64

we need to find benchmarks comparing gmp vs TomsFastMath

timotheecour / Nim