misc bigint, bignum

[timotheecour]

links

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

nim

• Add bigints to standard library · Issue #14696 · nim-lang/Nim
• nim js: js BigInt · Issue #222 · timotheecour/Nim

c, c++

• mp++ https://github.com/bluescarni/mppp
• https://github.com/niekbouman/ctbignum
• benchmarks for > 2 limbs + question on licensing · Issue #266 · bluescarni/mppp
• FLINT: Fast Library for Number Theory
• ttmath.org / Bignum C++ library

other

• zig: blog
• Big Integers in Zig | Hacker News

TomsFastMath

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

hebimath

suiginsoft/hebimath: arbitrary precision arithmetic library

v8

• Adding BigInts to V8 · V8
• src/objects/bigint.cc - v8/v8 - Git at Google
• v8/bignum.cc at master · v8/v8

benchmarks

• http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-in-the-west/
• performance measurements · Wiki · Glasgow Haskell Compiler / GHC · GitLab

gmp

languages using gmp through ffi:

• julia, haskell(ghc)

bsdnt

wbhart/bsdnt: BSD Licensed Bignum Library

[ringabout]

I will look into this feature.

[timotheecour]

@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 benchmarks for > 2 limbs + question on licensing bluescarni/mppp#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)

[ringabout]

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

[timotheecour]

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