Dear all,
How hard would it be to code arbitrary-precision integers in Julia with at
worst 2x performance loss over native Ints?
This is what I have in mind: have a bitstype structure, say 64 bits, which
is either the address of a BigInt (if even), or an Int64 (if odd). Addition
would be something like:
function +(a::FastInt,b::FastInt)
if a&b&1
(result,obit) = @llvm.sadd.with.overflow.i64(a,b&~1)
obit ? reinterpret(FastInt,BigInt(a>>1)+(b>>1)) : result
elseif a&1
reinterpret(FastInt,(a>>1) + reinterpret(BigInt,b))
elseif b&1
reinterpret(FastInt,reinterpret(BigInt,a) + b>>1)
else
reinterpret(FastInt,reinterpret(BigInt,a) + reinterpret(BigInt,b))
end
end
(code not meant to be run, just a skeleton)
This would be very useful in the development of computer algebra systems,
in which BigInts are too slow and eat up too much memory, but one is ready
to pay a small price for guard against arithmetic overflows.
If this is too complicated, then perhaps at least a type of integers that
would raise an error in case of over/underflows? Those could be caught in
throw/catch enclosures, so the user could restart the operation with
BigInts.
TIA, Laurent
