BigInt - Arbitrary Precision (Unsigned) Integers

Hello all.

This API allows programmers to use unsigned integers of effectively any size (as long as you have enough memory to hold it). Most programmers won't need to use this (2 to the power of 32 is usually big enough), but if you're coding something involving cryptography (such as a hash function), then you may want to use this.

This API stores arbitrary precision integers (or "bigints") as tables, with each digit in the number taking up one entry in the table. For example, the number 1273 would be stored as:

{3,7,2,1}

In addition, instead of using the normal operators ("+", "-", ">=", etc.), you will have to use the included functions.

Keep in mind:

• Bigints are unsigned (cannot be negative). Operations where the result should be less than zero will have an undefined result.
• You cannot pass bigints to a function that accepts "normal" numbers. (i.e you cannot pass a bigint to math.sqrt().)
• This API supports basic arithmetic (add, sub, mul, div, mod, exp), comparisons, and bitwise operations.
• Bitwise NOT may not return the value you expect; it only inverts the values that correspond to the value itself. For example,

  
  bigInt.bnot({6,2,1})
  

  would return 130 instead of -127.

Most of the functions in this API have alternate names:

• Left and right shifts: blshift() and brshift() instead of bitwiseLeftShift() and bitwiseRightShift().
• sub, mul, div, mod, exp: subtract(), multiply(), divide(), modulo(), exponent() instead of sub(), mul(), div(), mod(), and exp().
• <the comparison functions>: cmp_<full name of comparision> (e.g "cmp_greater_than_or_equal_to", "cmp_greater_than_equal_to", and "cmp_gteq" are equivalent)
• bitwise operations (AND, OR, XOR, NOT): band(), bor(), bxor(), bnot() instead of bitwiseNOT(), bitwiseOR(), bitwiseAND(), and bitwiseXOR().

Get it here. (Pastebin code: th3Vrppb)

Oh this is awesome. I was doing a custom hash function and got above the limit with strings that were too short! Thanks A lot! :)/>

I believe you can use meta tables to be able to use the addition subtraction ect operator like this:
Setmetatable(bigintObject, {__add = addfunction}) or something like that I will look into it later

darkroom, on 15 April 2013 - 04:25 PM said:

I believe you can use meta tables to be able to use the addition subtraction ect operator like this:
Setmetatable(bigintObject, {__add = addfunction}) or something like that I will look into it later

Yeah, I know about that. I've even tried it once, but for some reason, it produced odd results. Perhaps I should try it again later, to see if was a fluke. I'll do that later, though.

This is kind of pointless. By storing each digit in a table, you're storing 64 * n bits(Lua uses doubles, IIRC), AND storing the data necessary for the Lua to be able to handle the table.

The only thing I can find this useful for, is dealing with giant numbers, but I would never use it as an unsigned integer. Nice work, though.

Mads, on 19 April 2013 - 09:37 PM said:

This is kind of pointless. By storing each digit in a table, you're storing 64 * n bits(Lua uses doubles, IIRC), AND storing the data necessary for the Lua to be able to handle the table.

The only thing I can find this useful for, is dealing with giant numbers, but I would never use it as an unsigned integer. Nice work, though.

Yeah, that's pretty much my only use for it. Actually coding the API itself was a nice challenge.

As a side note, the "original" (unreleased) version of the API held 4 digits per table entry, but made writing and debugging the division algorithm difficult, so I scrapped it and went with the easier method of storing each individual digit in a table entry.