Skip to content

Instantly share code, notes, and snippets.

@kddnewton
Created December 15, 2023 21:39
Show Gist options
  • Save kddnewton/37995b99d46cc7221a359f6bb14a94e5 to your computer and use it in GitHub Desktop.
Save kddnewton/37995b99d46cc7221a359f6bb14a94e5 to your computer and use it in GitHub Desktop.
Bignums
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment