Use "binary GCD" algorithm

[shwaka]

"binary GCD" を使うと速く計算できるらしい。 先にgcd用のテストを書いた方が良い気がする。

Reference:

• Working with Rational numbers. Or how to write something when you just… | by Michael Spitsin | Medium
• Binary GCD algorithm - Wikipedia
• Binary GCD - ぎるばーとのノート

[shwaka]

ionspin/kotlin-multiplatform-bignum では binary GCD を使って実装してるっぽい。

https://github.com/ionspin/kotlin-multiplatform-bignum/blob/281d0e79ddc48883134bdbf91224c967bcbe6aee/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/integer/base63/array/BigInteger63Arithmetic.kt#L1731-L1743

[shwaka]

java.math.BigInteger.gcd も binary GCD で実装されてるっぽい？

• https://developer.classpath.org/doc/java/math/BigInteger-source.html
• https://github.com/MIPS/mips-src/blob/master/gcc/gcc-4.4.3/libjava/classpath/gnu/java/math/MPN.java#L643-L734

[shwaka]

とりあえず JavaRational で java.math.BigInteger.gcd を使ってみた cba1b695032b1684116c448d5ee74f7c044d3a72