Climbing Out of the Hole – BKFloat
For the last several days I've been heads down coding this 'infinite' precision floating point number in Java for BKit - BKFloat. I learned a lot of really interesting things in the process. Now that I've dug myself out of that all-encompassing task, I can take a little time to talk about it.
When I started working on it I thought that the best way to implement the class was to have a long as the whole number part and another as the fractional part. Then, when I needed to do any math, it was pretty easy as I could take advantage of the long's ability to do the math. And this got me quite a ways to the end. But I started running into a lot of problems when I got to the point of really building the add() and subtract() methods because I was getting into coding based on the long and not a general 'infinite' precision floating point number.
For instance, with the long, I still had to deal with the fact that I did have an upper limit on the number of digits I could represent. Sure, it was big, but it wasn't as big as it might need to be. Some of my test cases had numbers in scientific notation and for those guys I had 5.5511232344325E-17 and the like which made it very hard to make sure that I had enough digits to express the non-zero elements as well as the proper magnitude of the number.
The final problem that snapped this design was the use of the sign on the fractional part. Imagine that you had two longs - one for the whole number part and another for the fraction with an implied decimal point in between them. If I had a number like -0.5 the whole number part would be 0 and the fractional part would be 5 - but where did the sign go? If you had -1.5, the whole number part would be -1 - there's the sign. So I had to 'pack' the sign on the fractional part if the whole number part were zero. This lead to a lot of code to make sure I had the right sign of the number for the operation. It was looking ugly and I just knew there was a better way.
So after about a day of that I backed off and thought that the better way had to include the resizing of the digit storage in order to make sure that the only limitation to the size of the floating point number was the capacity of the machine. I also had a feeling that by separating the digits I'd be able to implement the arithmetic operations a lot easier because I could code it like third-grade math. So I started off on that tack.
The next day was spent gutting the code of the long-based code in factor of byte[] storage for the digits. I spent a little more than half a day getting to basically the same point that took me the previous day. I had added a lot of little things like the ability to shift the number right or left as if multiplying (or dividing) by 10. This made a lot of things easier and in general the code was drastically simplified.
The things we learn in third-grade are really powerful. Coding carry and borrow on the add() method was interesting and a bit of amazement at what we all do so easily. It's really quite amazing. I've done the classic computer numerical manipulation with the XOR for multiplication and the full adder, but this is interesting in that it wasn't base 2 and yet it was exactly a digit at a time. Very interesting. I don't think I've ever written code like it.
Multiplication was interesting and fun at the same. Division was almost fun once I got into it. Of course, the division was the first one that might have a loss of precision due to the mature of the operation so I had to do a few interesting things there, but in the end it was working remarkably well. I don't think this is going to set any speed records, but the point is not speed but precision and accuracy. The test cases I used in the development pointed out that there were plenty of times where a simple double in Java is just not very good at representing values. This class is for those times when you have a handful of numbers that have to be added, etc. without any loss of precision. For those cases, speed is typically not as important as the precision. Good enough.
Now I'm back down into the hole to convert it to C++ for CKit. Shouldn't take too long... all the logic and method calls are already worked out.