Log In  



I needed a BigInteger implementation in Pico-8, so today I made one with the help of Sonnet 3.5.

The cart includes tests and test utility functions. Copy only the relevant code for you project.

It's not minified/compressed whatsoever, and the big integer functions come in at just under 700 tokens.

The cart is not very interesting in the browser, as it just prinths the results of an array of test cases.

The cart:

  1. Download using load #bigint-0
  2. Save using export bigint.p8
  3. Run using pico8 -x bigint.p8


Cart #bigint-0 | 2024-11-21 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
1


The cart code:

 
#include ../lib/bigint.lua

function testAdd(aStr, bStr, expected)
  local actual = bi_tostring(bi_add(bi_new(aStr), bi_new(bStr)))
  local success = actual == expected
  local successStr = success and "SUCCESS" or "FAILURE"
  printh(successStr .. " ADD: a=" .. aStr .. " b=" .. bStr .. " expected=" .. expected .. " actual=" .. actual)
  assert(success)
end

function testMultiply(aStr, bStr, expected)
  local actual = bi_tostring(bi_multiply(bi_new(aStr), bi_new(bStr)))
  local success = actual == expected
  local successStr = success and "SUCCESS" or "FAILURE"
  printh(successStr .. " MULTIPLY: a=" .. aStr .. " b=" .. bStr .. " expected=" .. expected .. " actual=" .. actual)
  assert(success)
end

function testDivide(aStr, bStr, expectedQuotient, expectedRemainder)
  local quotient, remainder = bi_divide(bi_new(aStr), bi_new(bStr))
  local actualQuotient, actualRemainder = bi_tostring(quotient), bi_tostring(remainder)
  local success = actualQuotient == expectedQuotient and actualRemainder == expectedRemainder
  local successStr = success and "SUCCESS" or "FAILURE"
  printh(successStr .. " DIVIDE: a=" .. aStr .. " b=" .. bStr .. " expectedQuotient=" .. expectedQuotient .. " expectedRemainder=" .. expectedRemainder .. " actualQuotient=" .. actualQuotient .. " actualRemainder=" .. actualRemainder)
  assert(success)
end

-- Test the implementation
function _init()
  testAdd("5", "100", "105")
  testAdd("1234", "4321", "5555")
  testAdd("123456789", "987654321", "1111111110")
  testAdd("-5", "100", "95")
  testAdd("-1234", "4321", "3087")
  testAdd("5", "-100", "-95")
  testAdd("1234", "-4321", "-3087")
  testAdd("-5", "-100", "-105")
  testAdd("-1234", "-4321", "-5555")
  testMultiply("5", "100", "500")
  testMultiply("1234", "4321", "5332114")
  testMultiply("123456789", "987654321", "121932631112635269")
  testMultiply("-5", "100", "-500")
  testMultiply("1234", "-4321", "-5332114")
  testMultiply("-5", "-100", "500")
  testMultiply("-1234", "-4321", "5332114")
  testMultiply(
    "3847562389476529837465928376459827364523049857203948523948570923847509823745",
    "5283746598237645982736459872364598272394857029384755928374509827345098723",
    "20329544686903723274743083705476880972770341168444807445475875405973626135762459661431321794505414721093912651978329966088871732326246329019354577635"
  )
  testDivide("123456789", "987654321", "0", "123456789")
  testDivide("987654321", "123456789", "8", "9")
  testDivide(
    "3847562389476529837465928376459827364523049857203948523948570923847509823745",
    "5283746598237645982736459872364598272394857029384755928374509827345098723",
    "728",
    "994865959523562033785589378399822219593939811846208091927769540277953401"
  )
end

