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 prologue
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.
We know those famous Java Puzzlers, when 2.00–1.10
gives you not 0.9
but 0.89999999
number. You can read more about representation convention and how discrete float numbers works here.
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 0.045454547
.
Same as my decision. Wierd and strange. Same as this prologue. Useless. But interesting, how it will go :)
Basic ops
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.
1/2
,2/4
,100/200
— all of them are in fact the same number0.5
. - Both denominator and numerator can be negative, which makes
(-1)/2
and1/(-2)
the same number. - For instance min float number is
1.4E-45
, and my min rational number will be4.7E-10
. Max float number is3.4E38
whic my max rational number is just2.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.
Canonical method
Aim
As I said before there were different repeating numbers. For instance, 1/2
, 10/20
, 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.
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 Rational
.
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.
Formatting
Now the time is to print our rational number. For instance for number 18/99
we want to print 0.(18)
, which means 0.1818181818...
.
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 (
signum
property,1
or-1
respectively) - array of digits (
digits
property) - amount of digits after the dot, as decimal part (
scale
property) - amount of digits inside bracets, repeating part (
repeat
property)
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/3
with 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.
Format
Now the time to format our number, giving the information, provided by Decimal
.
What about big numbers
If we want to have a deal with really big numbers, using Int
for numerator
and denominator
might be not enough. In that case would be nice to use BigInteger
.
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 Int
& BigInt
).
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 OldRational
)
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
Int
&BigInteger
in 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.
Number wrapper
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 Int
or BigInteger
type.
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):
Decimal Computer
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 Int
.
Since the Number
actually can be anything, we don’t know in general what zero
and ten
means, that why they will be specified by children.
The implementation for BigInteger
looks pretty straightforward:
With 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 IntNumber
.
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.
Canonized Rational
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: SmallCanonizedRational
& 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.
Afterwords
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: