123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 12 August 2017
- # https://github.com/trizen
- # Algorithm invented by J. Stein in 1967, described in the
- # book "Algorithmic Number Theory" by Eric Bach and Jeffrey Shallit.
- func binary_gcd(u, v) {
- var g = 1
- while (u.is_even && v.is_even) {
- u >>= 1
- v >>= 1
- g <<= 1
- }
- while (u) {
- if (u.is_even) {
- u >>= 1
- }
- elsif (v.is_even) {
- v >>= 1
- }
- elsif (u >= v) {
- u -= v
- u >>= 1
- }
- else {
- v -= u
- v >>= 1
- }
- }
- return (g * v)
- }
- say binary_gcd(10628640, 3628800) #=> 1440
- say binary_gcd(3628800, 10628640) #=> 1440
- var u = 484118311800307409686872049018968526148964320406131317406564776592214983358038627898935326228550128722261905040875508300794183477624832000000000000000000000000
- var v = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
- say binary_gcd(u, v) #=> 33464469725118339932738475939854523519700805708105926500308251028510111778609255576238987149312000000000000000000000000
- say binary_gcd(v, u) #=> 33464469725118339932738475939854523519700805708105926500308251028510111778609255576238987149312000000000000000000000000
|