Arithmetic using binary numbers

Specific Domains Numerics
1

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?

2

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
3

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

Unless you count BitArray

1 Like
4

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

5

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.

1 Like
6

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

7

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

8

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.