Add bigints to standard library

[uninhm]

Summary

Add arbitrary precision integers to standard library

Solution

Add the bigints library (it is in nimble) to standard library

https://github.com/def-/nim-bigints

[Araq]

Yeah, maybe we should really do that. The compiler itself would benefit.

[andreaferretti]

Before sanctioning a particular implementation of bingints into the stdlib, some performance improvements are in order. The fact is, there is also https://github.com/FedeOmoto/bignum, which is a wrapper aroung GMP, and if I recall correctly it is significantly faster (maybe things have improved lately). See also the discussion in https://forum.nim-lang.org/t/3677. The ideal would be to have a fast, pure nim implementation of bigints

[timotheecour]

• user defined quote literals, eg: -12.3E+4022'dec128 ; -128'i8 is transformed as i8("-128") RFCs#228 would allow nicer syntax 123'bigint instead of initBigInt"123" but can be done as a syntax upgrade so is not a blocker.
• https://github.com/FedeOmoto/bignum didn't get an update in 5y and basic usage seems to fail (nim r examples/pidigits.nim fails: Error: cannot open file: unsigned FedeOmoto/bignum#2) /cc @FedeOmoto , but could be revived; that being said, if it's a wrapper, it may not work at CT unless using CT FFI

The ideal would be to have a fast, pure nim implementation of bigints

for something like bigint, I'd say performance matters more than pure nim implementation if I had to choose between the 2, unless performance difference is small enough. But it also has to work at CT, which requires either: CT FFI, pure nim implementation fallback for the VM, or integrating via vmops (which is not ideal as it ties the compiler to a bignum library)

[Araq]

For the Nim compiler I don't care much about the speed, it's much more important that it has no dependencies.

[planetis-m]

def-/nim-bigints is maintained by contributors. It is not a good candidate.

[Araq]

Why not? Sometimes software is finished.

[bpr]

Why not? Sometimes software is finished.

If you look at the TODO, it's clear that this isn't finished yet. It's a good start though.

I think it's important to have a pure Nim BigInt library, rather than calling out to some potentially faster other (C) based library. IMO, Nim is a systems programming language, and if we can't have a Nim (maybe Nim + asm) library that's roughly as performant as a C + asm library, then Nim needs to be enhanced.

[alaviss]

Personally I'd prefer stint due to it's maturity, but it appears that the library depends on parts of nim-stew...

Also, shouldn't something like this be added to fusion instead of the stdlib?

[juancarlospaco]

I think varints can be replaced by a new bigints on stdlib, then stdlib remains kinda constant in size.

[Araq]

I think varints can be replaced by a new bigints on stdlib, then stdlib remains kinda constant in size.

Er uh, I think that's not how it works. ;-)

[juancarlospaco]

I was thinking varints suppose to be a bigint kinda thing but was never completely implemented, sorry.

[mratsim]

GMP is a big no-no due to the license and not working at compile-time

I don't mind contributing a bigint from scratch, it's not like I wrote those 3 times already:

• Stint: https://github.com/status-im/nim-stint
• Stint current refactor: Refactor to use an array backend Part 1 status-im/nim-stint#104
• Constantine: https://github.com/mratsim/constantine/blob/master/constantine/arithmetic/limbs.nim

Note that Constantine backend or Stint current refactor are either 2x faster than GMP on modular arithmetic to sometimes slower for bigints below 1024 bits (didn't test much beyond and didn't test on non-modular arithmetic)

The main reasons behind stew dependencies are threefold:

• Nim endians doesn't work at compile-time and calls integers what are actually raw bytes
• No utilities for seq[byte] and byte arrays in the stdlib
• bitops noUndefined returning 0 instead of the bitwidth of the type forces everyone to reimplement countLeadingZero or countTrailingZero:

  Nim/lib/pure/bitops.nim

  Lines 397 to 399 in 234f4a2

  	when noUndefined:
  	if x == 0:
  	return 0

  .
  I am unaware of any use-cases where 0 is the correct answer.

In terms of BigInt usage, I would need to know more about the use-cases:

• What kind of API: out-of-place like integers proc +(a, b: BigInt): BigInt or in-place like GMP
• Do we target embedded? Because BigInt require dynamic memory management, and so the API would have to be gmp-like instead of "integer-like" i.e. only in-place operations
• Do we want it thread-safe?
• Do we assume that people might do BigInt operation in a loop, in that case if we use the out-of-place API we might want a caching allocator as memory allocation will be a bottleneck

[zah]

If the compiler needs big integers, shouldn't it finally start to use Nimble packages? stint, as it exists right now is is a mature implementation of fixed-size integers. Duplicating it wouldn't be beneficial for anyone. The notion that the standard library is what the compiler needs to use is a damaging policy that prevents the Nim team to benefit from collaboration with any other team. It wouldn't be that hard to add a bunch of git submodules and -p:<path> directives in the compiler nim.cfg file and solve the problem in an afternoon.

[Araq]

@zah Agreed. However, I'm in no rush in adding big integer support for Nim and busy with other work considered more important.

[uninhm]

If the compiler needs big integers, shouldn't it finally start to use Nimble packages? stint, as it exists right now is is a mature implementation of fixed-size integers. Duplicating it wouldn't be beneficial for anyone. The notion that the standard library is what the compiler needs to use is a damaging policy that prevents the Nim team to benefit from collaboration with any other team. It wouldn't be that hard to add a bunch of git submodules and -p:<path> directives in the compiler nim.cfg file and solve the problem in an afternoon.

But, in competitive programming, the bigints are important, and you can't use external libraries