In JavaScript rekenen met willekeurig grote gehele getallen: BigInt

JavaScript kent eigenlijk alleen 64-bit floatingpoint-­getallen. Slechts 53 bit staan voor integerberekeningen ter beschikking. Daardoor is het niet mogelijk met grotere gehele getallen te rekenen. Gelukkig is er voor moderne browsers het BigInt-project, waarmee je met willekeurig lange integers kunt rekenen.

Als je op zoek bent naar een plek om online wat te kunnen rekenen, heb je een probleem als je daarbij makkelijk het numerieke systeem wilt kunnen kiezen (binair, octaal, decimaal of hexadecimaal) zonder lastig tussen die modi te moeten wisselen. Bij geen enkel online rekenapparaat konden we variabelen gebruiken, die bij het uitproberen van formules heel handig kunnen zijn.

Dus leek het ons een goed idee er zelf een te maken. En dan het liefst een voor de browser, want dat maakt het makkelijker om deze zonder problemen op ieder platform te gebruiken. Zo gezegd, zo gedaan. Daar is de Arbitrary Precision Calculator uit voortgekomen.

De broncode daarvan kun je downloaden bij GitHub. Sla de bestanden eenvoudigweg op in een directory naar keuze van de root van je webserver, en dan kun je er meteen mee aan de slag. Deze rekenmachine heeft wiskundige en bit-operaties. Daarnaast zijn er nog enkele extra functies aan toegevoegd zoals GGD, KGV, min, max en worteltrekken.

Als je voor een browser programmeert, dan wordt je code uiteindelijk in de JavaScript-engine van de browser uitgevoerd. Getallen in JavaScript (van het type Number) zijn helaas altijd maar 64-bit floatingpoint-getallen, waarvan 53 bit beschikbaar zijn voor de mantisse – zeg maar het deel voor de komma. Java­Script werkt bij gehele getallen dan ook alleen met dat aantal bits.

Daarmee loopt het bereik aan mogelijke waarden van -2⁵³ + 1 (Number.MIN_SAFE_INTEGER) tot 2⁵³ – 1 (Number.MAX_SAFE_INTEGER). Zoiets als 64-bit integerberekeningen, die tegenwoordig heel normaal zijn, is daar dus niet mee mogelijk. Grote ID’s voor databaserecords, precieze tijdsaanduidingen: het kan niet. Het wordt nog erger als je integerberekeningen wilt doen met op bitniveau werkende operaties (a|0). Dan rekent JavaScript met 31-bit integers (inclusief voorteken).

De oplossing: rekenen met gehele getallen van willekeurige lengte. Dan kun je bijvoorbeeld boekhoudkundige problemen oplossen door euro’s niet meer als kommagetallen weer te geven, maar in centen als grote gehele getallen. Herken je het probleem niet? Typ dan in de JavaScript-console van je browser maar eens 5.10 + 10.20 === 15.30 in …

Voor het rekenen met willekeurig grote getallen zijn er wel bibliotheken ontwikkeld als JSBI, big.js, math.js, crunch.js en bin.js, maar door hun achterliggende principes werken die erg traag zodra een waarde een paar (honderd)duizenden cijfers lang wordt. Denk bijvoorbeeld maar eens aan het genereren van RSA-sleutels. Dat gaat sneller met het BigInt-object, dat Chrome sinds versie 67 en Opera sinds versie 54 ter beschikking stelt. In Firefox zit het vanaf versie 68. Safari, Internet Explorer en Edge kunnen daar nog niets mee.

Je kunt op allerlei manieren met BigInt werken. Om bijvoorbeeld aan de variabele a de BigInt-waarde 2 toe te kennen, schrijf je
let a = BigInt(2);
Let op: ook al gaat het hier om een object, je maakt het niet zoals gewoonlijk aan met new. Dat gaat met de BigInt-literals minder omslachtig. Je typt de getallen net als normaal in, maar voegt er een kleine n aan toe:
let b = 256n;
Met de BigInts in a en b kun je zoals normaal rekenen, bijvoorbeeld machtsverheffen:
let c = a ** b;
Dan bevat c een getal met 78 cijfers, dat we hier niet zullen afdrukken want je hebt de Arbitrary Precision Calculator nu immers toch bij de hand. Andere wiskundige operaties als +, –, *, / en % zijn ook mogelijk en voor operaties op bitniveau |, &, ^, << en >>, evenals de vergelijkingen <, >, <=, >=, ==, !=, ===, !==.

