====== Rational Number Type ======

You may wish to read the [[#About]] section first.

Please discuss on the discussion page.


===== License =====

This research project is distributed under a **dual license**:

  * **Open Source License**: [[http://www.opensource.org/licenses/gpl-license.php|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 [[:wiki:user:tatewake|Terence J. Grant]], the copyright holder.


===== Download =====

Before downloading or using this product, make sure you __**understand and accept**__ the terms of the [[#license]].

  * The source to {{:projects:dispfrac-02232007.zip|dispfrac.cpp - February 23, 2007}}.
    * Due to the algorithm using a flat table for data, it only supports tables up to 14 x 14

===== Current Research =====



==== Duplication ====

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 <m>2/4</m>, even if you construct it yourself-- it will always appear as <m>1/2</m>. 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:

  * {{:projects:1_by_1.pdf|1 x 1 bit}} (theoretical)
  * {{:projects:2_by_2.pdf|2 x 2 bit}} (theoretical)
  * {{:projects:3_by_3.pdf|3 x 3 bit}} (actual - **Rational8**)
  * {{:projects:4_by_4.pdf|4 x 4 bit}} (possible)
  * {{:projects:5_by_5.pdf|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:
  * {{:projects:all_by_all.pdf|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.

==== Naive Format ====

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

<m>s b n_k n_{k-1} cdots n_1 n_0 d_k d_{k-1} cdots d_1 d_0</m>

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.

<m>(-1)^s ~ {sum{i=0}{k}{n_i 2^i}/sum{i=0}{k}{d_i 2^i}}</m>

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'' | <m>-7 ... +7</m> | <m>-{1/7} ... {1/7}</m> |
^ Rational16 | ''s_nnnnnnnddddddd'' | <m>-127 ... +127</m> | <m>-{1/127} ... {1/127}</m> |
^ Rational32 | ''s_nnnnnnnnnnnnnnnddddddddddddddd'' | <m>-32767 ... +32767</m> | <m>-{1/32767} ... {1/32767}</m> |

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 <m>a = 1/31</m>, but <m>1 / a</m> would wrap to +Inf since 31 overflows n's single binary digit.


==== Special Numbers ====

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 | <m>0/0</m> | ''00000000'' |
^ +Inf | <m>1/0</m> | ''00001000'' |
^ -Inf | <m>-{1/0}</m> | ''10001000'' |
^ Zero | <m>0/1</m> | ''00000001'' |
^ One | <m>1/1</m> | ''00001001'' |

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


==== Special Rounding Rules ====

Let <m>a in Rational8</m> = ''s_nnnddd''.

  - If an operation leaves n > 7, then take <m>lim{n right infty}{n/d} = {infty / d} approx infty</m>. Thus a = +Inf = ''00001000''.
  - If an operation leaves n < -7, then take <m>lim{n right -infty}{n/d} = -{infty / d} approx -infty</m>. Thus a = -Inf = ''10001000''.
  - If an operation leaves d > 7, then take <m>lim{d right infty}{n/d} = {n / infty} approx 0</m>. Thus a = Zero = ''00000001''.
  - If an operation leaves d < -7, then take <m>lim{d right -infty}{n/d} = -{n / infty} approx 0</m>. Thus a = Zero = ''00000001''.

===== About =====

Rational numbers of the form <m>a/b</m> 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.

==== Benefits ====
  * 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)! 8-O
    * 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).

==== Drawbacks and Questions ====
  * 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?