I like very much the idea of a discriminated union - that would help
enormously with some of the stuff I work on.
On Friday, April 8, 2016 at 8:47:59 AM UTC-4, Erik Schnetter wrote:
>
> 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
> <[email protected] <javascript:>> 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 <[email protected] <javascript:>>
> http://www.perimeterinstitute.ca/personal/eschnetter/
>
