Laurent
I'm afraid you can't use `reinterpret` with a type such as `BigInt`.
I think what you want is an extension of `Nullable`: A nullable type
represents an object of a particular type that might or might not be
there; there's hope that this would be done efficiently, e.g. via an
additional bit. What you want is an efficient representation of a
discriminated union -- a type that can represent either of two types,
but without the overhead from boxing the types as is currently done in
a `Union`. Unfortunately, Julia currently doesn't provide this, but it
would make sense to have a feature request for this.
This might look like this:
```Julia
immutable FastInt
val::DiscriminatedUnion{Int, BigInt}
end
function (+)(a::FastInt, b::FastInt)
if typeindex(a.val) == 1 & typeindex(b.val) == 1
ov,res = add_with_overflow(a.val[1], b.val[1])
ov && return FastInt(BigInt(res))
return FastInt(res)
end
# TODO: handle mixed case
FastInt(a.val[2] + b.val[2])
end
```
This would be the same idea as yours, but the `reinterpret` occurs
within Julia, in a type-safe and type-stable manner, in a way such
that the compiler can optimize better.
You could try defining a type that contains two fields, both an `Int`
and a `BigInt` -- maybe `BigInt` will handle the case of a value that
is never used in a more efficient manner that doesn't require
allocating an object.
-erik
On Fri, Apr 8, 2016 at 2:07 AM, Laurent Bartholdi
<laurent.bartho...@gmail.com> wrote:
> 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
--
Erik Schnetter <schnet...@gmail.com>
http://www.perimeterinstitute.ca/personal/eschnetter/
