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):

1. There will be a lot of repeating numbers. 1/2, 2/4, 100/200 — all of them are in fact the same number 0.5.
2. Both denominator and numerator can be negative, which makes (-1)/2 and 1/(-2) the same number.
3. For instance min float number is 1.4E-45, and my min rational number will be 4.7E-10. Max float number is 3.4E38 whic my max rational number is just 2.1E9. So float has much bigger spread, than presented rational number
4. 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 (signumproperty, 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:

1. 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
2. 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.
3. 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:

Delightful swapping views animation

Android View Collisions

Immutable lists in presenter