Factorial computation in Nim

> Multipoint evaluation usually requires FFT for integers / Number Theoretic > Transform. I forgot about this. This is definitely quite technical to handle > limbs correctly and find thresholds between algorithms. Karatsuba algorithm > is not hard to implement, I have a PR in which it is

Factorial computation in Nim

@enthus1ast Thanks, your compilation flags did improve the timings ! with -d:release : CPU Time [Naive factorial] 6.429s CPU Time [Factorial with binary splitting] 3.698s with nim c -d:danger --opt:speed -d:lto -r factorial.nim: CPU Time [Naive factorial] 3.458s CPU Time [Factorial with

Factorial computation in Nim

I've implemented the same in Theo (, renamed Megalo, for "number-theory"). import ../theo/[ datatypes, io_hex, io_int, op_mul, op_init, op_comparisons ] import std/[times, strutils] template benchmark(benchmarkName: string,

Factorial computation in Nim

> I did not find any explanations of how to interpret the NimProf Not sure about it either, I use valgrind. On Windows, Intel VTune might work. Saw somebody mention it here on the forum. > Maybe we should use Boost for Windows platform ? Unfortunately, the one really fast backend supported by

Factorial computation in Nim

Here is an implementation using `bignum` and benchmarking with `benchy`. import std/strutils import benchy import bignum template one(): Int = newInt(1) #[ template benchmark(benchmarkName: string, code: untyped) = block: let t0 =

Factorial computation in Nim

Try to compile with: "-d:danger --opt:speed -d:lto"

Factorial computation in Nim

You are using the `bigints` library. Its [documentation](https://github.com/nim-lang/bigints) says that arithmetic operations are not optimized for performance.

Factorial computation in Nim

> Do you use other things for benchmarking ? Try [cpuTime()](https://nim-lang.org/docs/times.html#cpuTime) or [monotimes](https://nim-lang.org/docs/monotimes.html).

Factorial computation in Nim

What's the question ?

Factorial computation in Nim

I tried to benchmark binary splitting algorithm to compute factorial with nim-lang/bigints. There are some more complex (and faster) algorithms but they require polynomial fast multiplication and multipoint evaluation, which is a lot to implement (and I do not know algebra libraries in Nim