rslt ← {larg} (fn ##.rats) rarg ⍝ Rational arithmetic.
rslt ← (land ##.rats) rarg ⍝ Rational number.
[rats] provides accurate conversion and arithmetic for non-negative rational
numbers.
NB: [rats] deals only in single (scalar) numbers, rather than whole arrays.
Called with a natural number left operand, rats converts [land] and [rarg] to an
internal form.
r ← 16 rats 9 ⍝ internal form of rational number 16r9.
s ← 1 rats 2 ⍝ .. .. .. .. 1r2.
Otherwise, the operand is a function chosen from monadic ⍕ or ⍎:
rfmt ← ⍕rats ⍝ ⍕ r-format.
real ← ⍎rats ⍝ ⍎ approx real equivalent.
rfmt¨ r s ⍝ r-format of rational numbers.
16r9 1r2
real¨ r s ⍝ approx real equivalent of rational numbers.
1.7778 0.5
or from one of the dyadic functions + - × ÷ * ∨ ∧:
rfmt r +rats s ⍝ + sum of rational numbers 16r9 + 1r2
41r18
rfmt r -rats s ⍝ - difference · · · 16r9 - 1r2
23r18
rfmt r ×rats s ⍝ × product · · · · 16r9 × 1r2
8r9
rfmt r ÷rats s ⍝ ÷ quotient · · · 16r9 ÷ 1r2
32r9
rfmt r *rats s ⍝ * power · · · 16r9 * 1r2
4r3
rfmt r ∨rats s ⍝ ∨ gcd · · · · · 16r9 ∨ 1r2
1r18
rfmt r ∧rats s ⍝ ∧ lcm · · · · · 16r9 ∧ 1r2
16r1
[rats] assumes the presence of function →factors←, which it calls when it needs
to determine the prime factors of an argument. In practice, this happens relat-
ively infrequently.
Technical notes
---------------
A rational number ⍺r⍵ is conveniently represented as a pair [P Q] of vectors of
prime factors and corresponding powers. Within [rats] these vectors are stored
as a 2-row simple integer matrix.
For example: the rational number 28r75 has P≡(2 7 3 5) and Q≡(2 1 ¯1 ¯2):
28 rats 75 ⍝ internal form of 28r75.
2 7 3 5
2 1 ¯1 ¯2
Positive powers contribute to the numerator and negative ones to the denominat-
or. The approximate real equivalent of [P Q] is thus: P×.*Q.
28÷75 ⍝ approx real 28r75
0.37333
×/*⌿ 28 rats 75 ⍝ .. ..
0.37333
This representation makes arithmetic particularly straightforward. Almost all
operations are expressed in terms of factor matrices and even sums and differ-
ences are applied only to what remains after common factors have been removed.
This means that the relatively expensive factoring of large numbers into primes
is reduced to a minimum.
Normal Form
-----------
Subfunction [norm] normalises its argument by collecting like factors and summ-
ing their powers. The sum of powers with differing signs is equivalent to the
cancelling operation, when dealing with fractions.
In addition, [norm] removes factors-of-power-0, and powers-of-factor-1. This
means that the structure for rational number 1r1 is a 0-column matrix:
display 1 rats 1 ⍝ 1r1 - 0-column matrix.
┌⊖┐
↓0│
│0│
└~┘
Finally, as 0r1, 0r2, ·· 0r<anything> are equivalent, [norm] chooses 0r1.
NB: [norm] does not arrange factor-power columns in any particular order, so the
following are equivalent normal forms:
r35 r53 ⍝ equivalent expressions of 15r1
┌───┬───┐
│3 5│5 3│
│1 1│1 1│
└───┴───┘
⍕rats¨ r35 r53 ⍝ r-formats are identical.
15r1 15r1
Product ×
---------
The product of two rational structures is just the normalisation of their caten-
ation!
mul ← {norm ⍺,⍵} ⍝ ⍺×⍵ (⍺ and ⍵ are rational numbers).
¯
Quotient ÷
----------
The integer power of a rational number [P Q]*⍵ = [P Q×1 ⍵].
expn ← {↑1 ⍵×↓⍺} ⍝ ⍺*⍵ (⍺ is rational, ⍵ is integer).
or
expn ← {1 ⍵×[⎕io]⍺} ⍝ ... according to taste.
So:
(28 rats 75)∘expn¨1 2 3 ⍝ 28r75 * 1 2 3
┌─────────┬─────────┬─────────┐
│2 7 3 5│2 7 3 5│2 7 3 5│
│2 1 ¯1 ¯2│4 2 ¯2 ¯4│6 3 ¯3 ¯6│
└─────────┴─────────┴─────────┘
In particular, expn∘¯1 returns the _reciprocal_ of its rational argument:
{⍵∘expn¨1 ¯1} 28 rats 75 ⍝ 28r75 * 1 ¯1
┌─────────┬─────────┐
│2 7 3 5│ 2 7 3 5│
│2 1 ¯1 ¯2│¯2 ¯1 1 2│
└─────────┴─────────┘
so we can use expn to implement division:
div ← {norm ⍺,⍵ expn ¯1} ⍝ ⍺÷⍵ (⍺ and ⍵ rational).
¯
Next, notice that function 0∘⌈ returns the (un-normalised) numerator:
0∘⌈ 28 rats 75 ⍝ 28r1
2 7 3 5
2 1 0 0
real 0∘⌈ 28 rats 75 ⍝ 28r1
28
and applied to the reciprocal, reveals the denominator:
{0⌈⍵∘expn¨1 ¯1} 28 rats 75 ⍝ 28r75 → 28 75
┌───────┬───────┐
│2 7 3 5│2 7 3 5│
│2 1 0 0│0 0 1 2│
└───────┴───────┘
sepr ← {0⌈⍵∘expn¨1 ¯1} ⍝ separate numerator/denominator.
real¨ sepr 28 rats 75 ⍝ round trip: (28 75) → 28r75 → (28 75)
28 75
Power *
-------
The _rational_ power of a rational number:
·
[P Q]*[R S] = [P X],
where X = Q×R×.*S,
as long as X≡⌊X,
otherwise, error "irrational".
·
4r9 * 3r2 → 8r27
·
2r1 * 1r2 → irrational (square root of 2).
GCD ∨ / LCM ∧
---------------
We can extract greatest-common-divisor and least-common-multiple directly from
the factors of a pair of normalised rational numbers.
If two _whole_ numbers have normal rational forms [P Q] and [R S] (which means
that vectors Q and S have no negative items) then:
[P Q] ∨ [R S] = [PiR QnS], ⍝ ∨ ----------------------gcd[1]
¯
where:
PiR is the intersection of factor vectors P and R and
¯¯¯¯¯¯¯¯¯¯¯¯
QnS is the minimum of power vectors Q and S within the intersection.
¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
and
[P Q] ∧ [R S] = [PuR QxS], ⍝ ∧ ----------------------lcm[1]
¯
where:
PuR is the union of factor vectors P and R and
¯¯¯¯¯
QxS is the maximum of power vectors Q and S within the union.
¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
For example:
90 rats 1 ⍝ [(2 3 5)(1 2 1)]
2 3 5
1 2 1
84 rats 1 ⍝ [(2 3 7)(2 1 1)]
2 3 7
2 1 1
(90 rats 1)∨rats 84 rats 1 ⍝ gcd ∨: intersection / minimum.
2 3
1 1
(90 rats 1)∧rats 84 rats 1 ⍝ lcm ∧: union / maximum.
2 3 5 7
2 2 1 1
Secondly, if a, b, c and d are whole numbers, then in general:
(a÷b) ∨ (c÷d) = (a∨c) ÷ (b∧c) ⍝ ∨ ----------------------gcd[2]
(a÷b) ∧ (c÷d) = (a∧c) ÷ (b∨c) ⍝ ∧ ----------------------lcm[2]
Let ⌈P Q] and ⌊P Q] be notation for the numerator and denominator of [P Q]
⌈P Q] = num ← {norm 0⌈⍵} ⍝ numerator.
⌊P Q] = den ← {norm 0⌈⍵ expn ¯1} ⍝ denominator.
For example:
if
[P Q] = [(2 3 5 7)(¯1 2 1 ¯3)]
then
⌈P Q] = [(3 5)(2 1)] ⍝ numerator.
⌊P Q] = [(2 7)(1 3)] ⍝ denominator.
and
[P Q] = ⌈P Q] × ⌊P Q] * ¯1 ⍝ numerator × ÷ denominator.
¯
therefore:
[P Q] ∨ [R S]
¯
⌈P Q] ⌈R S] ⍝ defn of ⌈...] and ⌊...]
=> ----- ∨ -----
⌊P Q] ¯ ⌊R S]
⌈P Q]∨⌈R S] ⍝ from gcd[2] above.
=> -----------
⌊P Q]∧⌊R S]
[PiR QnS] ⍝ from gcd[1] above.
=> ---------
[PuR QxS]
=> [PiR QnS], [PuR QxS] * ¯1 ⍝ as in the quotient case.
Similarly, for lcm (∧):
[P Q] ∧ [R S]
¯
⌈P Q] ⌈R S] ⍝ defn of ⌈...] and ⌊...]
=> ----- ∧ -----
⌊P Q] ¯ ⌊R S]
⌈P Q]∧⌈R S] ⍝ from lcm[2] above.
=> -----------
⌊P Q]∨⌊R S]
[PuR QxS] ⍝ from lcm[1] above.
=> ---------
[PiR QnS]
=> [PuR QxS], [PiR QnS] * ¯1 ⍝ as in the quotient case.
Sum / difference
----------------
In general, for numbers A and B and any N≠0:
┌ A B ┐
A + B = N × │ --- + --- │
¯ └ N ¯ N ┘
If we choose N = A∨B (greatest common divisor of A and B), then both (A÷N) and
(B÷N) are whole numbers and may be added (resp. subtracted) directly. Further,
(A÷N) and (B÷N) are the smallest whole numbers for which this holds, so their
sum (resp. difference) is as small as possible and so easiest to re-factorise.
(muse:
sum/difference deals separately with zero arguments. Zero seems (to JMS) to
be, let's say, an uneasy member of the set of rational numbers.
sum←{ ⍝ sum (difference).
0∊⍵:⍺ ⍝ ⍺+0 → ⍺, ⍺-0 → ⍺
0∊⍺:⍵×nchk ⍺⍺ 1 ⍝ 0+⍵ → ⍵, 0-⍵ → error
mul←⍺ gcd ⍵ ⍝ gcd multiplier
...
)
Examples:
factors¨28 75 ⍝ prime factors.
┌─────┬─────┐
│2 2 7│3 5 5│
└─────┴─────┘
28 rats 75 ⍝ rational representation.
2 7 3 5
2 1 ¯1 ¯2
⍕rats 28 rats 75 ⍝ r-format.
28r75
⍎rats 28 rats 75 ⍝ approx real number equivalent.
0.3733333333
⍝ We can make a translator for simple expressions of rational scalars:
rexp←{⍺←'r' ⍝ simple r-expression translator.
rat←{')',⍵,'rats('} ⍝ ⍵ → )⍵rats(
svec←rat\¨2/¨'+-×÷*∧^∨⍎⍕' ⍝ subs pair for each op fn.
src←↑subs/(svec,⊂⍺' rats '),⊂⍵ ⍝ translated source. See →subs←.
'(',src,')' ⍝ source for apl expression.
}
rexp'2r3 + 3r4' ⍝ r-expression translation.
(2 rats 3 )+rats( 3 rats 4)
eval ← ⍕rats∘⍎∘rexp ⍝ r-expression evaluation.
eval ' 36r140 ' ⍝ simplify.
9r35
eval '1r2 + 1r3' ⍝ sum.
5r6
eval '1r2 - 1r3' ⍝ difference.
1r6
eval '3r4 × 2r3' ⍝ product.
1r2
eval '2r3 ÷ 2r3' ⍝ quotient.
1r1
eval '4r9 * 3r2' ⍝ power
8r27
eval '2r5 ∨ 3r5' ⍝ gcd.
1r5
eval '2r5 ∧ 3r5' ⍝ lcm.
6r5
eval ' (1r2 × 3r4) + 1r8 ' ⍝ more complex expression.
1r2
See also: numbers pco factors rational subs gcd nats bt ary
Back to: contents
Back to: Workspaces