rational arithmetic — Dyalog '20 questions

[Roger|Dyalog]

Some of the questions on Rational Arithmetic posed during the Dyalog ’20 User Meeting:

a. What happens if you apply qi to an irrational number?
b. What about Egyptian fractions?
c. In the representation, ⊂(⊂numerator),(⊂denominator),⊂sign, why is the there a separate part for the sign?
d. The function iq for converting rationals back to a floating points, does not work on negative numbers.
e. Performance?
f. Does the rational arithmetic facility need to work with prime numbers?
g. Big Floats
h. What about complex numbers?
i. Where can I get the code?


a. What happens if you apply qi to an irrational number?

In Dyalog APL you can only have integers and floating point numbers, and irrational numbers are necessarily represented in floating point. Therefore, qi works fine on “irrational numbers”. qi does have an optional left argument which specifies the tolerance to use in the conversion to rational numbers.

For example:

      qi 2*0.5
┌───────────────────────────────┐
│┌─────────────┬─────────────┬─┐│
││9 3 6 9 3 1 9│6 6 2 5 1 0 9│1││
│└─────────────┴─────────────┴─┘│
└───────────────────────────────┘
      0 qi 2*0.5
┌─────────────────────────────────────┐
│┌─────────────────┬───────────────┬─┐│
││1 3 1 8 3 6 3 2 3│9 3 2 2 2 3 5 8│1││
│└─────────────────┴───────────────┴─┘│
└─────────────────────────────────────┘
      20 ⍕Q qi 2*0.5
1.41421356237308699374
      20 ⍕Q 0 qi 2*0.5
1.41421356237309508948

      1 ↓ 20 ⍕ 2*0.5
1.414213562373095_____

(Misalignments in the display are due to defects in the APL Chat Forum software.)


b. What about Egyptian fractions?

An Egyption fraction is a finite sum of unit fractions (fractions with numerator 1). The following function (translated from J) computes an Egyptian fraction from a rational number:

      ef ← {(,1)≡⊃⊃⍵: ,⍵ ⋄ t, ∇ ⍵ -Q ⊢t← ÷Q (qi 1) +Q ⌊Q ÷Q ⍵}

      ef qi 19÷20
┌───────┬───────┬───────┬───────────┐
│┌─┬─┬─┐│┌─┬─┬─┐│┌─┬─┬─┐│┌─┬─────┬─┐│
││1│2│1│││1│3│1│││1│9│1│││1│1 8 0│1││
│└─┴─┴─┘│└─┴─┴─┘│└─┴─┴─┘│└─┴─────┴─┘│
└───────┴───────┴───────┴───────────┘

      ⍕Q ef qi 19÷20
1r2 1r3 1r9 1r180

      ⍕Q +Q/ ef qi 19÷20
19r20

      v← ef qi 11÷199
      ⍴v
11

      ⍕Q +Q/ v
11r199

      ⍕Q 5↑v
1r19 1r379 1r159223 1r28520799973 1r929641178371338400861

      ≢¨ 1 ⊃¨ v   ⍝ number of digits in the denominators
2 3 6 11 21 43 85 169 337 674 1348

c. In the representation, ⊂(⊂numerator),(⊂denominator),⊂sign, why is the there a separate part for the sign?

      qi 0.875 ¯3.25 0 123
┌───────┬──────────┬───────┬───────────┐
│┌─┬─┬─┐│┌───┬─┬──┐│┌─┬─┬─┐│┌─────┬─┬─┐│
││7│8│1│││1 3│4│¯1│││0│1│0│││1 2 3│1│1││
│└─┴─┴─┘│└───┴─┴──┘│└─┴─┴─┘│└─────┴─┴─┘│
└───────┴──────────┴───────┴───────────┘

I find that the representation is easier to work with when the sign is a separate part. If the sign is integrated with the numerator and/or the denominator, there is a question of how it would be done. (Part of the leading digit? Part of the numerator or denominator or both, etc.)

It turned out that the question was posed in the context where the numerator and denominator are single integers. In that context, the choices are simpler.


d. The function iq for converting rationals back to a floating points, does not work on negative numbers.

This is now corrected. Thanks.

      iq ← {(⊃⌽⍵) × ÷/ 10⊥¨ 2↑ ⍵}¨

e. Performance?

I expect the performance to improve significantly if there is a C implementation of fast multiplication. Currently the rational arithmetic facility uses an FFT-based multiplication, written in APL.


f. Does the rational arithmetic facility need to work with prime numbers?

No.

In the representation, the numerator and denominator are relatively prime (co-prime), but that just means that they have no common factors other than 1, ensured by dividing each of them by their GCD. The relatively prime condition leads to a nice property: two rational numbers are equal if and only if their representations are the same.

You can use the rational arithmetic facility to do prime number computations. See for example the APL Chat Forum post Miller-Rabin Primality Testing.


g. Big Floats

Due to a hiccup in my use of the Zoom screen sharing I was unable to show an example of extended precision floating point. The following is what I wanted to say:

We have shown that it is possible to compute rational approximations to non-rational functions. Another approach is to have floating point arithmetic to a specified number of digits (“big floats”). The following examples are from work in progress.

MAXDIGITS specifies the number of significant floating point decimal digits. Like the rational arithmetic facility, there is a design for the representation, a function fi (“floating point input”) to specify big floats conveniently, and a monadic operator F for working with big floats. The examples illustrate the computation of Euler’s number (*1) using a Taylor series. (The number of terms in the series, 60, is estimated by !⍣¯1 .)

      MAXDIGITS ← 80

      fi 3.14159e¯20
┌───────────────────┐
│┌───────────┬───┬─┐│
││3 1 4 1 5 9│¯25│1││
│└───────────┴───┴─┘│
└───────────────────┘

      ¯20 ⍕ +/ ÷ ! ⍳60
 2.718281828459046____E0

      ¯80 ⍕F +F/ ÷F !F fi ⍳60
2.71828182845904523536028747135266249775724709369995957 … 476e0
      ' ',⎕d[A001113]   ⍝ OEIS A001113
 271828182845904523536028747135266249775724709369995957 … 4759 …

      !⍣¯1 ⊢ 1e80
58.92

h. What about complex numbers?

I believe complex numbers as pairs (real and imaginary parts) of big floats would be more useful than complex numbers as pairs of rationals.


i. Where can I get the code?

You can download the presentation materials and the workspace from here (link from the Dyalog ’20 User Meeting webpage).