Naive BigInt implementation - how to improve?
I decided to start off my Mojo journey with some fibonacci. I wanted to handle arbitrary sized integers, so implemented a BigInt class.
besides the naive algorithm used - any suggestions for better syntax / use of Mojo types?
besides the naive algorithm used - any suggestions for better syntax / use of Mojo types?
from utils.vector import DynamicVector
from sys.info import sizeof
from math import max
struct BigInt:
var base_digits: Int
var data: DynamicVector[Int]
fn __init__(inout self, base_digits: Int, data: DynamicVector[Int]):
self.base_digits = base_digits
self.data = data
fn __init__(inout self, data: Int):
self.data = DynamicVector[Int](1)
self.data.push_back(data)
self.base_digits = 9
fn __str__(self) -> String:
var ret = String()
for i in range(self.data.size):
var val = String(self.data[self.data.size - i - 1])
if i > 0:
while len(val) < self.base_digits:
val = String("0") + val
ret += val
return ret
fn __copyinit__(inout self: Self, existing: Self):
self.base_digits = existing.base_digits
self.data = existing.data.deepcopy()
fn __add__(self, other: Self) -> Self:
let size = max(self.data.size, other.data.size)
var carry = 0
var new = self.data.deepcopy()
for i in range(size + 1):
if i == size and carry == 0:
break
if i == new.size:
new.push_back(0)
new[i] += carry + (other.data[i] if i < other.data.size else 0)
carry = 1 if new[i] >= (10 ** self.base_digits) else 0
if carry == 1:
new[i] -= (10 ** self.base_digits)
return BigInt(self.base_digits, new)
fn fib(n: Int) -> BigInt:
var a: BigInt = 0
var b: BigInt = 1
for _ in range(n):
let tmp = a + b
a = b
b = tmp
return a
fn main():
let r = fib(100_000)
print(r.__str__())from utils.vector import DynamicVector
from sys.info import sizeof
from math import max
struct BigInt:
var base_digits: Int
var data: DynamicVector[Int]
fn __init__(inout self, base_digits: Int, data: DynamicVector[Int]):
self.base_digits = base_digits
self.data = data
fn __init__(inout self, data: Int):
self.data = DynamicVector[Int](1)
self.data.push_back(data)
self.base_digits = 9
fn __str__(self) -> String:
var ret = String()
for i in range(self.data.size):
var val = String(self.data[self.data.size - i - 1])
if i > 0:
while len(val) < self.base_digits:
val = String("0") + val
ret += val
return ret
fn __copyinit__(inout self: Self, existing: Self):
self.base_digits = existing.base_digits
self.data = existing.data.deepcopy()
fn __add__(self, other: Self) -> Self:
let size = max(self.data.size, other.data.size)
var carry = 0
var new = self.data.deepcopy()
for i in range(size + 1):
if i == size and carry == 0:
break
if i == new.size:
new.push_back(0)
new[i] += carry + (other.data[i] if i < other.data.size else 0)
carry = 1 if new[i] >= (10 ** self.base_digits) else 0
if carry == 1:
new[i] -= (10 ** self.base_digits)
return BigInt(self.base_digits, new)
fn fib(n: Int) -> BigInt:
var a: BigInt = 0
var b: BigInt = 1
for _ in range(n):
let tmp = a + b
a = b
b = tmp
return a
fn main():
let r = fib(100_000)
print(r.__str__())
