Rational Number Type

You may wish to read the About section first.

Please discuss on the discussion page.

This research project is distributed under a dual license:

• Open Source License: GNU GPL v2, which states, among other things, that use of Rational Number Type (and anything below) requires that your project's source must definitely be available for download.

• Commercial License: If you do not want to release the source code for your application, you may purchase a license from Terence J. Grant, the copyright holder.

Before downloading or using this product, make sure you understand and accept the terms of the license.

• The source to dispfrac.cpp - February 23, 2007.
  • Due to the algorithm using a flat table for data, it only supports tables up to 14 x 14

Rational numbers are reduced before they are written to their final format.

So when reducing rationals, it becomes apparent that certain rational numbers are never truly represented as a bit mask. For example, you will never see , even if you construct it yourself– it will always appear as . This is true for any rational– you will never see two equal fractions with unequal formats.

This raises some interesting questions… How many duplicates will you get? How many originals get duplicated? How many unique representations for rationals do we have? It all depends on the number of bits used (even just theoretical), and the results are surprising.

Overall, we have a rough estimate of 40% duplicates on average, meaning we're only using 60% of all bit masks available to us. (Even more available if we're able to utilize the unused bit.)

I've created some tables, available currently in PDF format, demonstrating this– note that they only represent the positive side:

• 1 x 1 bit (theoretical)
• 2 x 2 bit (theoretical)
• 3 x 3 bit (actual - Rational8)
• 4 x 4 bit (possible)
• 5 x 5 bit (theoretical)

The legend is simple, no markup means unique– no duplicates, [THIS] means original but will be duplicated, and (THIS) means this entry is a duplicate and not really represented, it is a gap in the table.

Bigger tables than 5 x 5 won't render in DokuWiki, unfortunately. At this point, once a pattern is found for 1 x 1 through 5 x 5, it's very likely that we're only interested in the statistics to verify our calculations are correct for the higher tables. We just need to prove this via mathematical induction.

So here are some statistics for almost everything:

• 1 x 1 bit to 14 x 14 bit

The program I've written to create these tables is dispfrac, available above; it needs to be modified some to be able to map 15 x 15 and above. This may or may not be trivial though.

The question becomes then, how do we utilize the gaps? Glad you asked! We must find a way to enumerate the unique and original rational numbers in the n x n table, and then we extend the table by the a number of entries equal to the number of duplicates.

There are a few formats, though in general the standard, naive format is:

Where s is the signed bit, b is the unused bit, n are numerator bits, d are denominator bits.

Calculating the numerical value of the rational number from the standard, naive format is fairly straight forward.

Some standard naive formats are listed below. They are all balanced, meaning the number of bits for the numerator is equal to the number of bits for the denominator and each number can have its reciprocal taken.

Name	Format	Range	Granularity
Rational8	s_nnnddd
Rational16	s_nnnnnnnddddddd
Rational32	s_nnnnnnnnnnnnnnnddddddddddddddd

There is also a possibility for a free rational, which is a user specified format that is unbalanced. This implies that for any given free rational, you are not guaranteed the ability to take a reciprocal and get a valid result.

For instance, for s_nddddd, Let a = 00111111; thus , but would wrap to +Inf since 31 overflows n's single binary digit.

Listed below are currently some special numbers that you'll often deal with when using a standard naive rational number format.

Number	Rational representation	Bit Format (in Rational8)
NaN		00000000
+Inf		00001000
-Inf		10001000
Zero		00000001
One		00001001

Note that One = 00001001 00000001 = Zero 00000000 = NaN. This may lead to problems when debugging, if you're not careful.

Let = s_nnnddd.

1. If an operation leaves n > 7, then take . Thus a = +Inf = 00001000.
2. If an operation leaves n < -7, then take . Thus a = -Inf = 10001000.
3. If an operation leaves d > 7, then take . Thus a = Zero = 00000001.
4. If an operation leaves d < -7, then take . Thus a = Zero = 00000001.

Rational numbers of the form are not new. Integer division is not new. Floating point division resembling rational number division is not new. To implement a type for this seems unnecessary at first glance; however the idea of delaying division operations in computing is an interesting one that cannot be ignored.

I was first introduced to this concept in the form of a Java class a few years ago. The implementation was fairly rough– two signed integers for numerator and denominator. Due to it being Java the interface was somewhat clumsy, feeling like a class when it should feel more like a primitive type. Luckily we're able to fix this deficiency via C++'s operator overloading. But then if you look at it carefully, even though there are benefits, there are some possible problems.

• Possibly cheaper alternative for floating point
• Possibly cheaper alternative for fixed point
• Exact granularity not achievable in floating nor fixed point!
• Reduces all division operations (in terms of division) from O(n) to O(1)!
  • More accurate calculations, faster!
• Intuitive NaN, +/-Inf without special bit masks.
• Can implement “free rational”(unbalanced numerator/denominator bits) but is this worth it?
• Overflow easily maps to +/-Inf.
• Div by zero maps to NaN in O(1).

• Limited range.
• Possible numerical instability?
• Reduce operation is non-trivial.
• Extra bit since there's only one sign bit:
  • Uneven bit distribution implies impossibility to reciprocate in general.
  • Unused bit implies less storage (this is the better alternative.)
  • Two sign bits don't make sense.
• “Free rational” implies impossibility to reciprocate when unbalanced.
• Roughly only 60% of bit combinations are ever used on average (due to reduction.)
• Non-trivial conversion from float, fixed to rational.
• Conversion from float, fixed might go to +/-Inf
• Rounding rules necessary? Might give strange/incorrect results?