fib(10**62) works, fib(10**63) not

[Hermann-SW]

README.md fib demo on x86_64 Ubuntu.

log2(10*62) is 205, log2(10*63) is 209. Python number type has arbitrary precision, does codon restrict that? If so, what are the limits?

P.S: My interest comes from processing up to 617-digit or 2048-bit numbers: https://github.com/Hermann-SW/RSA_numbers_factored

[arshajii]

Hi @Hermann-SW -- Codon's int is 64-bit, which explains what you're seeing. However Codon has support for larger integers via the Int[N] and UInt[N] types; here's an example computing fib on a 2048-bit unsigned int:

I = UInt[2048]

@extend
class UInt:
    # full str support for bits > 64
    # will be added to stdlib in later release
    def __str__(self) -> str:
        self_cp = self
        int_str = ''
        while self_cp:
            remainder = 0
            quotient = UInt[N](0)
            # Euclidean division
            for bit_idx in range(N - 1, -1, -1):
                mask = int((self_cp & (UInt[N](1) << UInt[N](bit_idx))) != UInt[N](0))
                remainder = (remainder << 1) + mask
                if remainder >= 10:
                    quotient = (quotient << UInt[N](1)) + UInt[N](1)
                    remainder -= 10
                else: quotient = quotient << UInt[N](1)
            int_str = str(remainder) + int_str
            self_cp = quotient
        return int_str if int_str else '0'

def fib(n):
    a, b = I(1), I(1)
    for i in range(n):
        a, b = b, a + b
    return a

print(fib(100))  # 573147844013817084101

[Hermann-SW]

Thanks, that is impressive. But a minus in just taking Python code as is and use with codon unchanged.

For the repo I pointed to in initial issue text, that would mean I would have to rewrite completely. In addition, I would need to use at least 4096bit numbers and look whether that is sufficient, for intermediate results like in "y = x**2 mod n".

Are there any plans for being able to support Python arbitrary precision numbers unchanged in codon?

Whaat about esential libaries like sympy for number theory?