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