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
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
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