I do not intend this to be merged, but at the moment just present as an experiment in using crypto-bigint instead of num-bigint. Not sure how/if you want to proceed with it, but I just wanted something that matches the speed of GMP, and can be used in WASM.
It shows a significant speed-up over master:
Benchmark: 645.33 ms vs 1.2533 s
cargo test --release: 1.18s vs 13.60s
Notes:
It is tricky to compare it with the reference implementation properly; I tested it by basically logging local variables in methods and comparing outputs (had to use a deterministic RNG and match the behavior of sampling randoms, too), but it was mostly manual. So we will definitely have to have more eyes over it.
The num-bigint implementation can be sped up too by using Montgomery representation in lucas(), but I can't tell how big the effect will be.
This implementation can be also improved further by pre-computing inverses for the small primes so that we could calculate the remainders faster. According to https://gmplib.org/~tege/division-paper.pdf the division speed-up is about 30%, and those remainders take quite a bit of time according to my profiling.
Currently this PR is using master of crypto-bigint, because the Montgomery stuff is not released yet.
I do not intend this to be merged, but at the moment just present as an experiment in using
crypto-bigintinstead ofnum-bigint. Not sure how/if you want to proceed with it, but I just wanted something that matches the speed of GMP, and can be used in WASM.It shows a significant speed-up over
master:cargo test --release: 1.18s vs 13.60sNotes:
num-bigintimplementation can be sped up too by using Montgomery representation inlucas(), but I can't tell how big the effect will be.masterofcrypto-bigint, because the Montgomery stuff is not released yet.