Working with Rational numbers
Or how to write something when you just don’t know what to do :)
There are times. There are times in our lives when we don’t know what to say. When we think that we stopped in one place. Hell, like we not solving anything new. Actually nothing wrong with that. It is hard to invent something new and clever these days.
But rarely it can lead you to write maybe interesting, but still useless stuff. This is what about this article. About some strange choices in your life and weird but yet interesting decisions.
The year 2021, I was just an engineer in some company. And I received an offer from the other big company. I was really happy and accepted it. But due the covid the document processing took a while, so it was unknown, when I will start. Yet people said that July should be fine, we have some time.
Since I lived in Dubai and my contract came to the end, I decided to terminate everything, come back to my country and wait there. Without job. Only with earned money, that I didn’t want to spend, since I would need them later. Without knowing, when I will move in. With stuff left in Dubai in paid storage…
Strange decision right? Yet I made it. Similarly in java we have a float and double types. Those types aren’t new, and were created many many years ago. According to wiki, it was there since Fortran language.
The main point, is that Float/Doubles are clever rearrangement of bits, that were previously used for Int/Long. And this rearrangement gave an ability to work with divisions, square roots and other calculations, that involve not integer numbers. Yet it had its limits in precision. You can read more about how floating point numbers were borned in the book Code: The Hidden Language of Computer Hardware and Software.
When I read about all of that, I thought “why not to create” really Rational type, so we will be able to have numbers, like
18/396 which is
0.0(45) in decimal representation. Compare to it, float number will look like
Same as my decision. Wierd and strange. Same as this prologue. Useless. But interesting, how it will go :)
Simple an basic operations were easy to add:
As my decision this part was really simple. Simple and premature, as I faced eventually with understanding of few things. Things that I don’t know how to solve (mathematically and with java/kotlin):
- There will be a lot of repeating numbers.
100/200— all of them are in fact the same number
- Both denominator and numerator can be negative, which makes
1/(-2)the same number.
- For instance min float number is
1.4E-45, and my min rational number will be
4.7E-10. Max float number is
3.4E38whic my max rational number is just
2.1E9. So float has much bigger spread, than presented rational number
- In the same time my rational number is twice bigger than float. 8 bytes versus just 4 bytes
Now you understand, how useless this class is. Yet, it was still interesting to create it. So let’s continue.
As I said before there were different repeating numbers. For instance,
10000/20000 were the same number
0.5. So I wanted to have method, that would convert any rational number to its canonical form (minimal numerator and denominator with preserving the value).
To receive it, I needed to know the greatest common divisor of both numbers, and then divide them both by it.And here I discovered binary GCD.
If you will try to solve the GCD problem, the classical solution will be this one (it can be recursive or iterative, I presented recursive, since it’s more concise).
But I was interested to find more fast approach. And I found binary GCD algorithm. I will not dive into details of explanation and will just present the code, since I used it inside
Comparison with other GCD by benchmarks
Well, let’s check: is it really faster than recursive approach. I will also include iterative approach (let’s call it
loopGcd) to be more fair. You may ask, why you do this for kotlin or java, maybe it is better to check in more low level languages? Probably you right, but I was just curious :)
Let’s take a simple benchmark for different amount of pairs (numbers of which we will take a GCD). Also let’s test it for repeating the same calculation and using different numbers every time.
Here is a snippet of benchmark:
Now let’s see the result:
As you can see for small amount of numbers there is no real difference between recursive, loop and binary gcd. However on a big amount of numbers binary GCD is winning.
I would say that if you not using native code for building gcd algorithm, you can use any of them.
Now the time is to print our rational number. For instance for number
18/99 we want to print
0.(18), which means
To do this, we need to do the two main steps.
Split on an array of digits
First one, we need to build a decimal representation of our rational number. Let’s define
Decimal nested class:
It contains of:
- sign (
- array of digits (
- amount of digits after the dot, as decimal part (
- amount of digits inside bracets, repeating part (
To formulate the instance of such class, we need to do a good old school division:
This method can be basically several parts:
- In the first part we try to find, do we have the whole part of the number or not. If yes, then we split that whole part on array of digits. It not, then we add just 0
- In the second part we divide as in school. We take a dividend. If it less than divisor, we multiply it by ten until, it will be greater (in the same time we add zeroes to our digits array). After that we compute the whole part of division (it will be always a digit between 1 and 9) and check the remain. If remain is zero, we completed the division. If not, then repeat.
- The second step can be infinite in time in case of rational numbers like
1/3with infinite count of numbers in decimal part. So we keep all remaining in the hash table and check it on each step. If on some step we understand, that our remain already contains in the table, then we found repeating part of our decimal representation, and we completed the division.
Now the time to format our number, giving the information, provided by
What about big numbers
If we want to have a deal with really big numbers, using
denominator might be not enough. In that case would be nice to use
Well, we could just change everything to use such type, but why not to have a two types, one for small numbers and one for big (like
Basic: The Interface
Let’s make an interface first, that will generalize work with numbers. Later you will see, why such interface will be useful:
We have pretty much the same methods, as for our initial class (now it will be called
Now we have a decision:
- Either we want to keep two separate implementation repeating the all calculations but for different types (because there is no common interface for
BigIntegerin kotlin that unite them by math operations).
- Or we want to try to avoid this duplication
As I said, since the whole this solution is meaningless and just a mental experiments, let’s follow the second approach.
Actually all the operations are in idea the same. If you want to multiply two rational numbers, you multiply the numerators and denominators, regardlessly of their concrete type. If you want to convert rational to decimal representation, you just need to know how to divide numerator and denominator and how to convert them to array of digits. You don’t care if it
So we just need to abstract away from concrete types and think about numbers as some general type. To do that, let’s introduce the next interface:
So we have our custom number interface. Having it, we establish a typed protocol “we know and sure that all numbers can be added/subtracted and etc by their type”. For instance, all you can add integer to interger, or long to long, but not long to int. Pretty much similar to kotlin type system, hah?
Now we can have two implementation of numbers:
Now it is type to basically generalize everything (almost):
I said almost, because I didn’t include formulating of
Decimal number here, since it deserve the separate section. Instead we will build a computer, that can calculate decimal for some
Number<N> and will provide a different implementations for
BigInteger and for
Number actually can be anything, we don’t know in general what
ten means, that why they will be specified by children.
The implementation for
BigInteger looks pretty straightforward:
Int it is a bit more complicated. You see, then int can be overflowed, so this line:
var remain: N = numerator % denominator * ten
For instance if
numerator = 1000000000 and
denominator = Int.MAX_VALUE , then
numerator will be less than
denominator and the remain of division will be equal to
numerator. However multiplication on ten will give the value which is more than
Int.MAX_VALUE. To fix that,
remain should be the
LongNumber type not
To achieve that we will use Proxy pattern and a bit of hack.
So every time we want to
compute two int numbers, we convert them first to long, and then do calculations for long values.
We have two types of
Rational interface: for handling small numbers and big numbers.
Suppose now that we want to convert our rational number to canonic form each time, we finished our calculation. It will help us to keep numerator and denominator small enough if that’s possible.
But with what we have now, we need to remember to call
canonical method after each operation. Would be nice to automate it. And in the same time we don’t want to have two more types:
BigCanonizedRational. Suppose in the future we will have one more implementation of
Rational interface. We will have to remember to provide another canonized type for it, too. And here when Decorator Pattern shines.
We just wrap any
Rational number with decorator that invoke
canonical after each operation. We also use a trick with companion object to imitate
CanonizedRational constructor calling, but instead we call factory method
invoke that converts wrapped rational number to its canonical form.
As I said multiple times through the article, I’m not sure there is a real usage of what we have done. This post was more mind game “Let’s try to do this”.
Moreover it also showed how far we can go with generalization and overengineering in attempt to achieve DRY principle. And even if Rational numbers would be needed somewhere in prod. I’m not sure that you need to build whole this hierarchy for that. Maybe sometimes you can sacrifice a duplications a bit, in order to keep your structure clean and simple (according to KISS principle).
The balance matters in the end!
If you liked that article, don’t forget to support me by clapping. If you want to support me more, just subscribe to my blog and keep an eye on new articles. Also, if you have any questions, comment me, and let’s have a discussion. Happy coding!
Also, there are other articles, that can be interesting: