For the Library of Babel, I needed to convert very big numbers — hundreds of thousands of digits — from a base to another.
However, BigInt is limited:
- from string → the constructor
BigInt()accepts strings in bases 2, 8, 10, and 16, only; - to string →
toString()accepts a base of between 2 and 36.
I needed to work with bases 29 and 94, BigInt wasn't able to handle this. So I tried to implement the necessary algorithms in JavaScript.
From string
To convert a string to an integer, the classic algorithm is:
const fromBase = (
text: string,
base: bigint = 10n,
alphabet: string = "0123456789",
): bigint => {
let result = 0n;
// Start from the left of the string
for (let i = 0; i < text.length; i++) {
// for each digit, take the previous result,
// multiply it by the base, and add the new digit
result = result * base + BigInt(alphabet.indexOf(text.charAt(i)));
}
/* or we could do that, but it's slower:
// starting from the right of the string
for (let i = text.length - 1; i >= 0; i--) {
// multiply each digit by the base to the power of
// the digit position, and add it to the result
result +=
BigInt(alphabet.indexOf(text.charAt(i))) *
base ** BigInt(text.length - 1 - i);
}
*/
return result;
};
However, this is quite slow: it takes 30s on my machine to convert a string containing 500,000 random digits in base 10. (I tried to compile it to WebAssembly with AssemblyScript, but it made it even slower.)
Whereas it takes V8's BigInt only 100ms!
Turns out, BigInt uses a different algorithm, which can be found in V8's FromStringLarge function.
I'll leave it to you to read the description in V8's source code to understand how it works, and here is my JavaScript version:
const fromBase = (
text: string,
base: bigint = 10n,
alphabet: string = "0123456789",
): bigint => {
let parts = text
.split("")
.map((part) => [BigInt(alphabet.indexOf(part)), base]);
if (parts.length === 1) {
return parts[0][0];
}
let pairFull: boolean;
while (parts.length > 2) {
pairFull = false;
parts = parts.reduce<bigint[][]>((acc, cur, i) => {
if (!pairFull) {
if (i === parts.length - 1) {
acc.push(cur);
} else {
acc.push([
cur[0] * parts[i + 1][1] + parts[i + 1][0],
cur[1] * parts[i + 1][1],
]);
pairFull = true;
}
} else {
pairFull = false;
}
return acc;
}, []);
}
return parts[0][0] * parts[1][1] + parts[1][0];
};
It now takes 120ms to do the conversion! Just slightly slower than native BigInt. (And without any optimisations that are mentioned in V8's code.)
It's a bit counter intuitive, because this algorithm does about 1,000,000 iterations, instead of 500,000 for the classic algorithm (which does one for each digit). The reason is apparently that the multiplications are smaller, and possibly more optimisable because involving parts of the same size.
To string
To convert an integer to a string, the classic algorithm is the successive division method:
const toBase = (
value: bigint,
base: bigint = 10n,
alphabet: string = "0123456789",
): string => {
let result = "";
// At start, the dividend is equal to the value
let dividend = value;
let remainder;
while (dividend >= base) {
// We get the remainder of the dividend modulo the base
remainder = dividend % base;
// and we append it to the result, from right to left
result = alphabet[Number(remainder)] + result;
// then we divide the dividend by the base
// and that gives us the dividend for the next iteration
dividend = dividend / base;
}
result = alphabet[Number(dividend)] + result;
return result;
};
However, this is again quite slow: 30s to convert a bigint of 500,000 random digits in base 10.
For this too, V8's BigInt is much faster, and uses a different algorithm, « divide-and-conquer conversion ».
I recommend again to read the description in V8's code, as I couldn't explain it better, and here is my JavaScript version:
const toBase = (
value: bigint,
base: bigint = 10n,
alphabet: string = "0123456789",
): string => {
let result = "";
const divisors = [base];
const numberOfBitsInValue = value.toString(2).length;
while (divisors.at(-1).toString(2).length * 2 - 1 <= numberOfBitsInValue) {
divisors.push(divisors.at(-1) ** 2n);
}
const devide = (dividend: bigint, divisorIndex: number) => {
const divisor = divisors[divisorIndex];
const remainder = dividend % divisor;
const newDividend = dividend / divisor;
if (divisorIndex > 0) {
devide(remainder, divisorIndex - 1);
devide(newDividend, divisorIndex - 1);
} else {
result = `${alphabet[Number(newDividend)]}${
alphabet[Number(remainder)]
}${result}`;
}
};
devide(value, divisors.length - 1, true);
result = result.replace(new RegExp(`^${alphabet[0]}*`), "");
return result;
};
It now takes 150ms to do the conversion! (Also without any optimisations.)
And that's it. These two fast algorithms made possible my version of the the Library of Babel, which works entirely client-side.
Unexpected turn of events!
Thanks to these algorithms, I was able to finish the the Library of Babel. Every operation was taking a couple of seconds, at most, on my computer.
However, when testing the app on my phone, I realised that one operation was very slow: it took more than 3 minutes!
It turned out that it was a .toString() call on a very large bigint. The need was to convert this bigint to a string in base 10, so I didn't bother changing this .toString() to use the new algorithm toBase, because .toString() is able to handle base 10.
However, V8's source code shows that the fast .toString algorithm is behind the flag V8_ADVANCED_BIGINT_ALGORITHMS.
I guess this flag is ON when Chrome is built for Linux desktop, but OFF when it's built for Android.
I simply replaced .toString() by a call to toBase(...) and the app became fast on my phone too!
There is also a call to .toString(16) on the same number, but this one is very quick. The algorithm for base 16 must be much faster because it just has to split every byte into two hexadecimal values. So I didn't have to change this one.
Future
There is a TC39 proposal to give BigInt more capabilities, but as of 2023, it doesn't look like it's getting much traction.