You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Reacted by Juan Carlos, Unai HernΓ‘ndez Minaberry, Vicfred, IvΓ‘n VΓ‘zquez, Oscar N., Andrea Ferretti, ringabout, Lui, Omar David Sandoval Sida, Jonah Snider and 23 more
Yeah, maybe we should really do that. The compiler itself would benefit.
Reacted by Juan Carlos, IvΓ‘n VΓ‘zquez, Ivan Florentin, Unai HernΓ‘ndez Minaberry, Jonah Snider, Zoe Redfox, Felipe S. S. Schneider, Michael Campbell, ErikWDev, Justaus3r and 4 more
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
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)
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.
Reacted by ErikWDev, Dimitri Lesnoff and Satvik Pendem
Reacted by Andreas Rumpf and ΠΠ»Π΅ΠΊΡΠ°Π½Π΄Ρ Π‘ΡΠ°ΡΠΎΡΠΊΠΈΠ½
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:
.
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
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.
Reacted by Andreas Rumpf, Solitude, jibal, Esteban C Borsani and Michael Campbell
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
Reacted by ErikWDev
Reacted by Vicfred, IvΓ‘n VΓ‘zquez, jibal and Michael Campbell
The library does not even appear in the docs https://nim-lang.org/docs/lib.html
Maybe the issue might be renamed (or closed and open a new issue) for integration within the compiler.
I would like to know what kind of critical feature for the integration is missing, before spending time into efficiency improvement (if I can actually find the time for it). @mratsim raised an important issue about the library : we should consider using uint64 instead of uint32 which gives better asymptotic algorithms constants for all operations, especially if we implement naive operations like multiplication in O(n^2).
Half the number of limbs, that's four times less operations.
I know that @Araq does not care about performance, but the computations need to stay practically feasible. Benchmarking will enable us to detect regressions and/or improvements. For benchmarking and test purposes, we will need to generate random bigints.
There is still some discrepancies between bigints and int, see : nim-lang/bigints#90 (div/mod behaviour)
and : nim-lang/bigints#51 (bitwise operators for negative numbers).
@timotheecour proposed some benchmarking at the beginning of the thread :
benchmark: computing factorial(100) 1 million times
obviously a very partial benchmark but it's a start, feel free to suggest improvements/corrections
This kind of benchmark is not a good indicator for at least three kind of reasons. I would like to list them
this is not the algorithm we want to use in practice to compute a factorial. The binary splitting algorithm is more practical than the naΓ―ve algorithm, and depending on the number of digits there is an even better algorithm. GMP comes with a pre-built factorial mpz_fac_ui see : https://gmplib.org/manual/Number-Theoretic-Functions
I have done some tests with the factorial too at : https://forum.nim-lang.org/t/8967
We are on the order of several seconds for one factorial computation of the six digit number 123456! while it only takes 23ms for dedicated software for arithmetic in Pari/GP (like GMP).
It gets worse when scaling, but isn't it already acceptable timings for what we want to do ?
Anyway, n! has about n*log(n) digits (Stirling's approximation) so 100! has of the order of 600/700 digits. If we divide by 64, we can see, it is only a number of 10 limbs.
So we are only testing a very specific case of the library ! We are only testing the multiplication with the factorial computation !
When increasing the number of limbs, memory management and cache tuning becomes more crucial and needs to be taken into account.
we do the same computation of the exact same thing. Processors with predictive branching will optimize repetitive computations.
So results may vary greatly between different processors models/manufacturers.
we should launch some unmeasured computation before benchmarking. It "warms up" the processor for the computation. These "blank" computations does not appear in @timotheecour's scripts.
I wonder which operations will be the most useful for the compiler. Which number of limbs interests us ?
Aren't bit manipulation like setBit, logical operations and inc, dec operations more needed than costly arithmetic ops (multiplication, division essentially) ?
I believe we should tune the library specifically for the needs of the compiler. (If you disagree, please consider explaining why rather than just ππ½-ing this post).
The benefits of this library are very limited compared to the SciNim wrapper of GMP for other applications like scientific computation.
There are several other pitfalls in benchmarking, but the best I could think of is to actually test all the exported functions of the libraries on random bigints of given bit sizes and do these on batches of bigints.
If we try to measure the timings of just one multiplication operation, it might not be noticeable. So if we want to generate random numbers, and measure multiple multiplications, we don't want to measure the generation of the random numbers (nor the computation of multiplication).
But if we try to measure the timings of ten multiplication, we can average the timings.
So I would generate a batch of 2*ten BigInts, and do the multiplication on each pair of operands.
P.S: I'll edit the post when I'll be home for simplification. Sorry in the meantime. I am writing this from my job.
Yes, but that's a different issue (and it also applies to the other official libraries, like https://github.com/nim-lang/threading). It would be nice to get some more exposure for it though, so that hopefully more people suggest features, report bugs, etc.
Maybe the issue might be renamed (or closed and open a new issue) for integration within the compiler.
Agreed, that's also a different issue.
There is still some discrepancies between bigints and int, see : nim-lang/bigints#90 (div/mod behaviour)
and : nim-lang/bigints#51 (bitwise operators for negative numbers).
I'm well aware that there are still problems to be solved (heck, I opened those issues) and functions to be optimized and I appreciate your comments on that, but I don't think this issue is the right place to discuss that, https://github.com/nim-lang/bigints/issues is.
This issue is about adding bigints to std and we have an official library for bigints now, so it has been solved from my POV. @juancarlospaco can you explain why you don't think this issue should be closed?
the issue is about adding a bigints library to stdlib. we have a good candidate (https://github.com/nim-lang/bigints), which is now managed by nim-lang organization, but it still is not inside stdlib, it is an external package. The difference is that you need to install bigints with nimble to access it (it does not ship with nim) and versioning is independent from nim (which has its pros and cons). The issue can be closed when:
either there is a decision that we will not add bigints to stdlib and we keep bigints as an external package
I'm well aware that there are still problems to be solved (heck, I opened those issues) and functions to be optimized and I appreciate your comments on that, but I don't think this issue is the right place to discuss that, https://github.com/nim-lang/bigints/issues is.
I know that you are. Others aren't. I wasn't only addressing you.
I wanted to summarize important issues that I felt necessary to tackle for integration in the stdlib (before or after v2).
Yes people may check https://github.com/nim-lang/bigints/issues but actually nobody has the time to go through each of the ~15 currently opened issues, and the numerous technical posts of each of them, just to understand the state of the library.
That is why I created a special issue to do a roadmap (not up to date) nim-lang/bigints#76 as well as to discuss the versioning system.
I have been confused just like you by the difference between standard and official library. So:
Maybe the issue might be renamed (or closed and open a new issue) for integration within the compiler.
"Add bigints to standard library" is actually clear so no need to rename the issue.
Aren't bit manipulation like setBit, logical operations and inc, dec operations more needed than costly arithmetic ops (multiplication, division essentially) ?
No, if bit manipulation was needed a BitSeq is very simple and easy to optimize.
Multiplication is the backbone of bigints.
I believe we should tune the library specifically for the needs of the compiler. (If you disagree, please consider explaining why rather than just ππ½-ing this post).
The compiler needs are already covered by int128, which have been tested extensively after the past 3 years, but introduced many regressions at first
Furthermore, the current nim/bigint will be slower because of the limb size and also heap allocation.
Combined that with huge regression risks (for example mod/remainder behavior) I only see downside to have the compiler use it.
Activity
Araq commentedon Jun 17, 2020
Yeah, maybe we should really do that. The compiler itself would benefit.
andreaferretti commentedon Jun 17, 2020
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 commentedon Jun 17, 2020
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.nim r examples/pidigits.nimfails: 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 FFIfor something like bigint, I'd say performance matters more than
pure nim implementationif 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 commentedon Jun 17, 2020
For the Nim compiler I don't care much about the speed, it's much more important that it has no dependencies.
planetis-m commentedon Jun 17, 2020
def-/nim-bigints is maintained by contributors. It is not a good candidate.
Araq commentedon Jun 17, 2020
Why not? Sometimes software is finished.
bpr commentedon Jun 18, 2020
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 commentedon Jun 18, 2020
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 commentedon Jun 18, 2020
I think
varintscan be replaced by a newbigintson stdlib, then stdlib remains kinda constant in size.Araq commentedon Jun 18, 2020
Er uh, I think that's not how it works. ;-)
juancarlospaco commentedon Jun 18, 2020
I was thinking
varintssuppose to be a bigint kinda thing but was never completely implemented, sorry.mratsim commentedon Jun 18, 2020
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:
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:
seq[byte]and byte arrays in the stdlibnoUndefinedreturning 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
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:
proc +(a, b: BigInt): BigIntor in-place like GMPzah commentedon Jun 18, 2020
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 commentedon Jun 18, 2020
@zah Agreed. However, I'm in no rush in adding big integer support for Nim and busy with other work considered more important.
uninhm commentedon Jun 18, 2020
But, in competitive programming, the bigints are important, and you can't use external libraries
61 remaining items
ringabout commentedon Nov 24, 2021
Core team group should add more repos.
def- commentedon Nov 25, 2021
The double redirect works btw, old link from https://github.com/def-/nim-bigints goes to https://github.com/nim-lang/bigints
konsumlamm commentedon Jul 27, 2022
I think this can be closed now, since https://github.com/nim-lang/bigints exists.
dlesnoff commentedon Jul 28, 2022
The library does not even appear in the docs https://nim-lang.org/docs/lib.html
Maybe the issue might be renamed (or closed and open a new issue) for integration within the compiler.
I would like to know what kind of critical feature for the integration is missing, before spending time into efficiency improvement (if I can actually find the time for it).
@mratsim raised an important issue about the library : we should consider using uint64 instead of uint32 which gives better
asymptotic algorithmsconstants for all operations, especially if we implement naive operations like multiplication in O(n^2).Half the number of limbs, that's four times less operations.
I know that @Araq does not care about performance, but the computations need to stay practically feasible. Benchmarking will enable us to detect regressions and/or improvements. For benchmarking and test purposes, we will need to generate random bigints.
There is still some discrepancies between bigints and int, see : nim-lang/bigints#90 (div/mod behaviour)
and : nim-lang/bigints#51 (bitwise operators for negative numbers).
dlesnoff commentedon Aug 1, 2022
@timotheecour proposed some benchmarking at the beginning of the thread :
This kind of benchmark is not a good indicator for at least three kind of reasons. I would like to list them
this is not the algorithm we want to use in practice to compute a factorial. The binary splitting algorithm is more practical than the naΓ―ve algorithm, and depending on the number of digits there is an even better algorithm. GMP comes with a pre-built factorial
mpz_fac_uisee : https://gmplib.org/manual/Number-Theoretic-FunctionsI have done some tests with the factorial too at : https://forum.nim-lang.org/t/8967
We are on the order of several seconds for one factorial computation of the six digit number 123456! while it only takes 23ms for dedicated software for arithmetic in Pari/GP (like GMP).
It gets worse when scaling, but isn't it already acceptable timings for what we want to do ?
Anyway, n! has about n*log(n) digits (Stirling's approximation) so 100! has of the order of 600/700 digits. If we divide by 64, we can see, it is only a number of 10 limbs.
So we are only testing a very specific case of the library ! We are only testing the multiplication with the factorial computation !
When increasing the number of limbs, memory management and cache tuning becomes more crucial and needs to be taken into account.
we do the same computation of the exact same thing. Processors with predictive branching will optimize repetitive computations.
So results may vary greatly between different processors models/manufacturers.
we should launch some unmeasured computation before benchmarking. It "warms up" the processor for the computation. These "blank" computations does not appear in @timotheecour's scripts.
I wonder which operations will be the most useful for the compiler. Which number of limbs interests us ?
Aren't bit manipulation like setBit, logical operations and inc, dec operations more needed than costly arithmetic ops (multiplication, division essentially) ?
I believe we should tune the library specifically for the needs of the compiler. (If you disagree, please consider explaining why rather than just ππ½-ing this post).
The benefits of this library are very limited compared to the SciNim wrapper of GMP for other applications like scientific computation.
There are several other pitfalls in benchmarking, but the best I could think of is to actually test all the exported functions of the libraries on random bigints of given bit sizes and do these on batches of bigints.
If we try to measure the timings of just one multiplication operation, it might not be noticeable. So if we want to generate random numbers, and measure multiple multiplications, we don't want to measure the generation of the random numbers (nor the computation of multiplication).
But if we try to measure the timings of ten multiplication, we can average the timings.
So I would generate a batch of 2*ten BigInts, and do the multiplication on each pair of operands.
P.S: I'll edit the post when I'll be home for simplification. Sorry in the meantime. I am writing this from my job.
konsumlamm commentedon Aug 1, 2022
Yes, but that's a different issue (and it also applies to the other official libraries, like https://github.com/nim-lang/threading). It would be nice to get some more exposure for it though, so that hopefully more people suggest features, report bugs, etc.
Agreed, that's also a different issue.
I'm well aware that there are still problems to be solved (heck, I opened those issues) and functions to be optimized and I appreciate your comments on that, but I don't think this issue is the right place to discuss that, https://github.com/nim-lang/bigints/issues is.
This issue is about adding bigints to std and we have an official library for bigints now, so it has been solved from my POV.
@juancarlospaco can you explain why you don't think this issue should be closed?
pietroppeter commentedon Aug 1, 2022
the issue is about adding a bigints library to stdlib. we have a good candidate (https://github.com/nim-lang/bigints), which is now managed by nim-lang organization, but it still is not inside stdlib, it is an external package. The difference is that you need to install bigints with nimble to access it (it does not ship with nim) and versioning is independent from nim (which has its pros and cons). The issue can be closed when:
dlesnoff commentedon Aug 1, 2022
I know that you are. Others aren't. I wasn't only addressing you.
I wanted to summarize important issues that I felt necessary to tackle for integration in the stdlib (before or after v2).
Yes people may check https://github.com/nim-lang/bigints/issues but actually nobody has the time to go through each of the ~15 currently opened issues, and the numerous technical posts of each of them, just to understand the state of the library.
That is why I created a special issue to do a roadmap (not up to date) nim-lang/bigints#76 as well as to discuss the versioning system.
I have been confused just like you by the difference between standard and official library. So:
"Add bigints to standard library" is actually clear so no need to rename the issue.
mratsim commentedon Aug 2, 2022
No, if bit manipulation was needed a BitSeq is very simple and easy to optimize.
Multiplication is the backbone of bigints.
The compiler needs are already covered by int128, which have been tested extensively after the past 3 years, but introduced many regressions at first
Furthermore, the current nim/bigint will be slower because of the limb size and also heap allocation.
Combined that with huge regression risks (for example mod/remainder behavior) I only see downside to have the compiler use it.
Re benchmarking:
juancarlospaco commentedon Aug 2, 2022
But then
int128needs to be made public and documented properly. π€mratsim commentedon Aug 3, 2022
No it doesn't, it's compiler only.
A public int128 should instead use the C compiler builtins like: https://github.com/rockcavera/nim-nint128/blob/f88047b/src/nint128/nint128_cint128.nim#L72-L77
juancarlospaco commentedon Aug 3, 2022
I understand, then maybe a public and documented
int128backed by compiler is doable,just documenting its limitations should be enough.
dlesnoff commentedon Aug 3, 2022
I post here an old discussion (31 january 2022) on Discord concerning the desire to change to bigints:

Araq commentedon Aug 27, 2023
https://github.com/nim-lang/bigints/ is official.