Arithmetic using binary numbers

I have huge matrices each entry of which is a 2-bit binary number. If I were to load them and convert to any of the Floats precisions, the memory required to load will be at least half a terabyte. Can Julia do arithmetic on (2-bit) binary numbers?

Basically yes. You can always implement this yourself using bitfield operations, or use e.g. GaloisFields.jl (though you still may need to load them from your array yourself — the smallest type that Julia can store in an array is UInt8, 8 bits, but you can think of this as a packed representation of 4 2-bit numbers that you can extract using bit operations).

There is no “built-in” array of 2-bit numbers in Julia, but that’s fine — user-written code for this can be just as efficient as anything “built-in” could be.

What operations do you want to perform on your matrices?

1 Like

the smallest type that Julia can store in an array is UInt8

Unless you count BitArray

1 Like

I’m looking to do linear algebra like matrix vector product, solving a linear system, matrix decomposition/factorization operations (also basic arithmetic of course)

Assuming you can pack your initial values into two bits and provide suitable methods for how you represent them, you’re likely to generate values that are no longer two-bit numbers. Unless your precision requirements are extremely low (so low as to be unuseful), you’ll need to store those results in much larger sized numbers.

That is certainly true. But then perhaps I’m wondering if I can vary the number of bits to be used for variables arbitrarily

There’s Integers and Floating-Point Numbers · The Julia Language, but that is used to get more precision, not less.

I doubt variable precision will help you — you will quickly need the full precision required for your problem (which depends on the condition number of your matrix).

(When you originally posted, I thought you meant some kind of finite-field arithmetic, but it sounds like you are doing ordinary real arithmetic, in which case you generally need floating-point numbers with decent precision for the results and intermediate values even if the input matrix entries can be represented with 2 bits.)

Maybe there is some other structure you can exploit. For example, if your huge matrix is mostly zeros (sparse), then you can use sparse-matrix methods.