Outer Product: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (Text replacement - "<source" to "<syntaxhighlight")
 
(One intermediate revision by the same user not shown)
Line 2: Line 2:


=== Syntax ===
=== Syntax ===
Outer Product differs from all other [[monadic operator]]s, which are written as a single [[glyph]], with the operand on the left. For [[backwards compatibility|historical reasons]], the outer product operator is a [[bi-glyph]] denoted as <source lang=apl inline>∘.</source>, and its appears on the right. This special notation is derived from the <source lang=apl inline>f.g</source> notation of [[inner product]]:<ref>[[Adin Falkoff|Falkoff, A.D.]] and [[Ken Iverson|K.E. Iverson]]. [https://www.jsoftware.com/papers/APL360TerminalSystem1.htm#ip The APL\360 Terminal System: Inner and Outer Products]. Research Report RC-1922. [[IBM]] Watson Research Center. 1967-10-16.</ref>
Outer Product differs from all other [[monadic operator]]s, which are written as a single [[glyph]], with the operand on the left. For [[backwards compatibility|historical reasons]], the outer product operator is a [[bi-glyph]] denoted as <syntaxhighlight lang=apl inline>∘.</syntaxhighlight>, and its appears on the right. This special notation is derived from the <syntaxhighlight lang=apl inline>f.g</syntaxhighlight> notation of [[inner product]]:<ref>[[Adin Falkoff|Falkoff, A.D.]] and [[Ken Iverson|K.E. Iverson]]. [https://www.jsoftware.com/papers/APL360TerminalSystem1.htm#ip The APL\360 Terminal System: Inner and Outer Products]. Research Report RC-1922. [[IBM]] Watson Research Center. 1967-10-16.</ref>
<blockquote>
<blockquote>
The result of an inner product is an array with rank two less than the sum of the argument ranks. The result of an outer product, on the other hand, is always an array of rank equal to the sum of the argument ranks. This follows from the fact that the reduction operation, which collapses two dimensions in an inner product, is not used in the outer product. The notation for outer product reflects this by canonically using a small circle as the first symbol. Thus, the ordinary outer product is written as <code>a∘.×b</code> .
The result of an inner product is an array with rank two less than the sum of the argument ranks. The result of an outer product, on the other hand, is always an array of rank equal to the sum of the argument ranks. This follows from the fact that the reduction operation, which collapses two dimensions in an inner product, is not used in the outer product. The notation for outer product reflects this by canonically using a small circle as the first symbol. Thus, the ordinary outer product is written as <code>a∘.×b</code> .
</blockquote>
</blockquote>


This syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <source lang=j inline>/</source> and <code>⌜</code> respectively, has the usual operator syntax.
This syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <syntaxhighlight lang=j inline>/</syntaxhighlight> and <code>⌜</code> respectively, has the usual operator syntax.


=== Examples ===
=== Examples ===
<source lang=apl>
<syntaxhighlight lang=apl>
       x ← 1 2 3
       x ← 1 2 3
       y ← 4 5 6
       y ← 4 5 6
Line 48: Line 48:
└───┴───┴───┘
└───┴───┴───┘
        
        
</source>
</syntaxhighlight>


=== Applications ===
=== Applications ===
Line 54: Line 54:


For example, suppose we want to find duplicated elements in an non-[[nested array]]. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.
For example, suppose we want to find duplicated elements in an non-[[nested array]]. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.
<source lang=apl>
<syntaxhighlight lang=apl>
       x ← 1 2 3 2
       x ← 1 2 3 2
       ⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
       ⎕ ← matrix ← x∘.=x ⍝ compare elements with each other using equal
Line 72: Line 72:
       (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
       (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
2
2
</source>
</syntaxhighlight>
Using similar techniques, we can define a function that generates prime numbers by using an outer product of [[Residue]].
Using similar techniques, we can define a function that generates prime numbers by using an outer product of [[Residue]].
<source lang=apl>
<syntaxhighlight lang=apl>
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes 10
     primes 10
Line 80: Line 80:
       primes 20
       primes 20
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19
</source>
</syntaxhighlight>
Here there are faster solutions such as the [[wikipedia:Sieve of Eratosthenes|Sieve of Eratosthenes]].
Here there are faster solutions such as the [[wikipedia:Sieve of Eratosthenes|Sieve of Eratosthenes]].
== External links ==
== External links ==

Latest revision as of 22:31, 10 September 2022

∘.

Outer Product (∘.), or Table is a monadic operator, which will produce a dyadic function when applied with a dyadic function. Outer product applies the operand function on each element of the left array with each element of the right array. It can be described as a shortcut for constructing nested for loops.

Syntax

Outer Product differs from all other monadic operators, which are written as a single glyph, with the operand on the left. For historical reasons, the outer product operator is a bi-glyph denoted as ∘., and its appears on the right. This special notation is derived from the f.g notation of inner product:[1]

The result of an inner product is an array with rank two less than the sum of the argument ranks. The result of an outer product, on the other hand, is always an array of rank equal to the sum of the argument ranks. This follows from the fact that the reduction operation, which collapses two dimensions in an inner product, is not used in the outer product. The notation for outer product reflects this by canonically using a small circle as the first symbol. Thus, the ordinary outer product is written as a∘.×b .

This syntactical inconsistency is resolved in J and BQN, where the outer product operator, called Table, and denoted / and respectively, has the usual operator syntax.

Examples

      x  1 2 3
      y  4 5 6
      x ∘., y ⍝ visualizing outer product
┌───┬───┬───┐
1 41 51 6
├───┼───┼───┤
2 42 52 6
├───┼───┼───┤
3 43 53 6
└───┴───┴───┘

      ⍝ works for multi-dimensional arrays as well
      y2 3  'abcdef'
      x2 2  4
      x∘.,y 
┌───┬───┬───┐
1 a1 b1 c
├───┼───┼───┤
1 d1 e1 f
└───┴───┴───┘
┌───┬───┬───┐
2 a2 b2 c
├───┼───┼───┤
2 d2 e2 f
└───┴───┴───┘
             
┌───┬───┬───┐
3 a3 b3 c
├───┼───┼───┤
3 d3 e3 f
└───┴───┴───┘
┌───┬───┬───┐
4 a4 b4 c
├───┼───┼───┤
4 d4 e4 f
└───┴───┴───┘

Applications

Outer product is useful for solving problems that intuitively require a polynomial time algorithm. This may also indicate that such an algorithm is not the fastest solution.

For example, suppose we want to find duplicated elements in an non-nested array. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.

      x  1 2 3 2
        matrix  x∘.=x ⍝ compare elements with each other using equal
1 0 0 0
0 1 0 1
0 0 1 0
0 1 0 1
        count  +/matrix ⍝ get the number of occurence of each element
1 2 1 2
        indices  count  2 ⍝ get the indices of elements which occured more than once
0 1 0 1
        duplicated   indices/x 
2

      ((+/x∘.=x)2)/x ⍝ everything above in one line
2
      (⊢∪⍤/⍨2(+/∘.=)) x ⍝ point-free/tacit version
2

Using similar techniques, we can define a function that generates prime numbers by using an outer product of Residue.

     primes  {x1↓⍳  (2>+0=x∘.|x)/x}
     primes 10
2 3 5 7
      primes 20
2 3 5 7 11 13 17 19

Here there are faster solutions such as the Sieve of Eratosthenes.

External links

Documentation

References

  1. Falkoff, A.D. and K.E. Iverson. The APL\360 Terminal System: Inner and Outer Products. Research Report RC-1922. IBM Watson Research Center. 1967-10-16.
APL built-ins [edit]
Primitive functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentitySelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndex
Selector Index generatorGradeIndex OfInterval IndexIndicesDeal
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Primitive operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductPowerAtUnderRankDepthVariantStencilCut (J)
Quad names
Arrays Index originMigration levelAtomic vector
Functions Name classCase convertUnicode convert
Operators SearchReplace