To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.
Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.
I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits:
If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes.
This might work really well in practice idk, but I think it's not allowed by big O to pick a maximum supported size. Otherwise you could just make a lookup table. Your algorithm must be ready for anything.
To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.
Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits:
Here it is if we use the k largest primes that fit in 16-bit unsigned integers: If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes.This might work really well in practice idk, but I think it's not allowed by big O to pick a maximum supported size. Otherwise you could just make a lookup table. Your algorithm must be ready for anything.