search

rust-num / num-bigint

Big integer types for Rust
Apache License 2.0
544 stars 189 forks source link

Mixed-algorithm GCD (potential optimization) #296

Open Rudxain opened 7 months ago

Rudxain commented 7 months ago

Similarly to how multiplication uses different algorithms depending on some conditions, GCD could be optimized by using more than 1 algorithm. It should look something like this: https://github.com/Rudxain/EsoMath.js/blob/8c896b3804b40b8c0307a0a32c10264ff82a52b5/src/mod/factors.js#L52-L178

[!note] Here's an alt link to the proof that GCDs of Mersennes are Mersennes themselves: https://math.stackexchange.com/a/7561 . Both links have different proofs.

Yes, I know, my code is an abomination.

Honestly, I don't even know if that JS impl is 100% correct , or if it's always faster than a simple Stein. Some explicit special-case branches (the guard clauses) may be unnecessary, as one (or more) of these 3 algos may implicitly handle them efficiently.

However, it uses Lehmer's algorithm, which is proven to be faster than Stein's for huge ints. IIRC, the Euclidean algorithm is also faster than Stein's, but only for small ints (~128bits?).

I'm willing to open a PR for this, but I need to "get familiar" with the codebase

cuviper commented 7 months ago

It's definitely something we could experiment with!