[RFC] Faster BigInt Implement via Malachite?

[qingshi163]

Summary

Currently we are using a num-bigint, a pure rust implement for BigInt support, but at lease now the implement is bit naive especially do not have small int optimize witch is a big deal.

The fastest BigInt implement I know is gmplib witch part of GNU, there is a high-level wrapper https://docs.rs/rug/latest/rug/ witch looks really nice.

Detailed Explanation

Drawbacks, Rationale, and Alternatives

I am worried about the platform supporting mostly for webassembly, I don't see gmplib has offical support for that. and compiling on Windows seem like depends on MingW.

Otherwise we probably need to have our own implement.

[fanninpm]

I am worried about the platform supporting mostly for webassembly, I don't see gmplib has offical support for that. and compiling on Windows seem like depends on MingW.

The malachite crate could be a viable alternative, as it's the fastest pure-Rust implementation from what I have seen so far.

[DimitrisJim]

Yes! The small int optimization (well, if n < 2^64 is small 😄) would be really cool to have.

In general, I think we should prefer options that don't require additional software to be present on the host machine, that's why I was also looking into malachite too.

@qingshi163 are there any other benefits to using rug over something like malachite? I can see that GMP would be battle hardened and probably be faster than malachite with the downside that it might be troublesome to set up.

[qingshi163]

malachite sounds great!