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

10 months ago

1.0.38

10 months ago

1.0.40

10 months ago

1.0.41

10 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