Re: Beating C++ std::gcd

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

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