Re: Beating C++ std::gcd
"Ruud H.G. van Tol" <[email protected]>
| Newsgroups | gmane.comp.mathematics.pari.devel |
|---|---|
| Message-ID | <[email protected]> |
On 2026-08-08 13:51, Ruud H.G. van Tol wrote: > In a project I'm working on, I measured that about 25% of its runtime > was spent in gcd. > The program runs with 10 threads, on a MacBook M1 Max. > > On my clang, std::gcd came out as the best suited implementation. > Then I started looking for more speed, and tried a lookup table for > smaller values. > And that made it 20% faster! > gcd(a, b); 0 <= a <= 511; 0 <= b <= 1023. It is used in this project: https://oeis.org/A295344/a295344.gp.txt (GP code) https://oeis.org/A295344/a295344_1.cpp.txt (C++ code) https://oeis.org/A295344/a295344_7.txt (example of output) -- Ruud