View source for Rational and VFP Numbers

===Introduction===

<p><b>Rational numbers</b> complement the 64-bit integer datatype to provide infinite precision (or <apll>WS FULL</apll>) at the cost of some performance.  Similarly, <b>Variable-precision Floating Point</b> (VFP) numbers complement the 64-bit floating point datatype to provide more precision (as much as the user cares to specify) again with some cost in performance.</p>

<p>There is no separate datatype for infinite precision Integers.  Instead, they are represented as a special case of rational numbers.  In the discussion below, the phrase <b>rational integer</b> means a rational number whose denominator is one.</p>

<p class="note">Throughout this discussion the similarity between integer and rational numbers as well as floating point and VFP numbers will become apparent.</p>

===Rationale===

<p>Simply put:  precision.  If the 53 bits of precision in the floating point result of, say, <apll>2÷3</apll> is not enough, you now have two more choices:  one as an exact number, and one as a decimal number with as much precision as you care to specify.</p>

<p>For example,</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕PP←60 ⋄ ⎕FPC←512<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2÷3x<br />
2r3<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2÷3v<br />
0.666666666666666666666666666666666666666666666666666666666667<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2*200<br />
1.6069380442589903E60<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2*200x<br />
1606938044258990275541962092341162602522202993782792835301376<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;○1<br />
3.141592653589793<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;○1v<br />
3.14159265358979323846264338327950288419716939937510582097494</apll>

===Constants===

<p>Rational constants may be entered as follows:</p>

* <apll>123x</apll> for the constant <apll>123</apll> (the suffix <apll>x</apll> is but a shorthand for <apll>r1</apll>)
* <apll>123r4567</apll> for the constant <apll>123÷4567</apll>

<p>VFP constants may be entered as follows:</p>

* <apll>123v</apll> for the constant <apll>123</apll>
* <apll>123v4567</apll> for the constant <apll>123.4567</apll>
* <apll>123v4567e3</apll> for the constant <apll>123.4567e3</apll>

<p>The above formats for constants (except for the suffix <apll>x</apll>) may be used in other constants such as <apll>1r4p2</apll> to generate a shorter and more accurate value for <apll>π<sup>2</sup>/4</apll> than, say, <apll>((○1)*2)÷4</apll>.</p>

===Precision===

<p>Rational numbers have <b>infinite precision</b>.  They are stored with a separate numerator and denominator, both of which are exact numbers in the sense that their size (and hence precision) grows limited only by the available workspace.</p>

<p>VFP numbers have <b>user-controlled variable precision</b>, and each number may have a different precision.  The default precision at startup is controlled by the value of the system variable <apll>⎕FPC</apll>.  The system default of this value is <apll>128</apll> in units of bits of precision of the mantissa (the digits) of the number, not counting the exponent (which is of fixed size).  The current precision may be changed as needed by assigning a new value to the system variable.  All newly created VFP numbers will have the new precision – the precision of VFP numbers already present in the workspace does not change.</p>

<p>Generally, precision is set once for a particular application and unchanged thereafter.  Although not recommended, it is possible to mix VFP numbers of different precisions in a single array – presumably you <b>really</b> know what you are doing.  The system function <apll>⎕DR</apll> may be used to display an array's precision(s).</p>

===Datatype Propagation===

<p>Generally, the datatype of constants propagates through a calculation. That is, if you start with a rational number and don't calculate with irrational or transcendental functions, you'll end up with a rational result, and if you start with a VFP number, you'll end up with a VFP result.</p>

