2

This suggests just storing BigInts as an array:

// n = -123
var n = {
    sign: -1,
    digits: [3, 2, 1]
};

However, if you have "big ints", that array will get large:

var n = {
    sign: -1,
    digits: [ 1, 2, 3, ..., n_100 ]
};

A hundred digit array, that would be pretty slow if there were a lot.

Maybe there is a way to combine the numbers in some other way, so each number in the array goes until it maxes out at the 32-bit or 64-bit limit. That way you can pack it down tightly.

Wondering if there is a way to do that. It seems that's what is done here:

{
  type: 'BigInt',
  sign: 0,
  num_digits: 3,
  digits: [0x12…, 0x34…, 0x56…],
}
3
  • 1
    If whatever you are doing has 100 significant figures, using an extra 400 bytes of memory / datapoint is going to be the least of your worries. Commented Aug 24, 2018 at 20:55
  • So, let's note that the BigInt discussion from the V8 blog is pseudo code (though in JavaScript-like style), yet V8 is written in C++, and generates machine code, so has access to directly indexed arrays accessible in assembly (and C). So, discussions of efficiency and potential improvement should focus on what can be done in machine code (and not on the JavaScript pseudo code).
    – Erik Eidt
    Commented Aug 24, 2018 at 21:14
  • @whatsisname: not true - encryption algorithms very commonly work with very long numbers, and storing them in a compact way to reduce the memory footprint and improve cache behaviour can make a significant difference. Commented Aug 24, 2018 at 21:18

1 Answer 1

4

Bignums are usually stored as an array of digits. Just like smallnums are.

Smallnums are usually stored as a fixed-length arrays of "digits" in base 2. Bignums are usually stored as variable-length arrays of "digits" in base 18446744073709551616.

Arithmetic is exactly in the same way as you learned in school.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.