rslt ← (fun ##.limit) arg                   ⍝ Function power limit (fixpoint).

This  operator  applies its function operand repeatedly until the result has the
same value as the argument (a "fixpoint" of the function). Note that the operand
function  must  be monadic and that a dyadic function may be rendered monadic by
being bound to ("curried" with) either of its arguments:

NB: Dyalog implements [limit] directly using derived operator ⍣≡.

Technical notes:

A straightforward coding of the operator might look like this:

    limit←{             ⍝ Function power limit (fixpoint).
        rslt←⍺⍺ ⍵       ⍝ Apply operand until
        rslt≡⍵:rslt     ⍝ ... it has no effect.
        ∇ rslt          ⍝ Otherwise, repeat.
    }

This variable-free version, due to Phil Last, which uses the left argument of an
inner operator to carry the previous result, turns out to be quicker:

    limit←{             ⍝ Function power limit (fixpoint).
        ⍵ ⍺⍺{           ⍝ 'old' value:
            ⍺≡⍵:⍵       ⍝       old matches new: finished.
            ⍵ ∇ ⍺⍺ ⍵    ⍝       otherwise: try new value.
        }⍺⍺ ⍵           ⍝ 'new' value.
    }

For amusement, the operator can be made nearly _palindromic_ by substituting (∇)
with (⍺⍺ ∇∇):

    limit←{
        ⍵ ⍺⍺{
            ⍺≡⍵:⍵
            ⍵ ⍺⍺ ∇∇ ⍺⍺ ⍵
        }⍺⍺ ⍵
    }

...  and fully palindromic by appending a dummy guard, which is never evaluated,
after  the recursive call. This is not without precedent; a significant proport-
ion of our DNA _may_ turn out to be dummy code that is never evaluated!

    limit←{
        ⍵ ⍺⍺{
            ⍺≡⍵:⍵
            ⍵ ⍺⍺ ∇∇ ⍺⍺ ⍵
            ⍵:⍵≡⍺           ⍝ dummy line mirrors guard.
        }⍺⍺ ⍵
    }

Stringing this out on a single line shows the symmetry. The following expression
calculates the "Golden Ratio" (a.k.a. "Phi") by finding a fixpoint of the funct-
ion  {1+÷⍵} close to {⍵÷+1}1. The 1 at the extreme left of the expression is in-
cluded solely to mirror the 1 on the right and is ignored.

      1{1+÷⍵}{⍵ ⍺⍺{⍺≡⍵:⍵ ⋄ ⍵ ⍺⍺ ∇∇ ⍺⍺ ⍵ ⋄ ⍵:⍵≡⍺}⍺⍺ ⍵}{⍵÷+1}1
1.618033989

For amusement, there is an animation of this expression on YouTube:
See: http://www.youtube.com/watch?v=X3bv4Iu1aEg&fmt=18

Examples:

      enlist←{1↓↑,/'·',,,¨⍵}limit   ⍝ Expensive alternative to primitive: ∊.

      0.5∘× limit 2                 ⍝ Fixpoint of halving function.
0
      ⍝ Note that a function can have more than one fixpoint:

      *∘(÷3) limit¨¯2 2             ⍝ Two fixpoints of cube root function.
¯1 1
      ⍝ Operator: [nr] returns the next term in a Newton-Raphson approximation:

      nr←{⍺←⎕CT                     ⍝ Newton-Raphson.
          y ∆y←⍺⍺¨(⊂⍵)×1+0 ⍺        ⍝ f(x), f(x+∆)
          ⍵+(⍺×y)÷y-∆y              ⍝ next estimate.
      }

      1∘○ nr limit 3 6 9            ⍝ Roots of Sin(x) near x=3, x=6, x=9.
3.1416 6.2832 9.4248

⍝ Just for fun, the above code for the next item in the Newton-Raphson sequence
⍝ could be expressed as a single derived function:
⍝
⍝                                ┌─┐ ← operand function 1∘○
⍝     ┌──────────────────────────┤ ├──────────────────┐
      +∘(÷∘↑∘(-/)⍨∘(×∘⎕ct)∘⊃⍨⍨)∘(1∘○¨)∘((1+0 ⎕ct)∘×)∘⊂⍨ limit 3 6 9
3.1416 6.2832 9.4248

⍝ See also →tacit←

⍝ Gianluigi Quario suggests the following example for finding the Arithmetic-
⍝ Geometric Mean (AGM).
⍝
⍝ The arithmetic-geometric mean of two numbers M and N is defined by starting
⍝ with a(0)←M  and  g(0)←N, then iterating:
⍝
⍝   a(n+1) ← arithmetic mean of a(n) and g(n)
⍝   g(n+1) ← geometric  mean of a(n) and g(n)
⍝       until
⍝   a(n)=g(n)

      AM←{(+/⍵)×÷⍴,⍵}               ⍝ Arithmetic mean.
      GM←{(×/⍵)*÷⍴,⍵}               ⍝ Geometric  mean.
      AGM←{⍬⍴{(AM ⍵),GM ⍵}limit ⍵}  ⍝ Arithmetic-geometric mean.

      AM 1 2 3 4 5
3
      GM 1 2 3 4 5
2.6052
      AGM 1 2 3 4 5
2.7991
      ÷AGM 1 2*÷2                   ⍝ Gauss's constant.
0.83463

⍝ Gianluigi's second example calculates ArcTan by similar means. (Acton, F.S.
⍝ "The Arctangent." In Numerical Methods that Work, upd. and rev. Washington,DC:
⍝ Math. Assoc. Amer., pp. 6-10, 1990.)

      ArcTan←{
          ⍝ Inverse trigonometric tangent - gqr 19-11-2002.
          ⍝ For scalar ⍵: (ArcTan ⍵)≡¯3○⍵
          ⍝
          ⍝ Limit's operand function returns a 2-vector. Repeated application
          ⍝ of the function produces two sequences, both of which converge and
          ⍝ have the same limit:
          ⍝
          ⍝    A≡ {a(0),a(1), ... , a(n), ...   }
          ⍝    G≡ {g(0),g(1), ... , g(n), ...   }
          ⍝
          ⍝  Starting with arguments:
          ⍝       a(0)←(1+⍵*2)*-÷2  and  g(0)←1
          ⍝  the iteration produces:
          ⍝       a(n+1)← arithmetic mean of a(n)   and g(n)
          ⍝       g(n+1)← geometric  mean of a(n+1) and g(n)
          ⍝  until:
          ⍝   a(n+1)=a(n) and g(n+1)=g(n) and a(n+1)=g(n+1)

          next←{                          ⍝ next term in sequence.
              AM←{(+/⍵)×÷⍴⍵}              ⍝ arithmetic mean.
              GM←{(×/⍵)*÷⍴⍵}              ⍝ geometric  mean.
              (AM ⍵),GM(AM ⍵),1↓⍵
          }
          start←⍬⍴(1+⍵*2)*-÷2
          finish←⍬⍴next limit start,1     ⍝ calculated limit
          ⍬⍴⍵×start÷finish
      }

      ArcTan 0.5    ⍝ method using limit ...
0.46365

      ¯3○0.5        ⍝ ... agrees with primitive function.
0.46365

⍝ From Mayer Goldberg, the "Univac division algorithm" for ⍺÷⍵, where 0<⍵≤1.

      ⍬⍴{⍵×2-¯1↑⍵} limit 20 0.3
66.667

⍝ ... which can be coded as a derived function using primitive power and monadic
⍝ commute operators. Notice that 0∘⊥ returns the last item of a numeric vector:

    univac_div← ⊃∘(×∘(2∘-)∘(0∘⊥)⍨⍣≡)    ⍝ Univac division algorithm.

    univac_div 1.2 0.3
4

    univac_div dft 1        ⍝ display of derived function, see →dft←
        ∘
      ┌─┴─┐
      ⊃   ⍣
        ┌─┴─┐
        ⍨   ≡
      ┌─┘
      ∘
  ┌───┴───┐
  ∘       ∘
┌─┴─┐   ┌─┴─┐
×   ∘   0   ⊥
  ┌─┴─┐
  2   -

See also: pow inverse traj while until dft tacit

Back to: contents

Back to: Workspaces