Port to BigInt? #6
Comments
|
Basic sketch, proof of concept, showing both ascending and descending operation: "use strict";
function bigIntToDigits(x, base) {
let ret = [];
while (x > 0) {
ret.push(x % base);
x /= base;
}
ret.reverse();
return ret;
}
function bigIntSubdivide(l, r, n, base) {
while ((r - l) / n === 0n) {
r *= base;
l *= base;
}
let delta = (r - l) / n;
let ret = [];
let nNumber = Number(n);
{
let prev = l;
for (let i = 0; i < nNumber; i++) {
let next = prev + delta;
ret.push(next);
prev = next;
}
}
return ret;
}
function digits2bigint(arr, base) {
arr = arr.map(BigInt);
let ret = 0n;
let pow = 1n;
for (let i = arr.length - 1; i >= 0; --i) {
ret += arr[i] * pow;
pow *= base;
}
return ret;
}
function makeUniqueNumArr(vov, left) {
vov.forEach((arr, i) => {
const prev = vov[i - 1] || left;
const hit = arr.findIndex((n, i) => n !== prev[i]);
if (hit >= 0) { vov[i] = vov[i].slice(0, hit + 1); }
});
return vov;
}
function main(left, right, numStringsNumber, num2sym, shorten = true) {
let sym2num = new Map(num2sym.map((sym, i) => [sym, i]));
let base = BigInt(num2sym.length);
const str2digits = s => s.split('').map(c => sym2num.get(c));
let flipped = left > right;
if (flipped) { [left, right] = [right, left]; }
let maxLen = Math.max(left.length, right.length);
let bigintarr = bigIntSubdivide(
digits2bigint(str2digits(num2sym[1] + left + num2sym[0].repeat(maxLen - left.length)), base),
digits2bigint(str2digits(num2sym[1] + right + num2sym[0].repeat(maxLen - right.length)), base),
BigInt(numStringsNumber),
base,
);
if (!shorten) {
if (flipped) { bigintarr.reverse(); }
return bigintarr.map(n => bigIntToDigits(n, base).slice(1).map(n => num2sym[n]).join(''));
}
let ret = makeUniqueNumArr(bigintarr.map(n => bigIntToDigits(n, base).slice(1).map(n => num2sym[n])), left.split(''))
.map(v => v.join(''));
if (flipped) { ret.reverse(); }
return ret;
}
function checkAsc(v) {
if (!v.every((s, i) => (!i) || v[i - 1] < s)) { throw new Error('invalid'); }
}
function checkDesc(v) {
if (!v.every((s, i) => (!i) || v[i - 1] > s)) { throw new Error('invalid'); }
}
if (require.main === module) {
let num2sym = '0123456789abcdef'.split('');
let left = '03a';
let right = '2';
let numStrings = 1000;
let mudder = require('./index');
let hex = new mudder.SymbolTable(num2sym);
for (let i = 0; i < 2; i++) {
if (i > 0) { [left, right] = [right, left]; }
let sameLength = main(left, right, numStrings, num2sym, false);
let shortAsPossible = main(left, right, numStrings, num2sym, true);
let gold = hex.mudder(left, right, Number(numStrings));
console.log('\n\nBigIntSameLen\tBigIntShort\tMudder');
console.log(gold.map((gold, i) => [sameLength[i], shortAsPossible[i], gold].join('\t')).join('\n'));
let check = (left < right) ? checkAsc : checkDesc;
check(sameLength);
check(shortAsPossible);
check(gold);
}
}Outputs: |
|
Using the above proof-of-concept code, generating 20'000 strings between '03a' and '2' in hexadecimal symbol table:
Certainly we should offer this for BigInt-enabled runtimes, with the fallback to the existing manual big-int-like implementation available. |
|
I know this is an old issue, but just a heads up - the above implementation can be buggy, especially around lower values of > main("03a", "2", 1, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '2' ] // bug - array contains value of right
> main("03a", "2", 2, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '1', '2' ] // bug - array contains value of right
> main("03a", "2", 3, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '0h', '1', '1z' ] //fineThis can be fixed by updating function bigIntSubdivide(l, r, n, base) {
let divisor = n + 1n; //avoids situation where (delta * n) + l == r
while ((r - l) / divisor === 0n) {
r *= base;
l *= base;
}
let delta = (r - l) / divisor;
let ret = [];
let nNumber = Number(n);
{
let prev = l;
for (let i = 0; i < nNumber; i++) {
let next = prev + delta;
ret.push(next);
prev = next;
}
}
return ret;
}New outputs: > main("03a", "2", 1, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '1' ]
> main("03a", "2", 2, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '0h', '1' ]
> main("03a", "2", 3, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split(''))
[ '0X', '1', '1V' ] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt
Available in Chrome/Node now. In Firefox beta. WIP in Safari per https://wingolog.org/archives/2019/05/23/bigint-shipping-in-firefox
The text was updated successfully, but these errors were encountered: