I recently started a module in my Computer Science course where we were each given an Arduino Uno to play around with. The version of C/C++ the Arduino Uno works with doesn’t have support for 64-bit operations out of the box. Ints are 16-bit, longs and floats are 32-bit, and doubles are only technically implemented. They exist, but are also 32 bits, making them identical to floats.
I wanted to see if I could implement a ‘64-bit long’ in C, without doing significant prior research. That was a bit of a mouthful, so I tenatively changed the name to “LongLong” before finding out partway through the project that this was, in fact, the name I needed: ‘long long’ was the real name for the data type. The way I’d like to describe the ‘long long’ is as two longs stapled together. A struct holds a left long and a right long. Functions take instances of this struct as inputs and perform operations on them, taking into account the fact that both ‘halves’ must behave like one number.
As an example of how this works, to perform a left shift, the left side of the number is first shifted the specified number of places. Then, a bitmask is used to make a record of the rightmost values of the right side of the number–the amount of values recorded is equal to the number of places the bits will be shifted. The recorded values are then right-shifted for the amount of bits that weren’t saved by the bitmask, putting them in the right position to be added to the left side of the number. Only after this has been done is the left shift applied to the right side of the number.
This process allows the bits on the left side of the right side of the number to be ‘carried into’ the left side of the number. The process is reversed for a right shift.
I used a lot of references while writing this code, so a lot of what I did wasn’t ‘reinvent subtraction’ but something more like ‘adjust an existing subtraction algorithm to work with this construct’. I’ve commented links to sources used above each function.
Addition and subtraction are implemented using the boolean operators I defined earlier. Multiplication and division are implemented using addition and subtraction using iterative definitions. This works but isn’t very efficient. If I make improvements to this, I’d like to learn about more efficient algorithms for multiplication and division and implement one of them.
Other changes I’d like to make include switching to using
typedef (which I didn’t know existed when I was writing the code) and allowing operations to happen between long longs and other numeric types. I’d also like to try implementing a signed 64-bit type as my current implementation can only do unsigned numbers.
Overall, I think this was an interesting and challenging project which allows room for further improvement within it. It is ‘reinventing the wheel’, but it was a fun wheel to reinvent and I learned a lot in the process.
If you’d like to have a look at the code, check it out on my github!