binary_gcd.js (2129B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2018 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 'use strict'; 20 21 /** 22 * Computes the greatest common divisor (gcd) using the binary GCD algorithm. 23 * 24 * ## References 25 * 26 * - Stein, Josef. 1967. "Computational problems associated with Racah algebra." _Journal of Computational Physics_ 1 (3): 397–405. doi:[10.1016/0021-9991(67)90047-2][@stein:1967]. 27 * 28 * [@stein:1967]: https://doi.org/10.1016/0021-9991(67)90047-2 29 * 30 * @private 31 * @param {integer} a - integer 32 * @param {integer} b - integer 33 * @returns {integer} greatest common divisor 34 * 35 * @example 36 * var v = gcd( 1.2676506002282294e+30, 9007199254740992 ); 37 * // returns 9007199254740992 38 */ 39 function gcd( a, b ) { 40 var k = 1; 41 var t; 42 43 // Simple cases: 44 if ( a === 0 ) { 45 return b; 46 } 47 if ( b === 0 ) { 48 return a; 49 } 50 // Reduce `a` and/or `b` to odd numbers and keep track of the greatest power of 2 dividing both `a` and `b`... 51 while ( a%2 === 0 && b%2 === 0 ) { 52 a /= 2; // right shift 53 b /= 2; // right shift 54 k *= 2; // left shift 55 } 56 // Reduce `a` to an odd number... 57 while ( a%2 === 0 ) { 58 a /= 2; // right shift 59 } 60 // Henceforth, `a` is always odd... 61 while ( b ) { 62 // Remove all factors of 2 in `b`, as they are not common... 63 while ( b%2 === 0 ) { 64 b /= 2; // right shift 65 } 66 // `a` and `b` are both odd. Swap values such that `b` is the larger of the two values, and then set `b` to the difference (which is even)... 67 if ( a > b ) { 68 t = b; 69 b = a; 70 a = t; 71 } 72 b -= a; // b=0 iff b=a 73 } 74 // Restore common factors of 2... 75 return k * a; 76 } 77 78 79 // EXPORTS // 80 81 module.exports = gcd;