Bignums

bignums.rb

# frozen_string_literal: true

class Number
  SIZE = 32

  attr_reader :values

  def initialize(values = [0])
    @values = values
  end

  def self.from(value)
    values = []

    while value > 0
      values << (value & (2 ** SIZE - 1))
      value >>= SIZE
    end

    new(values)
  end

  def +(value)
    values = [*self.values]

    carry = value
    index = 0

    while carry > 0
      carry, values[index] = ((values[index] || 0) + carry).divmod(2 ** SIZE)
      index += 1
    end

    Number.new(values)
  end

  def *(value)
    values = [*self.values]

    carry = 0
    index = 0

    while index < values.length
      carry, values[index] = ((values[index] || 0) * value + carry).divmod(2 ** SIZE)
      index += 1
    end

    values << carry if carry > 0
    Number.new(values)
  end

  def to_integer
    result = 0
    values.each_with_index do |value, index|
      result += (value << (index * SIZE))
    end
    result
  end
end

def assert_equal(exp, act)
  raise "Expected #{exp.inspect} but got #{act.inspect}" unless exp == act
end

assert_equal 1, Number.from(1).to_integer
assert_equal 2, Number.from(2).to_integer
assert_equal 2 ** 32, Number.from(2 ** 32).to_integer
assert_equal 2 ** 32 + 1, Number.from(2 ** 32 + 1).to_integer
assert_equal 2 ** 64, Number.from(2 ** 64).to_integer
assert_equal 2 ** 64 + 1, Number.from(2 ** 64 + 1).to_integer

assert_equal 2, (Number.from(1) + 1).to_integer
assert_equal 2 ** 32 + 1, (Number.from(2 ** 32) + 1).to_integer
assert_equal 2 ** 32 + 2, (Number.from(2 ** 32) + 2).to_integer
assert_equal 2 ** 64 + 1, (Number.from(2 ** 64) + 1).to_integer
assert_equal 2 ** 64 + 2, (Number.from(2 ** 64) + 2).to_integer

assert_equal 2, (Number.from(1) * 2).to_integer
assert_equal 2 ** 32, (Number.from(2 ** 32) * 1).to_integer
assert_equal 2 ** 32 * 2, (Number.from(2 ** 32) * 2).to_integer
assert_equal 2 ** 64, (Number.from(2 ** 64) * 1).to_integer
assert_equal 2 ** 64 * 2, (Number.from(2 ** 64) * 2).to_integer