Thank you for your advices and running benchmark code and shared results! I just wanted to see if LAR makes gcd in Nim's stdlib faster. If so, I would test it with negative inputs and other int types and if it still works correctly and faster, make PR that replace stdlib's gcd with the new gcd. But on Raspberry Pi 3 CPU, gcd in stdlib is fastest. And new gcd I wrote are not simpler than gcd in stdlib and I don't think they are good for replacing gcd in stdlib.
In the case of gcd, input values can be converted to absolute values and and run Euclidean algorithm as if all inputs were positive. `gcd` in bigints do so. My gcdLAR that requires both x and y always positive calculates the absolute value of inputs and both x and y should being positive inside the loop. > Which algorithm do other languages implement in their stdlib? Please provide > links to actual stdlib libraries for Rust, Julia, D, ... I don't know much about Rust but it seems they don't have gcd in stdlib. <https://users.rust-lang.org/t/why-no-gcd-in-standard-lib/36490> It seems Rust gcd crate provide 2 algorithms, simple euclid without LAR and binary gcd that looks similar to gcd in Nim's bigints: <https://docs.rs/gcd/latest/src/gcd/lib.rs.html> D's gcd looks also uses Binary Gcd or simple euclid: <https://github.com/dlang/phobos/blob/f7e523bc3c69506c3e7b4da7e78af93ed8547910/std/numeric.d#L3130> GCD in GCC's C++ standard lib uses Binary GCD: <https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/std/numeric;h=201bb8e74a121bba239e0799935e9e9467865954;hb=HEAD> It seems LAR is not used by these libraries. > Could you describe a little more what your flags do ? I compile it with `nim c -r -d:release testgcd.nim`. `-d:release` adds runtime error checks code, but I think it is more frequently used than `-d:danger`. I think it is important to measure times in similar condition people uses. My CPU is Intel Core i7-3612QM CPU @ 2.10GHz. > (std/bitops appears in the middle of the program, is it intentional?) I just added bitops module above `gcdSub` proc when I wrote it as it uses `countTrailingZeroBits`.
