1.0.46 • Published 7 months ago

bigint-gcd v1.0.46

Weekly downloads
10
License
SEE LICENSE IN LI...
Repository
github
Last release
7 months ago

bigint-gcd

Greater common divisor (gcd) of two BigInt values using Lehmer's GCD algorithm. See https://en.wikipedia.org/wiki/Greatest_common_divisor#Lehmer's_GCD_algorithm. On my tests it is faster than Euclidean algorithm starting from 80-bit integers.

A version 1.0.2 also has something similar to "Subquadratic GCD" (see https://gmplib.org/manual/Subquadratic-GCD ), which is faster for large bigints (> 65000 bits), it should has better time complexity in case the multiplication is subquadratic, which is true in Chrome 93.

Installation

$ npm install bigint-gcd

Usage

import gcd from './node_modules/bigint-gcd/gcd.js';

console.log(gcd(120n, 18n));

There is also an implementation of the Extended Euclidean algorithm, which is useful to find the multiplicative modular inverse:

console.log(gcd.gcdext(3n, 5n)); // [2n, -1n, 1n]

And "Half GCD" which is useful to do the Rational reconstruction: It returns the transformation matrix and the transformed values after applying about half of the Euclidean steps.

console.log(gcd.halfgcd(1000000n, 1234567n)); // [-16n, 13n, 21n, -17n, 49371n, 12361n]

Performance:

The benchmark (see benchmark.html) resutls under Chrome 131:

bit sizegcdgmpy2 gcdinvmodgmpy2 invert
640.000270ms0.00030ms0.000310ms0.00066ms
1280.001270ms0.00047ms0.001720ms0.00137ms
2560.002660ms0.00153ms0.003650ms0.00224ms
5120.005460ms0.00321ms0.007630ms0.00391ms
10240.012080ms0.00653ms0.018250ms0.00806ms
20480.031130ms0.01429ms0.048220ms0.01587ms
40960.067870ms0.02979ms0.137700ms0.03590ms
81920.174320ms0.06837ms0.341310ms0.09035ms
163840.503910ms0.17093ms0.867190ms0.24908ms
327681.677730ms0.49816ms2.281250ms0.75801ms
655364.406250ms1.43795ms6.152340ms1.94962ms
13107211.828130ms3.98527ms16.937500ms4.98559ms
26214432.296880ms10.52619ms47.203130ms14.05025ms
52428886.625000ms28.16362ms123.500000ms38.94622ms
1048576213.312500ms70.89262ms310.062500ms103.71075ms
2097152519.250000ms177.16650ms773.875000ms269.43650ms
41943041255.750000ms433.85675ms1870.500000ms658.39875ms
83886082988.500000ms1069.74050ms4548.000000ms1673.88250ms

Benchmark:

import {default as LehmersGCD} from './gcd.js';

function EuclideanGCD(a, b) {
  while (b !== 0n) {
    const r = a % b;
    a = b;
    b = r;
  }
  return a;
}

function ctz4(n) {
  return 31 - Math.clz32(n & -n);
}
const BigIntCache = new Array(32).fill(0n).map((x, i) => BigInt(i));
function ctz1(bigint) {
  return BigIntCache[ctz4(Number(BigInt.asUintN(32, bigint)))];
}
function BinaryGCD(a, b) {
  if (a === 0n) {
    return b;
  }
  if (b === 0n) {
    return a;
  }
  const k = ctz1(a | b);
  a >>= k;
  b >>= k;
  while (b !== 0n) {
    b >>= ctz1(b);
    if (a > b) {
      const t = b;
      b = a;
      a = t;
    }
    b -= a;
  }
  return k === 0n ? a : a << k;
}

function FibonacciNumber(n) {
  console.assert(n > 0);
  var a = 0n;
  var b = 1n;
  for (var i = 1; i < n; i += 1) {
    var c = a + b;
    a = b;
    b = c;
  }
  return b;
}

function RandomBigInt(size) {
  if (size <= 32) {
    return BigInt(Math.floor(Math.random() * 2**size));
  }
  const q = Math.floor(size / 2);
  return (RandomBigInt(size - q) << BigInt(q)) | RandomBigInt(q);
}

function test(a, b, f) {
  const g = EuclideanGCD(a, b);
  const count = 100000;
  console.time();
  for (let i = 0; i < count; i++) {
    const I = BigInt(i);
    if (f(a * I, b * I) !== g * I) {
      throw new Error();
    }
  }
  console.timeEnd();
}

const a1 = RandomBigInt(128);
const b1 = RandomBigInt(128);

test(a1, b1, LehmersGCD);
// default: 426.200927734375 ms
test(a1, b1, EuclideanGCD);
// default: 1136.77294921875 ms
test(a1, b1, BinaryGCD);
// default: 1456.793212890625 ms

const a = FibonacciNumber(186n);
const b = FibonacciNumber(186n - 1n);

test(a, b, LehmersGCD);
// default: 459.796875 ms
test(a, b, EuclideanGCD);
// default: 2565.871826171875 ms
test(a, b, BinaryGCD);
// default: 1478.333984375 ms
1.0.46

7 months ago

1.0.45

7 months ago

1.0.44

9 months ago

1.0.43

9 months ago

1.0.42

9 months ago

1.0.39

9 months ago

1.0.38

10 months ago

1.0.40

9 months ago

1.0.41

9 months ago

1.0.37

10 months ago

1.0.36

10 months ago

1.0.35

10 months ago

1.0.34

10 months ago

1.0.33

11 months ago

1.0.29

1 year ago

1.0.32

1 year ago

1.0.31

1 year ago

1.0.30

1 year ago

1.0.28

2 years ago

1.0.22

2 years ago

1.0.21

2 years ago

1.0.20

2 years ago

1.0.26

2 years ago

1.0.25

2 years ago

1.0.24

2 years ago

1.0.23

2 years ago

1.0.27

2 years ago

1.0.19

3 years ago

1.0.18

3 years ago

1.0.17

3 years ago

1.0.16

3 years ago

1.0.9

3 years ago

1.0.8

3 years ago

1.0.11

3 years ago

1.0.10

3 years ago

1.0.15

3 years ago

1.0.14

3 years ago

1.0.13

3 years ago

1.0.12

3 years ago

1.0.7

4 years ago

1.0.6

4 years ago

1.0.5

4 years ago

1.0.4

4 years ago

1.0.3

4 years ago

1.0.2

4 years ago

1.0.1

5 years ago

1.0.0

5 years ago