for loops for bigint is very slow

[kaji331]

in Nim 2.0

import bigints

var x:BigInt = 1.initBigInt

for i in 1 .. 99999:
    x *= i.initBigInt
echo x

takes about 19 seconds in my computer, but Python 3.10 and Julia 1.6.7 only takes less than 2 seconds...

[dlesnoff]

Please share the Python and Julia code.

This huge time is due to the initialisations (initBigInt) inside the for loop.
Note that you should prefer a dedicated function for factorial computation, a direct for loop has an absurdly high binary complexity.
To lower the binary complexity, you may have a look at https://forum.nim-lang.org/t/8967.

I do not know about Julia, but Python has a native support for multiprecision integers with fast simple multiplication integers (Karatsuba).
I have begun to implement it, but I do not have the time to finish my pull request. Feel free to look at #95, if you are eager to contribute to this library.

If you really need to compute factorials fast and efficiently for your application, consider using e.g. Pari/GP or Sagemath or any good formal computer library.
This computation factorial(99_999) should not take more than 20ms when well parallelized.

[kaji331]

Please share the Python and Julia code.

This huge time is due to the initialisations (initBigInt) inside the for loop. Note that you should prefer a dedicated function for factorial computation, a direct for loop has an absurdly high binary complexity. To lower the binary complexity, you may have a look at https://forum.nim-lang.org/t/8967.

I do not know about Julia, but Python has a native support for multiprecision integers with fast simple multiplication integers (Karatsuba). I have begun to implement it, but I do not have the time to finish my pull request. Feel free to look at #95, if you are eager to contribute to this library.

If you really need to compute factorials fast and efficiently for your application, consider using e.g. Pari/GP or Sagemath or any good formal computer library. This computation factorial(99_999) should not take more than 20ms when well parallelized.

Thank you very much! I am just a beginner of Nim. So, this is a toy test. I didn't optimize the julia codes or python codes.

let
    x::BigInt = 1
        
    @time for i in 1:99999
        x *= i
    end
    println
end

x = 1
for i in range(1,100000):
    x = x * i
print(x)

I tried to use the bignum, but always errors...so, thank you again!

[dlesnoff]

Note that when compiling with the -d:danger flag, timings on my machine went from 23 seconds to 8 seconds.
I tried to remove initBigInt calls, but timings were similar:

import bigints

var x:BigInt = 1.initBigInt
var counter = 1.initBigInt

for i in 1 .. 99998:
  x *= counter
  counter.inc
x *= counter
echo x

[kaji331]

Note that when compiling with the -d:danger flag, timings on my machine went from 23 seconds to 8 seconds. I tried to remove initBigInt calls, but timings were similar:

import bigints

var x:BigInt = 1.initBigInt
var counter = 1.initBigInt

for i in 1 .. 99998:
  x *= counter
  counter.inc
x *= counter
echo x

Great! I think bigints or Nim need more optimizations...I will return to check it in future!