BigNum and BigInt timings on the Pollard Rho algorithm

> A big frustration I have with extant languages is how most of the techniques > for manipulating the boundary between comptime and runtime -- generics, > static[], specialization of such, etc -- is invariably pretty limiting/buggy > to work with compared to what I think it could/should be. I've

BigNum and BigInt timings on the Pollard Rho algorithm

> for division, expect days of debugging, everyone gets it wrong, even Google > in Go and JavaScript Incidentally, it was recently found out that bigints has a bug in its division implementation:

BigNum and BigInt timings on the Pollard Rho algorithm

Heya mratsim! When I first got into Nim, you're the person that kept coming up time and time again for the stuff I was searching--including feature requests--so I think we have a lot of overlapping interests (even go, judging by your github picture). > But it is doable, for example for size sui

BigNum and BigInt timings on the Pollard Rho algorithm

> As for opinion pieces on bigint libraries in general, I also wrote a little > note on the rather sad state of GMP vs “anything else” at > > ## Why GMP? > > Unfortunately there is just no beating GMP when it comes to performance. It > is the unequivoc

BigNum and BigInt timings on the Pollard Rho algorithm

Heya, I don't really have anything to contribute but I recently uploaded which are intended to be ergonomic integers (wrapping GMP) and seems kind of maybe-possibly-peut-être adjacent to what you're looking for. No guarantees re polish or bugs or

BigNum and BigInt timings on the Pollard Rho algorithm

If I compile bigints with nim c -d:release --passC:-flto --passL:-s --mm:arc rho1.nim Run I get improved timings of: real1m24.066s user1m24.060s sys 0m0.000s Run

BigNum and BigInt timings on the Pollard Rho algorithm

@diesnoff I am not very conversant with Github. If you send me an email, I will send you the code: doug at dougtelford.com

BigNum and BigInt timings on the Pollard Rho algorithm

We are still very much interested in your Pollard Rho's example for the nim-lang/bigints. Don't hesitate to add it in the examples dir and PR it in Github. It might serves me to test my integers multiplication algorithms.

BigNum and BigInt timings on the Pollard Rho algorithm

You are correct. The timings go up from 1.38 seconds to 3.32 seconds, which is tolerable for better readability.

BigNum and BigInt timings on the Pollard Rho algorithm

Maybe also of interest:

BigNum and BigInt timings on the Pollard Rho algorithm

i think you're misreading the [docs](http://fedeomoto.github.io/bignum/#mod,Int,) for bignum, in that it does provide infix overloads, so `x =(x*x + c) mod n` syntax works just fine

BigNum and BigInt timings on the Pollard Rho algorithm

The markandsweep GC option was copied from other runs where it did improve the run time, but on the Pollard Rho it makes no difference.

BigNum and BigInt timings on the Pollard Rho algorithm

Why the markandsweep GC exactly ? What about others GC's ? No wonder, there is no fast multiplication algorithm of integers in std/bigint. Nim-stint should be better, among the pure Nim's implementation, but is more cryptographic specific (I think it supports unsigned integers only).

BigNum and BigInt timings on the Pollard Rho algorithm

Also (more popular) and

BigNum and BigInt timings on the Pollard Rho algorithm

I installed bigints and bignum from nimble. My understanding is that bigints (the slower one) is entirely written in nim while bignum is a wrapper for gmp. I have not tried bignumber.nim. It appears to be a work in progress. It does not have gcd (which I need), although it is easy to write one.

BigNum and BigInt timings on the Pollard Rho algorithm

I am assuming the slow one is the nim-lang library and the other the gmp wrapper? Also have you tried ?

BigNum and BigInt timings on the Pollard Rho algorithm

So far I am enjoying nim. I have a personal benchmark that I try on each new language that I try. It uses the Pollard Rho algorithm to find a factor or 2^257 - 1. I am using linux mint and a Ryzen 5600x cpu slightly overclocked (Geekbench single core score of 1730). For my nim runs I use: `