The Under Operator

Roger Hui




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”:

   
apply anasthetics
   perform surgery
wake up from 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:

mean ← +/ ÷ ≢ arithmetic mean
mean⍢⍟ geometric mean
mean⍢÷ harmonic mean
mean⍢(*∘2) quadratic mean (root mean square)
mean⍢(*∘p) power mean (generalized mean)
 
 ∧⍢~     ∨   De Morgan’s laws
 ∨⍢~     ∧
 
f/⍢⍉    f⌿ also \ andinstead of / and
b/⍢⍉    b⌿
 ⌽⍢⍉    ⊖
 ,⍢⍉    ⍪
 
f Cut 2    (f∘⊖ Cut 1)⍢ ⊖
  cut [4] on trailing separator defined in terms of cut on leading separator

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.) Ifandare 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

[0]   Iverson, K.E., Operators and Functions, 1978-04-26; §8 Composition and Duality.
[1] Iverson, K.E., Rationalized APL, 1983-01-06; §I New Operators.
[2] Iverson, K.E., A Dictionary of APL, 1987-09; u¨v under.
[3] Hui, R.K.W., and K.E. Iverson, J Introduction and Dictionary, 2011; &. and &.: (under) and :. (obverse).
[4] Hui, R.K.W., The Cut Operator, Dyalog ’15, Naxos Beach, Sicily, 2015-09-08.
[5] Hui, R.K.W., Under, J Wiki Essay, 2005-10-12.
[6] Hui, R.K.W., editor, Ken Iverson Quotations and Anecdotes, 2005-09-30.
[7] Rich, H.H., Convolution using FFT, J Programming Forum, 2010-12-27.
[8] Hui, R.K.W., Rational Numbers in Dyalog APL, Dyalog ’11, Boston, 2011-10; Session D05.
[9] Hui, R.K.W., xtimes, dfns Workspace, 2011.


Presented at Dyalog ’15, Naxos Beach, Sicily, 2015-09-10.

created:  2015-06-06 07:25
updated: