[6a3a178] | 1 | /**
|
---|
| 2 | * @license
|
---|
| 3 | * Copyright Google LLC All Rights Reserved.
|
---|
| 4 | *
|
---|
| 5 | * Use of this source code is governed by an MIT-style license that can be
|
---|
| 6 | * found in the LICENSE file at https://angular.io/license
|
---|
| 7 | */
|
---|
| 8 | /**
|
---|
| 9 | * Represents a big integer using a buffer of its individual digits, with the least significant
|
---|
| 10 | * digit stored at the beginning of the array (little endian).
|
---|
| 11 | *
|
---|
| 12 | * For performance reasons, each instance is mutable. The addition operation can be done in-place
|
---|
| 13 | * to reduce memory pressure of allocation for the digits array.
|
---|
| 14 | */
|
---|
| 15 | export declare class BigInteger {
|
---|
| 16 | private readonly digits;
|
---|
| 17 | static zero(): BigInteger;
|
---|
| 18 | static one(): BigInteger;
|
---|
| 19 | /**
|
---|
| 20 | * Creates a big integer using its individual digits in little endian storage.
|
---|
| 21 | */
|
---|
| 22 | private constructor();
|
---|
| 23 | /**
|
---|
| 24 | * Creates a clone of this instance.
|
---|
| 25 | */
|
---|
| 26 | clone(): BigInteger;
|
---|
| 27 | /**
|
---|
| 28 | * Returns a new big integer with the sum of `this` and `other` as its value. This does not mutate
|
---|
| 29 | * `this` but instead returns a new instance, unlike `addToSelf`.
|
---|
| 30 | */
|
---|
| 31 | add(other: BigInteger): BigInteger;
|
---|
| 32 | /**
|
---|
| 33 | * Adds `other` to the instance itself, thereby mutating its value.
|
---|
| 34 | */
|
---|
| 35 | addToSelf(other: BigInteger): void;
|
---|
| 36 | /**
|
---|
| 37 | * Builds the decimal string representation of the big integer. As this is stored in
|
---|
| 38 | * little endian, the digits are concatenated in reverse order.
|
---|
| 39 | */
|
---|
| 40 | toString(): string;
|
---|
| 41 | }
|
---|
| 42 | /**
|
---|
| 43 | * Represents a big integer which is optimized for multiplication operations, as its power-of-twos
|
---|
| 44 | * are memoized. See `multiplyBy()` for details on the multiplication algorithm.
|
---|
| 45 | */
|
---|
| 46 | export declare class BigIntForMultiplication {
|
---|
| 47 | /**
|
---|
| 48 | * Stores all memoized power-of-twos, where each index represents `this.number * 2^index`.
|
---|
| 49 | */
|
---|
| 50 | private readonly powerOfTwos;
|
---|
| 51 | constructor(value: BigInteger);
|
---|
| 52 | /**
|
---|
| 53 | * Returns the big integer itself.
|
---|
| 54 | */
|
---|
| 55 | getValue(): BigInteger;
|
---|
| 56 | /**
|
---|
| 57 | * Computes the value for `num * b`, where `num` is a JS number and `b` is a big integer. The
|
---|
| 58 | * value for `b` is represented by a storage model that is optimized for this computation.
|
---|
| 59 | *
|
---|
| 60 | * This operation is implemented in N(log2(num)) by continuous halving of the number, where the
|
---|
| 61 | * least-significant bit (LSB) is tested in each iteration. If the bit is set, the bit's index is
|
---|
| 62 | * used as exponent into the power-of-two multiplication of `b`.
|
---|
| 63 | *
|
---|
| 64 | * As an example, consider the multiplication num=42, b=1337. In binary 42 is 0b00101010 and the
|
---|
| 65 | * algorithm unrolls into the following iterations:
|
---|
| 66 | *
|
---|
| 67 | * Iteration | num | LSB | b * 2^iter | Add? | product
|
---|
| 68 | * -----------|------------|------|------------|------|--------
|
---|
| 69 | * 0 | 0b00101010 | 0 | 1337 | No | 0
|
---|
| 70 | * 1 | 0b00010101 | 1 | 2674 | Yes | 2674
|
---|
| 71 | * 2 | 0b00001010 | 0 | 5348 | No | 2674
|
---|
| 72 | * 3 | 0b00000101 | 1 | 10696 | Yes | 13370
|
---|
| 73 | * 4 | 0b00000010 | 0 | 21392 | No | 13370
|
---|
| 74 | * 5 | 0b00000001 | 1 | 42784 | Yes | 56154
|
---|
| 75 | * 6 | 0b00000000 | 0 | 85568 | No | 56154
|
---|
| 76 | *
|
---|
| 77 | * The computed product of 56154 is indeed the correct result.
|
---|
| 78 | *
|
---|
| 79 | * The `BigIntForMultiplication` representation for a big integer provides memoized access to the
|
---|
| 80 | * power-of-two values to reduce the workload in computing those values.
|
---|
| 81 | */
|
---|
| 82 | multiplyBy(num: number): BigInteger;
|
---|
| 83 | /**
|
---|
| 84 | * See `multiplyBy()` for details. This function allows for the computed product to be added
|
---|
| 85 | * directly to the provided result big integer.
|
---|
| 86 | */
|
---|
| 87 | multiplyByAndAddTo(num: number, result: BigInteger): void;
|
---|
| 88 | /**
|
---|
| 89 | * Computes and memoizes the big integer value for `this.number * 2^exponent`.
|
---|
| 90 | */
|
---|
| 91 | private getMultipliedByPowerOfTwo;
|
---|
| 92 | }
|
---|
| 93 | /**
|
---|
| 94 | * Represents an exponentiation operation for the provided base, of which exponents are computed and
|
---|
| 95 | * memoized. The results are represented by a `BigIntForMultiplication` which is tailored for
|
---|
| 96 | * multiplication operations by memoizing the power-of-twos. This effectively results in a matrix
|
---|
| 97 | * representation that is lazily computed upon request.
|
---|
| 98 | */
|
---|
| 99 | export declare class BigIntExponentiation {
|
---|
| 100 | private readonly base;
|
---|
| 101 | private readonly exponents;
|
---|
| 102 | constructor(base: number);
|
---|
| 103 | /**
|
---|
| 104 | * Compute the value for `this.base^exponent`, resulting in a big integer that is optimized for
|
---|
| 105 | * further multiplication operations.
|
---|
| 106 | */
|
---|
| 107 | toThePowerOf(exponent: number): BigIntForMultiplication;
|
---|
| 108 | }
|
---|