Large width Integers in Julia?

Question

Julia's Integer data types are defined in julia itself as bitstype, so can i define something like a Int256 and make julia work with Integer literals that are bigger than Int128 and use them as Int256?

Answer 1

Yes, you can. Probably the easiest way to do so, would be to make your own wrapper for the GMP library, using BigInt as a starting point (I've actually been working on a better, faster, and thread-safe wrapper for MPFR, to replace BigFloat, adding bigger fixed size floating point types and a mutable big float "container" type as well). You can also overwrite the definitions for the macros int128_str, uint128_str, and big_str, to handle the conversions of literals, so that won't even be a problem (except for the annoying warning when the package is loaded about replacing Base.@int128_str etc.

Answer 2

I will answer this question as asked: it is not possible without hacking at Julia itself. To be precise, the parser knows only about the built-in integer types. The Int128 support for literals is actually hardcoded in the parser:

(if (and (integer? n) (> n 9223372036854775807))
    `(macrocall @int128_str ,s)
    n)

So what you want with literals is not possible without changing the language itself. OK, so let's say we give up on literal support. Could we at least make a Int256 type and get it to work well? Of course, but it is not as easy as you might think.

The reason it is so tricky: internally, base Julia has BitInteger, BitUnsigned, and BitSigned types that implement most of the integer functionality. However, these types cannot be extended, because they are unions instead of abstract types. For example, we can see where and how & is implemented:

julia> @which 0x1 & 0x2
&{T<:Union{Int128,Int16,Int32,Int64,Int8,UInt128,UInt16,UInt32,UInt64,UInt8}}(x::T, y::T) at int.jl:141

As you can see, the implementation of & is for a specific set of types, and this set of types is not extensible. This is the case for a huge chunk of primitive functions on integers. Thus, we would have to reimplement much of that functionality, which is quite a bit of work! It is possible of course, but nobody wants to do that. On the other hand, if we had simply implemented Int256 support within Base itself, adding it to the appropriate unions, it would be much easier. But it is unlikely this will be added to Base, as in many applications, an arbitrary sized integer like BigInt will be more useful than a fixed but large integer like Int256.

In fact, there is an example of how complex reimplementing all integer behaviour is: BigInt. But wait, BigInt is in Base, right? While technically true, BigInt is actually defined in a well-isolated module named Base.GMP. We can see that it is not a member of any of the unions defined in base for the fixed-width integers. So we can actually follow the format of how BigInt is implemented to implement a new integer type. But I will leave it up to you whether you consider it worthwhile, as the implementation of BigInt is itself a large amount of code.

Answer 3

You can use BigInt for arbitrary-sized ints, but it gives a performance penalty. You can definitely speed it up if you used a fixed-size larger Int and defined fast rules, either via lookup-tables or something like DoubleDouble.jl for ints. You can use this by defining BitsTypes as its gone over in this video and define the appropriate operations on BitsTypes.

To make it fast you would want to try and use the operations built into the processor for integers to get more speed, and then somehow compensate for your extra size (this is what DoubleDouble.jl does it). You could always just define the operations bit by bit, but that most likely will not be as fast as plugging into the existing integer adding circuits on the processor. There is some mathematical/algorithmic work that would have to be done to make this work out correctly.

In theory (and judging by examples with floats: DoubleDouble, ArbFloats, ArbReals, various Unums, etc.), you can do all of this in Julia and release this as a packge. I just don't know of anyone who has done it already.

Answer 4

Well, there is the BigInt type which can be of arbitrary size. You can read about that in the docs here. I've found though that if you're doing much heavy computation with it, there will be a big performance penalty.

Apart from this you can certainly define your own type. I think that one of the challenges is that not all of the under-the-hood libraries in other languages like C that Julia works with support integers this big. I found, for instance, the following discussion on Julia's GitHub informative when I was looking into issues of the BigFloat type.