Ook van een string kun je een BigInt maken: door er 0b voor te zetten, interpreteert JavaScript de string als binair getal, en met 0x als hexadecimaal:
let largeDecimal = BigInt(“73405987340958730743098”);
let notSoLargeBinary = BigInt(“0b1110110101001011100001”);
let sixtyFourBitHex = BigInt(“0xfeacbeac12345678”);

Als je wilt achterhalen of een variabele een BigInt bevat, kun je de typecontrole gebruiken. Het volgende zal daarbij leiden tot true:
typeof 42n === “bigint”

Het door elkaar gebruiken van BigInt- en Number-­operaties is niet toegestaan:
23 + 42n
Dat leidt in dit geval niet tot 65, maar levert bij Chrome bijvoorbeeld de TypeError op ‘Cannot mix BigInt and other types, use explicit conversions’. Ook de functies uit het Math-object mag je niet op BigInt toepassen: Math.sqrt(144n) kan bijvoorbeeld niet.

Numbers en BigInts zijn echter wel type-onafhankelijk met elkaar te vergelijken:
42 == 42n
Dergelijke vergelijkingen leiden net zo lang tot true als de BigInt naar een gelijkwaardige Number te converteren is.

Het berekenen van 23 tot de macht 1.234.567 is met BigInt in acht seconden gedaan, het converteren van de bijna 1,7 miljoen cijfers duurde bij Chrome en Opera echter meer dan twee minuten. Hexidecimaal kan dat in een paar milliseconden.

Als een waarde tussen Number.MIN_SAFE_INTEGER en Number.MAX_SAFE_INTEGER ligt, ontstaat bij de conversie een geheel getal Number, in de andere gevallen een floatingpoint-getal dat de oorspronkelijke waarde zo goed mogelijk benadert. Te hoge of te lage getallen worden omgezet naar Infinity respectievelijk -Infinity.

Als je net als wij hier gedaan hebben van een BigInt een string wilt maken, kun je de bij Number bekende methode toString() gebruiken. Daarbij wordt als parameter de basis van het getalssysteem verwacht. Om de variabele aStr te vullen met de binaire weergave (dus met als grondtal 2), volstaat
let aStr = a.toString(2);

De titel van dit artikel suggereert dat BigInt met willekeurig veel posities kan rekenen. Maar klopt dat ook? In principe wel, maar … hoe meer cijfers een Big­Int-getal heeft, des te meer geheugen het in beslag neemt. Zo leidt 2**10000000 tot een decimaal getal met meer dan drie miljoen cijfers. Daar wordt dan een string van gemaakt die 3 MB geheugenruimte in beslag neemt. Voor een beetje moderne computer is dat natuurlijk peanuts. En eigenlijk is dat nog minder ook omdat BigInt intern met byte-arrays werkt. Alleen veel grotere waarden als 1234**1234**3 met meer dan 5,8 miljard cijfers leiden ook bij een krachtige computer tot een RangeError (BigInt too big).

Het berekenen van 2**10000000 is echter geen probleem: Chrome 75 heeft op een iMac met een 2,7 GHz Intel core-i5 slechts 1,4 seconden nodig om dat uit te rekenen. Als je toch nog zit te wachten op de grote ‘maar’, hier komt hij: het vervolgens weergeven van dat getal in een tekstveld duurt dan nog zo’n zeven minuten. Chrome heeft een groot deel van die tijd nodig om het resultaat met toString(10) om te zetten naar een decimaal getal. Maar dat is ook logisch: BigInt hoeft voor het converteren naar een binaire, octale of heximale weergave alleen wat bits te verschuiven en maskeren, maar voor een decimale weergave zijn in vergelijking lang durende modulo-delingen door 10 nodig. Opera 60 heeft hetzelfde probleem. Firefox heeft het berekenen van de formule grappig genoeg in zijn geheel geweigerd en brak af met RangeError en ‘BigInt is too large to allocate’.

Als je de Arbitrary Precision Calculator handig vindt, experimenteer dan eens wat met variabelen en gebruik die in een formule. De code is opensource, dus je kunt er zelf mee knutselen als je wilt.

(Oliver Lau en Noud van Kruysbergen, c’t magazine)