Does Julia support hardware, which does not provide twos' complement integers?

In the function gcd in intfuncs.jl I saw, that the logic depends on the twos’ complement representation of integers. It would be important to avoid that, if Julia claimed to support the rare processor architectures not using twos’ complement.

Which would those be?

wiki.
I used to work on a CDC6000 in the ealy 1970s; am am not aware of modern machines.
Nevertheless a clear ‘NO’ would be helpfull.

The practical details would depend on LLVM, which (AFAIK) does not have any backends which are not 2-complement.

Your question is very hypothetical, and the same time touches on a lot of low-level details, so I don’t think you will get a clear yes or no. These issues are usually decided when they come up — everything is possible, it’s just that someone has to do the work. If anyone wants to use Julia on a 1-complement machine (do they still exist? your link has only historical examples), I guess they would have to port a lot of things, starting with LLVM.

3 Likes

Somewhere there is written that explicit “No”.

1 Like

Meaning “No” - Julia does not support anything different form twos’ complement.

1 Like

indeed

2 Likes

In this form, this statement is not very meaningful, because it is unclear what exactly you want to be “supported”.

Eg it would be very easy to implement a type of integer that represents negative numbers as one’s complement internally, or a one’s complement operation on unsigned integers. You could even define an integer type with a signed zero! It is just not very clear from your question why you need this, but if you do, you could code these things quite easily and put it in a package.

The question was more, if it is necessary to immunize the the Julia codebase for the case, that the standard bit integers are not using twos’ complement storage.
That is not the case, because of such hardware is not supported.

The relevant question is whether such hardware exists (in contemporary use). I am not sure about this, and the wiki you linked lists historical hardware.

A similar question could be asked about IEEE floating point: a lot of assumptions about it are baked into the code. Or hardware with nonstandard byte sizes. But as long as such hardware is not used in practice, “immunizing” against these things may not be a high priority exercise.

1 Like

Such defensive/portability measure could indeed be useful in some cases but there’s a continuous spectrum that goes from non-sense to absolutely necessary.

Whenever you write low level code, you must assume something about the hardware. And we are indeed talking about low level code here since otherwise basically everything can be simulated. 2s complement arithmetics can certainly be implemented on archs that natively support 1s complement and vise versa. It may not be as efficient but it should work.

Just because something “could” happen is never a good argument for anything. You always need to consider the probability, the cost and the benefit of it. There are a huge number of assumptions we make about OS, arch, uarch, endianess, bit representation of integer, floating point, pointers, memory model, thread model, etc. There is only so much assumption you can give up before you’ll literally not be able to write any code. The solution/defensive measure for each one have to be considered separately and ranges from making strong assumption, to writing multiple versions of code, to using a generic abstraction (i.e. weaker assumption) or even cross compiling (targetting accelerator for example). It is a valid point to bring up about supporting hardware with different integer representation but you just can’t ignore the current environment when talking about it. I’m sorry but your favorate CPU from the 70s might never be supported by julia and that’s at least partially because very few people miss them… (which doesn’t necessarily because it’s bad, but that it doesn’t fit in the world anymore…)

Now for this particular case, there’s basically no argument to be made about hardware. That’s not to say such hardware will never ever exist again but since basically nothing exist in a vacuum, unless some major discovery is made, no one is ever going to make a non-2’s complement comercial hardware in the foreseeable future. The investment to bring up such an architecture would be huge given how often such assumption is made in code these days. If for some reason it really happens, with all the dependencies fixed, fixing julia would be easy compared to the work done before us. (Note that this is basically the same argument that justify us making as much assumptions as our dependencies)

That is not to say one is encouraged to use bit operation on integers and especially not floating points. There are still different representation of numbers (arbitray length/precision, decimal numbers) so if something can be done with arithmetic operation just as efficient it is certainly preferred to do that since the code would be more generic and the algorithm would be more easily applied to a different type. However, for a specialization that is operating only on known type and if using bit operation simplify the code, then there’s no reason not to use it.

12 Likes

I am far from wanting to run julia on any old hardware. My primary concern is not “will Julia work, if it installed on non twos’ complement hardware?” but “is the current user well-adviced to rely on the twos’ complement interpretation of signed integers?”.

Both questions have been answered with “NO”. The second one is a little bit unsatisfactory. Alternative would be to guarantee to the Julia programmer this interpretation (as for example Java does). But that would maybe interfere with future progress.
The CDC6000 was never my favorite, by the way, but it was at my disposition to work on it.
It is always a good idea to work at an appropriate abstraction level. As an example, if you want ot find the multiplicity of 2 as a prime factor of an integer a, you could use trailing_zeros(a) (which is efficient and correct for two’s complement but not for negative ones’ complement). But that is in a way bit-based; preferrably define like twopowers(a) = trailing_zeros(a), which can be easily extended to adapt to other hardware.

I am still not sure why you are worried about this, but generally the best solution in these cases is to

  1. confine dependence on particular representation to a few key functions,

  2. encourage users use higher-level APIs (eg - for negating integers, instead of manipulating bits)

  3. make sure that the resulting code is still efficient (ideally 0 overhead)

Julia does pretty much this.

I don’t quite see the value of codifying the interpretation of bits in the standard unless there are multiple ones used in practice.

Note that it already does what you are asking for, and the documentation is pretty clear: you get

Number of zeros trailing the binary representation of x.

which is pretty unambiguous, and has nothing to do with that the actual bits are:

julia> trailing_zeros(-8)
3

julia> trailing_zeros(BigInt(-8))
3

Again, you are making a very generic argument here that doesn’t even mention anything in particular about the specific assumption you are talking about. Put it another way, are you going to say the same about not assuming 8-bit being the smallest addressable unit?

The core argument I’m making is that you have to consider exactly what you are defending against and come up with a cost-benefit analysis. That’s exactly why everyone else is asking you about contemporary hardware which is the point that you are ignoring (AFAICT).

Put in another way, you are advocating for us to not make an assumption and the argument is that it “maybe interfere with future progress”. However, the counter argument is that it’ll definitely interfere with current progress and how much do you want to pay for that?

If you want to propose a change using the argument of supporting possible future hardware, you’ll have to justify the additional complexity in the code (due to additional helper functions and the auditing effort[1]) against the likelyhood of this matters in the future. (If you are proposing a change based on other reason and it happens to make it easier to support 1s complement better that’s totally fine but is also unrelated to 1s complement)

And FWIW, I don’t think this is even the assumption we make about hardware that is the most likely to change. People are still proposing/making new CPU/computing architectures these days and AFAICT, none of them breaks this assumption while a bunch of them breaks many other assumptions.


[1] By definition this can’t be done automatically or you can just automatically port the code later, which is also similar to simulating 2s complement on 1s complement hardware.

5 Likes