The Under Operator 0. Definition and Motivation Under (AKA dual) is a dyadic operator f⍢g defined as: f⍢g ⍵ ←→ g⍣¯1 f g ⍵ ⍺ f⍢g ⍵ ←→ g⍣¯1 (g ⍺) f (g ⍵) In words: apply g to the argument(s), then apply f to the result(s), and finally apply the inverse of g to the result of that. Diagrammatically: f⍢g ⍵ ⍺ f⍢g ⍵ g⍣¯1 g⍣¯1 | | f f | / \ g g g | | | ⍵ ⍺ ⍵ As a d-operator: Under←{0=⎕nc'⍺': ⍵⍵⍣¯1⊢⍺⍺ ⍵⍵ ⍵ ⋄ ⍵⍵⍣¯1⊢(⍵⍵ ⍺)⍺⍺(⍵⍵ ⍵)} Under was first defined by Iverson in 1978 [0] and carried forward in [1,2,3]. Under elucidates the important but often mysterious concept of duality in mathematics. A duality is with respect to a transformation, here the function g . A problem is transformed by g into another domain where it more readily solved by f , and then transformed back into the original domain. An example from real life is “under anasthetics”:
Obviously f⍢g does not provide anything new,
because it can be replaced by an equivalent short expression.
It is justified by its benefits as a tool of thought.
1. Simple Examples A simple example of under is × ↔ +⍢⍟ , multiplication is addition under log. (The equivalence underlies the design of slide rules.) 3 +Under⍟ 4 12 * (⍟3) + (⍟4) 12 ¯3 +Under⍟ 4 ¯12J1.46958E¯15 * (⍟¯3) + (⍟4) ¯12J1.46958E¯15 Now that you know × ↔ +⍢⍟ , do you know what is ×⍢* ? A few other examples:
Further examples of under can be found in
[5]
and
[6].
2. A Non-Trivial Example A less trivial example with clear tool of thought benefits, is extended precision multiplication. (More precisely, digital multiplication without carry AKA polynomial multiplication AKA convolution.) If ⍺ and ⍵ are the digits of extended precision numbers, then ⍺ mult ⍵ ←→ ⍺ ×⍢FFT ⍵ FFT is the Fast Fourier Transform and × is the ordinary APL multiply on two numeric vectors. The “school” method for extended precision multiply is +/OB ⍺∘.×⍵ where OB is an operator which applies its operand to the oblique lines (anti-diagonals). For example, if x←5 6⍴⍳30 then its oblique lines are: x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ⊂ OB x ┌─┬───┬──────┬─────────┬─────────────┬─────────────┬ │1│2 7│3 8 13│4 9 14 19│5 10 15 20 25│6 11 16 21 26│ └─┴───┴──────┴─────────┴─────────────┴─────────────┴ ┬───────────┬────────┬─────┬──┐ │12 17 22 27│18 23 28│24 29│30│ ┴───────────┴────────┴─────┴──┘ The killer in the school method is of course the ∘.× , whose deleterious effects start to be felt at around 1000 digits, and is completely impossible when you get up to a million or more digits. For ×⍢FFT , both FFT and its inverse are O(n×⍟n) and of course × is O(n) , so the whole extended precision multiply is O(n×⍟n) , much better than the O(n*2) school method. An implementation of FFT was originally written in J [7] and subsequently translated into APL [8,9]. It is updated here to version 14.0: mult←{ cube ← {⍵⍴⍨2⍴⍨2⍟⍴⍵} roots ← {¯1*(⍳⍵)÷⍵} butterfly ← {(⊣/⍺)∇⍣(×r)⊢(+⌿⍵),[r-0.5]⍺×[⍳r←≢⍴⍺]-⌿⍵} FFT ← { ,(cube roots 2÷⍨⍴⍵) butterfly cube ⍵} IFT ← {(⍴⍵)÷⍨,(cube +roots 2÷⍨⍴⍵) butterfly cube ⍵} m←2*⌈2⍟¯1+(⍴⍺)+⍴⍵ IFT (FFT m↑⍺) × (FFT m↑⍵) ⍝ ←→ (m↑⍺) ×⍢FFT (m↑⍵) } mult1←{+⌿(-⍳≢⍺)⌽(0 ¯1++\(≢⍺),≢⍵)↑⍺∘.×⍵} ⍝ "school" method x y ← ↓ ?2 2048⍴10 ⍴x mult y 4096 ⌈/ | (x mult y) - 4096↑x mult1 y 1.73909E¯11 cmpx 'x mult y' 'x mult1 y' x mult y → 3.83E¯3 | 0% ⎕⎕⎕⎕⎕ * x mult1 y → 2.50E¯2 | +554% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 3 Obverse It’d be pretty hard for the system to “figure out” the inverse of FFT, the IFT or Inverse Fourier Transform. To avoid this problem, we can introduce an obverse operator ⍫ ; f⍫g ←→ f except that f⍫g⍣¯1 ←→ g⍫f . So to make it explicit, ⍺ mult ⍵ ←→ ⍺ ×⍢FFT ⍵ ←→ ⍺ ×⍢(FFT⍫IFT) ⍵ Obverse is pretty straightforward.
There are no side effects, no special line labels,
no special syntax in the header, etc.
References
Presented at Dyalog ’15, Naxos Beach, Sicily, 2015-09-10.
|