The lua library:

 
-- Helper function to create a new BigInteger
function bi_new(n)
  local bi = { sign = 1, digits = {} }
  if type(n) == "number" then
    if n < 0 then
      bi.sign = -1
      n = -n
    end
    while n > 0 do
      add(bi.digits, n % 10)
      n = flr(n / 10)
    end
  elseif type(n) == "string" then
    if sub(n, 1, 1) == "-" then
      bi.sign = -1
      n = sub(n, 2)
    end
    for i = #n, 1, -1 do
      add(bi.digits, tonum(sub(n, i, i)))
    end
  end
  if #bi.digits == 0 then add(bi.digits, 0) end
  return bi
end

-- Helper function to remove leading zeros
function bi_trim_zeros(bi)
  while #bi.digits > 1 and bi.digits[#bi.digits] == 0 do
    deli(bi.digits, #bi.digits)
  end
  if #bi.digits == 1 and bi.digits[1] == 0 then
    bi.sign = 1
  end
end

-- Helper function to compare absolute values
function bi_abs_compare(a, b)
  if #a.digits > #b.digits then return 1 end
  if #a.digits < #b.digits then return -1 end
  for i = #a.digits, 1, -1 do
    if a.digits[i] > b.digits[i] then return 1 end
    if a.digits[i] < b.digits[i] then return -1 end
  end
  return 0
end

-- Addition operation
function bi_add(a, b)
  local result = bi_new(0)
  local carry = 0
  local i = 1
  local a_len, b_len = #a.digits, #b.digits
  local max_len = max(a_len, b_len)

  if a.sign == b.sign then
    -- Simple addition
    while i <= max_len or carry > 0 do
      local sum = carry
      if i <= a_len then sum += a.digits[i] end
      if i <= b_len then sum += b.digits[i] end
      carry = flr(sum / 10)
      result.digits[i] = sum % 10
      i += 1
    end
    result.sign = a.sign
  else
    -- Subtraction
    local larger, smaller
    if bi_abs_compare(a, b) >= 0 then
      larger, smaller = a, b
      result.sign = a.sign
    else
      larger, smaller = b, a
      result.sign = b.sign
    end

    while i <= max_len do
      local diff = (larger.digits[i] or 0) - (smaller.digits[i] or 0) - carry
      if diff < 0 then
        diff += 10
        carry = 1
      else
        carry = 0
      end
      result.digits[i] = diff
      i += 1
    end
  end

  bi_trim_zeros(result)
  return result
end

-- Improved multiplication operation
function bi_multiply(a, b)
  local result = bi_new(0)
  result.digits = {}

  for i = 1, #a.digits + #b.digits do
    result.digits[i] = 0
  end

  for i = 1, #a.digits do
    local carry = 0
    for j = 1, #b.digits do
      local index = i + j - 1
      local prod = result.digits[index] + a.digits[i] * b.digits[j] + carry
      result.digits[index] = prod % 10
      carry = flr(prod / 10)
    end
    if carry > 0 then
      result.digits[i + #b.digits] += carry
    end
  end

  result.sign = a.sign * b.sign
  bi_trim_zeros(result)
  return result
end

-- Improved division operation
function bi_divide(a, b)
  if #b.digits == 1 and b.digits[1] == 0 then
    error("division by zero")
  end

  -- Check if a < b
  if bi_abs_compare(a, b) < 0 then
    return bi_new(0), a
  end

  local quotient = bi_new(0)
  local remainder = bi_new(0)

  for i = #a.digits, 1, -1 do
    -- Shift remainder left by 1 digit and add current digit of a
    remainder = bi_multiply(remainder, bi_new(10))
    remainder = bi_add(remainder, bi_new(a.digits[i]))

    -- Find the largest digit q such that b * q <= remainder
    local q = 0
    while bi_abs_compare(bi_multiply(b, bi_new(q + 1)), remainder) <= 0 do
      q += 1
    end

    -- Subtract b * q from remainder
    remainder = bi_add(remainder, bi_multiply(b, bi_new(-q)))

    -- Add q to the quotient
    quotient = bi_add(bi_multiply(quotient, bi_new(10)), bi_new(q))
  end

  quotient.sign = a.sign * b.sign
  remainder.sign = a.sign
  bi_trim_zeros(quotient)
  bi_trim_zeros(remainder)
  return quotient, remainder
end

-- Helper function to convert BigInteger to string
function bi_tostring(bi)
  local str = ""
  for i = #bi.digits, 1, -1 do
    str = str .. bi.digits[i]
  end
  if bi.sign < 0 then str = "-" .. str end
  return str
end

The cart outputs:

 
SUCCESS ADD: a=5 b=100 expected=105 actual=105
SUCCESS ADD: a=1234 b=4321 expected=5555 actual=5555
SUCCESS ADD: a=123456789 b=987654321 expected=1111111110 actual=1111111110
SUCCESS ADD: a=-5 b=100 expected=95 actual=95
SUCCESS ADD: a=-1234 b=4321 expected=3087 actual=3087
SUCCESS ADD: a=5 b=-100 expected=-95 actual=-95
SUCCESS ADD: a=1234 b=-4321 expected=-3087 actual=-3087
SUCCESS ADD: a=-5 b=-100 expected=-105 actual=-105
SUCCESS ADD: a=-1234 b=-4321 expected=-5555 actual=-5555
SUCCESS MULTIPLY: a=5 b=100 expected=500 actual=500
SUCCESS MULTIPLY: a=1234 b=4321 expected=5332114 actual=5332114
SUCCESS MULTIPLY: a=123456789 b=987654321 expected=121932631112635269 actual=121932631112635269
SUCCESS MULTIPLY: a=-5 b=100 expected=-500 actual=-500
SUCCESS MULTIPLY: a=1234 b=-4321 expected=-5332114 actual=-5332114
SUCCESS MULTIPLY: a=-5 b=-100 expected=500 actual=500
SUCCESS MULTIPLY: a=-1234 b=-4321 expected=5332114 actual=5332114
SUCCESS MULTIPLY: a=3847562389476529837465928376459827364523049857203948523948570923847509823745 b=5283746598237645982736459872364598272394857029384755928374509827345098723 expected=20329544686903723274743083705476880972770341168444807445475875405973626135762459661431321794505414721093912651978329966088871732326246329019354577635 actual=20329544686903723274743083705476880972770341168444807445475875405973626135762459661431321794505414721093912651978329966088871732326246329019354577635
SUCCESS DIVIDE: a=123456789 b=987654321 expectedQuotient=0 expectedRemainder=123456789 actualQuotient=0 actualRemainder=123456789
SUCCESS DIVIDE: a=987654321 b=123456789 expectedQuotient=8 expectedRemainder=9 actualQuotient=8 actualRemainder=9
SUCCESS DIVIDE: a=3847562389476529837465928376459827364523049857203948523948570923847509823745 b=5283746598237645982736459872364598272394857029384755928374509827345098723 expectedQuotient=728 expectedRemainder=994865959523562033785589378399822219593939811846208091927769540277953401 actualQuotient=728 actualRemainder=994865959523562033785589378399822219593939811846208091927769540277953401

If you've got suggestions, improvements, bugs, or whatever else, please let me know.

This is also my first post on BBS, so there's probably also something I could do better in regards to that.

Thanks for reading, have fun!

1
1

Implementing big integers is how I familiarized myself with metatables and metamethods.
You could start with __add and __mul and __div, but nothing stops you from going overboard as practice :
__unm , __mod , __pow , __band , __bor , __bxor , __bor , __shl, __shr, __eq, __lt and __le
all make sense for big integers.
__idiv is redundant with __div since we are dealing with integers.
Speaking about integer division, you could have used it in your code :
flr(n/10) can be written as n \ 10

For pico-8 games, my preference goes to using string numbers for big numbers, and have a small function for addition and multiplication. Haven't needed big divisions yet, but I now know where to look, should the need arise.



[Please log in to post a comment]