Function gcd_many

pub fn gcd_many(elems: &[u64]) -> u64

Finds the GCD (Greatest Common Divisor) for an array of elements.

Examples

use ads_rs::prelude::v1::math::gcd_many;

let res0 = gcd_many(&[42, 8, 144]);
let res1 = gcd_many(&[89, 144, 233, 377, 610]);
let res2 = gcd_many(&[25, 105, 235, 100]);

assert_eq!(2, res0);
assert_eq!(1, res1);
assert_eq!(5, res2);

Corner cases

• GCD of an empty array equals 0.
• GCD of a single element array equals that element.

use ads_rs::prelude::v1::math::gcd_many;

let res0 = gcd_many(&[]);
let res1 = gcd_many(&[25]);

assert_eq!(0, res0);
assert_eq!(25, res1);

Implementation details

• Stein’s algorithm is used.
• Time complexity: O(K * N²) where:
  • N - bits count in the biggest number.
  • K - number’s count