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 | }
|
---|