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