CODEWITHSUNDEEP
arraysobjectintegerdata-modelingbigint
Lance Pollard
Lance Pollard

Reputation: 79278

How do BigIntegers work in detail at the fundamental level?

I saw Explain BigInt Like I'm Five, but I already understand what a BigInt is. I want to know how to make one though. I am trying to pick apart BigInt.js (the v8 bigint.cc is too large and I'm not familiar with C++).

For myself and perhaps others in the future, could one explain what the data model looks like for a BigInt that supports arbitrary sized integers? Basically, what is the object and its properties. I get that there are all the arithmetic functions implemented in unique ways for the BigInt, but I don't see what the kernel is. What is the essence of the structure of the BigInt? Perhaps this one will be slightly easier to grok.

Upvotes: 0

Views: 61

Answers (1)

Jörg W Mittag
Jörg W Mittag

Reputation: 369468

A BigInt works exactly like you learned about integers in school, except the "digits" are not based on 10 symbols, they are based on 4294967296 (or 18446744073709551616, or specifically for ECMAScript 9007199254740991).

The kernel of the data model is simply a list of "digits" that are themselves fixed-size integers and a sign bit (or alternatively, the first "digit" is itself signed). Everything else would be a performance optimization.

In pseudo-code, it would look something like this:

record BigInt
    sign: boolean
    digits: sequence[unsigned_integer]

or this:

record BigInt
    first_digit: signed_integer
    digits: sequence[unsigned_integer]

Again, if you write down an integer in base-10, you write it as a sequence of digits and a sign, i.e. writing the current year, you would write: 2, 0, 1, 9, signifying (from right-to-left)

  9 * 10^0 =    9
+ 1 * 10^1 =   10
+ 0 * 10^2 =  000
+ 2 * 10^3 = 2000
             ====
             2019

Or, maybe you would write 7, E, 3, signifying (from right-to-left)

  3_16 * 10_16^0
+ E_16 * 10_16^1
+ 7_16 * 10_16^2

which is the same as 

  3_16 * 16_10^0
+ E_16 * 16_10^1
+ 7_16 * 16_10^2

which is the same as 

   3_10 * 16_10^0 =    3_10
+ 14_10 * 16_10^1 =  224_10
+  7_10 * 16_10^2 = 1792_10
                    =======
                    2019_10

And a BigInt is represented in exactly the same way, except the base is (much) larger.

Upvotes: 1

Related Questions