<p>An example from the programming problems site [http://projecteuler.net/ ProjectEuler.net] illustrates this point.  [http://projecteuler.net/problem=48 Problem #48] asks what are the low-order ten digits of the sum of the first thousand instances of N<sup>N</sup>?</p>

<p>The obvious expression <apll>¯10↑⍕+/N*N←⍳1000</apll> at first sight seems to solve the problem until you realize that it quickly runs afoul of the limited precision of 64-bit integer and floating point numbers.  Clearly, this is a problem for the infinite precision of rational integers.</p>

<p>As <apll>⍳1000</apll> generates the first thousand integers as an integer datatype (actually an Arithmetic Progression Array), <apll>⍳1000x</apll> generates the same values as rational integers.  Next, <apll>N*N←⍳1000x</apll> generates the first thousand instances of N<sup>N</sup> as exact rational integers, and unlike its integer counterpart, there is no overflow to floating point.  Then, <apll>+/N*N←⍳1000x</apll> sums them into a single 3001-digit rational integer, and finally <apll>¯10↑⍕+/N*N←⍳1000x</apll> converts the large integer to characters and extracts the low-order ten digits &mdash; <apll>9110846700</apll> &mdash; all in a small number of milliseconds.</p>

<p>Note how we started with an obvious expression that failed because of its limited precision, and made a single change to suffix the constant <apll>1000</apll> with an <apll>x</apll> to convert it to a rational integer which then propagates through the calculation with infinite precision to yield the correct result.</p>

===Display===

<p>Rational integers are displayed as an integer with no special adornment; rational non-integers are displayed as a numerator and denominator separated by an <apll>r</apll> as in <apll>34r9</apll>.  As with the integer datatype, the numerator and denominator of a rational number are displayed exactly, unaffected by <apll>⎕PP</apll>.</p>
<br />
<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;!40<br />
8.159152832478977E47<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;!40x<br />
815915283247897734345611269596115894272000000000<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+\÷⍳10x<br />
1 3r2 11r6 25r12 137r60 49r20 363r140 761r280 7129r2520 7381r2520<br />
</apll>

<p>VFP numbers are displayed as decimal numbers to the precision inherent in the number or <apll>⎕PP</apll>, whichever is smaller, just as floating point numbers are displayed.  For example,</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕PP←100<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕FPC←64<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;○1<br />
3.141592653589793<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;○1x<br />
3.14159265358979323851<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕FPC←128<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;○1x<br />
3.141592653589793238462643383279502884195</apll><br />

<p>where both of the above displays were limited by the precision of the number, not <apll>⎕PP</apll>.</p>

<p>However, the first of the following displays <b>is</b> limited by <apll>⎕PP</apll>, and the second one by the explicit <apll>20</apll> in the format function:</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕FPC←128<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕PP←20<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;!40v<br />
81591528324789773435E28<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;20⍕!40v<br />
&nbsp;81591528324789773435E28<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;⎕PP←80<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;!40v<br />
815915283247897734345611269596115894272000000000<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;39⍕!40v<br />
&nbsp;815915283247897734345611269596115894272000000000</apll><br />

<p class="note">In other words, if a VFP integer appears in E-notation, it means that either <apll>⎕PP</apll> or an explicit display precision to the format function is too small to show all of its significant digits.</p>

===Formatted Display===

<p>The system function <apll>⎕FMT</apll> has been enhanced to allow formatting of rational numbers via the (new) <apll>R</apll>-format specifier.  For example,</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'R4.2' ⎕FMT ∘.÷⍨⍳6x<br />
1 &nbsp;&nbsp;1r2 1r3 1r4 1r5 1r6 <br />
2 &nbsp;&nbsp;1 &nbsp;&nbsp;2r3 1r2 2r5 1r3 <br />
3 &nbsp;&nbsp;3r2 1 &nbsp;&nbsp;3r4 3r5 1r2 <br />
4 &nbsp;&nbsp;2 &nbsp;&nbsp;4r3 1 &nbsp;&nbsp;4r5 2r3 <br />
5 &nbsp;&nbsp;5r2 5r3 5r4 1 &nbsp;&nbsp;5r6 <br />
6 &nbsp;&nbsp;3 &nbsp;&nbsp;2 &nbsp;&nbsp;3r2 6r5 1  </apll>

<p>Moreover, the Symbol Substitution (<apll>S&lt;…&gt;</apll>) feature of <apll>⎕FMT</apll> allows you to substitute a different symbol for the default <apll>r</apll> used to separate the numerator and denominator of a rational number, as in</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'S&lt;r/&gt;R4.2' ⎕FMT ∘.÷⍨⍳6x<br />
1 &nbsp;&nbsp;1/2 1/3 1/4 1/5 1/6 <br />
2 &nbsp;&nbsp;1 &nbsp;&nbsp;2/3 1/2 2/5 1/3 <br />
3 &nbsp;&nbsp;3/2 1 &nbsp;&nbsp;3/4 3/5 1/2 <br />
4 &nbsp;&nbsp;2 &nbsp;&nbsp;4/3 1 &nbsp;&nbsp;4/5 2/3 <br />
5 &nbsp;&nbsp;5/2 5/3 5/4 1 &nbsp;&nbsp;5/6 <br />
6 &nbsp;&nbsp;3 &nbsp;&nbsp;2 &nbsp;&nbsp;3/2 6/5 1  </apll>

===Datatype Promotion===

<p>For the most part, rational numbers beget rational numbers and VFP numbers beget VFP numbers.  However, when irrational, transcendental, and certain other functions are used, rational numbers beget VFP numbers.  For example,</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*1<br />
2.718281828459045<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*1x<br />
2.718281828459045235360287471352662497759</apll><br />

<p>where the datatype of the two results are floating point and VFP, respectively.  That is, in a manner similar to how some primitive functions with integer arguments may return floating point results, when a rational number is used as an argument to a primitive function that can't return a result with infinite precision, it returns a VFP number.</p>

<p class="note">The reason irrational, transcendental, and certain other functions on rational numbers don't return rational numbers is that, by definition, the result of such a function is, in general, not representable as a rational number; instead, VFP numbers are better suited to represent irrational results where the end user may control exactly how much precision is desired in an obviously inexact number.</p>

<p>Two special functions are the prime decomposition (<apll>πR</apll>)/number theoretic (<apll>LπR</apll>) functions.  In order to return accurate results over a wide range of precision, VFP and floating point numeric arguments are converted to rational and integer numbers, respectively, and the result is returned as a rational or integer number.  Similarly, rational and integer numeric arguments return the same datatype in the result.</p>

<p>Ignoring purely structural functions, the list of functions that produce VFP numbers given rational numbers is as follows:</p>

* Power:  <apll>*R</apll> and <apll>L*R</apll> (except when <apll>R</apll> is a 32-bit integer, in which case the result is a rational number)
* Logarithm:  <apll>⍟R</apll> and <apll>L⍟R</apll>
* Pi Times and Circle functions:  <apll>○R</apll> and <apll>L○R</apll>
* Root:  <apll>√R</apll> and <apll>L√R</apll>
* Factorial and Binomial:  <apll>!R</apll> and <apll>L!R</apll> (except when the arguments are rational integers, in which case the result is a rational integer)

<p>Beyond the ones mentioned above, the list of functions that <b>don't</b> produce a rational or VFP result given those argument(s) is as follows:</p>

* Depth:  <apll>≡</apll> (Integer)
* Dyadic Comparison:  <apll>= ≠ < ≤ ≥ > ≡ ≢</apll> (Boolean)
* Nand and Nor:  <apll>⍲ ⍱</apll> (Boolean)
* Grade Up/Down:  <apll>⍋ ⍒</apll> (Integer)
* Index Of:  <apll>⍳</apll> (Integer)
* Member Of:  <apll>∊</apll> (Boolean)
* Find:  <apll>⍷</apll> (Boolean)
* Subset and Superset:  <apll>⊆ ⊇</apll> (Boolean)
* Format:  <apll>⍕</apll> (Character)

<p>Otherwise, rational argument(s) produce rational result(s) and VFP argument(s) produce VFP result(s).</p>

===Datatype Demotion===

<p>It is common in APL implementations to demote datatypes where appropriate.  For example, the constant <apll>1.0</apll> might actually be represented as an integer or even Boolean datatype.  The idea is there is no loss of precision and the storage is typically smaller which might lead to a more efficient algorithm when next used, so why not?</p>

<p class="note">With rational and VFP numbers those reasons no longer apply.  While the constant <apll>1x</apll> might have the same precision as the constant <apll>1.0</apll>, the difference in latent precision between the two is vast.  In fact, in order for datatype propagation of rational and VFP numbers to work at all, we must be careful <b>not</b> to demote them automatically to a smaller datatype.  Otherwise, it would require an intolerable degree of analysis on the part of the programmer to ensure that the desired datatype (rational or VFP) remains in effect throughout a calculation.</p>

===Conversions===

<p>To convert manually from one datatype to another,</p>

* Integer to rational, use <apll>0x+</apll>
* Integer, floating point, or rational number to VFP, use <apll>0v+</apll>
* Rational integer to a 64-bit integer (possibly losing some precision), use <apll>⍎⍕</apll>
* Rational non-integer to a floating point number (possibly losing some precision), use <apll>⍎⍕0v+</apll>
* VFP number to a floating point number (possibly losing some precision), use <apll>⍎⍕</apll>
* VFP number to rational &mdash; at the moment, no APL method exists although the underlying libraries do have such a function

===Comparisons===

<ul><li><p>Comparisons between two rational numbers or a rational number and any other integer is exact &mdash; just as they are between integers.</p></li>

<li><p>Comparisons between a rational number and a floating point number convert both arguments to VFP numbers and compare the two as below.</p></li>

<li><p>Comparisons between a VFP number and any other number is sensitive to <apll>⎕CT</apll> &mdash; just as they are between floats.</p></li>

</ul>

<p>That is, comparisons continue the analogy between integers and rationals as well as floats and VFPs.</p>

===Integer Tolerance===

<p>Both rational and VFP numbers may be used where the system ordinarily requires an integer (such axis coordinates, indexing, left argument to structural primitives, etc.) just as the system tolerates floating point numbers in those contexts if they are sufficiently near an integer.  In all cases, the system attempts to convert the non-integer to an integer using the fixed system  comparison tolerance (at the moment, <apll>3E¯15</apll>).</p>

===Infinities===

<p>Support for <apll>±∞</apll> has been extended to rational and VFP numbers in the same manner as it applies to 64-bit integers and 64-bit floats.  That is, the same cases covered by the system variable <apll>⎕IC</apll> (Indeterminate Control) also apply to infinite rational and VFP numbers.  Moreover, infinite numeric constants may be entered, for example, as</p>

* <apll>∞x</apll>
* <apll>∞r1</apll>
* <apll>∞v</apll>
* <apll>∞v0</apll>

<p>Also constants such as <apll>2r∞</apll> resolve to <apll>0x</apll>.</p>

===New And/Or Different Behavior===

<ul>
  <li><p>Both roll (<apll>?R</apll>) and deal (<apll>L?R</apll>) on rational integers use a built-in random number generator so as to use the entire range of rational integers – this algorithm uses its own internal seeds that are much more complicated than the simple integer seed that is <apll>⎕RL</apll>.  Thus <apll>⎕RL</apll> is unchanged by these functions on rationals.</p>

<p>For example, if you need <b>really</b> large random numbers</p>

<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;?10*60x<br />
370857192605742854709703007683731949504799559659692534573173</apll>
</li>
  <li><p>At the moment, matrix inverse (<apll>⌹R</apll>) and matrix division (<apll>L⌹R</apll>) on rational or VFP arguments each have two limitations above and beyond that of normal conformability:</p>
    <ul>
      <li><p>for a square right argument that it be non-singular, and</p></li>
      <li><p>for an overdetermined (<apll>&gt;/⍴R</apll>) right argument that the symmetric matrix <apll>(⍉R)+.×R</apll> be non-singular.</p></li>
    </ul>
    <p>These limitations are due to the algorithm ([http://en.wikipedia.org/wiki/Gauss%E2%80%93Jordan_elimination Gauss-Jordan Elimination]) used to implement Matrix Inverse/Divide on rational and VFP numbers.</p>

    <p>Integer and floating point arguments are not subject to these limitations because they use a more general algorithm ([http://en.wikipedia.org/wiki/Singular_value_decomposition Singular Value Decomposition]) that produces a unique result even for singular arguments (e.g., <apll>⌹5 3⍴0</apll>).</p></li>
</ul>

===Conclusions===

<p>The new datatypes offer several benefits:</p>

* They extend the precision of existing integer and floating point datatypes to a much greater level.
* As integer blows up to floating point, rational blows up to VFP, providing a natural parallel progression for irrational and transcendental primitive functions.
* There is a close similarity between integer and rational numbers as well as floating point and VFP numbers.
* Datatype propagation without demotion allows one to code an algorithm in either of the new types easily and without the need for detailed analysis of the datatype in intermediate results.
* All primitives extend naturally to encompass the new types as numbers.
* The notation for constants builds on existing point notation formats.

===Acknowledgments===

<p>The designers of J are thanked for having the foresight to include [http://www.jsoftware.com/help/dictionary/dictg.htm rational numbers] as a separate datatype.</p>

<p>The following GPL libraries have been used to provide support for these datatypes:</p>

* MPIR (Multiple Precision Integers and Rationals) at [http://www.mpir.org mpir.org].
* MPFR (Multiple Precision Floating-Point Reliable Library ) at [http://www.mpfr.org mpfr.org].