Find a Fixed Point

Question

Given an integer x1 and some black box function f: ℤ → ℤ find a fixed point of f in the sequence defined by xk+1 := f(xk).

Details

• A value x is said to be a fixed point of f if x = f(x).

  For instance if f(x) := round(x/pi)and we have a starting point x1 = 10 then we get x2 = f(x1) = f(10) = 3, then x3 = f(x2) = f(3) = 1, then x4 = f(x3) = f(1) = 0, and finally x5 = f(x4) = f(0) = 0 which means the submission should return 0.

• You can assume that the generated sequence actually contains a fixed point.
• You can use the native type for integers in place of ℤ.
• You can use any language for which there are defaults for black box functions input in the standard IO meta post. If there are no such default for your language feel free to add one in the sense of the definition of black box functions, and make sure to link your proposals in that definition. Also don't forget to vote on them.

Examples

f(x) = floor(sqrt(abs(x)))
0 -> 0,  all other numbers -> 1

f(x) = c(c(c(x))) where c(x) = x/2 if x is even; 3*x+1 otherwise
all positive numbers should result in 1,2 or 4 (Collatz conjecture)

f(x) = -42
all numbers -> -42

f(x) = 2 - x
1 -> 1

Answer 1

Actually, 1 byte

Y

Try it online!

Y is the fixed point function in Actually. In the TIO example, the function is shown being taken as a string, and £ is used to transform it to a function on the stack. It's also possible to just push the function to the stack like so. These are the only two ways to get a function input in Actually.

Answer 2

APL (Dyalog), 2 bytes

⍣=

Try it online!

NB: I define O←⍣= in the the input section due to a bug in that derived monadic operators can't be defined in the way that TIO likes to define things.

⍣ Is an operator that can be used like (function⍣condition) ⍵

It applies the function, f, to ⍵ until (f ⍵) condition ⍵ returns true.

⍣= is a derived monadic operator that takes a monadic function, f, as its left argument and applies it to its right argument, ⍵, until f ⍵ = ⍵

Answer 3

Haskell, 17 bytes

until=<<((==)=<<)

Try it online!

Answer 4

MATLAB, 41 bytes

function x=g(f,x);while f(x)-x;x=f(x);end

There is also this beauty that does not need function files. Unfortunately it is a little bit longer:

i=@(p,c)c{2-p}();g=@(g,f,x)i(f(x)==x,{@()x,@()g(g,f,f(x))});q=@(f,x)g(g,f,x)

Try it online!

Answer 5

R, 36 35 bytes

thanks to JayCe for golfing down a byte

function(f,x){while(x-(x=f(x)))0;x}

Try it online!

Verify the example functions!

R port of flawr's solution.

Answer 6

Standard ML (MLton), 30 bytes

fun& $g=if$ =g$then$else&(g$)g

Try it online! Use as & n blackbox.

The black box functions are defined as following:

fun blackbox1 x = floor(Math.sqrt(Real.fromInt(abs x)))

fun blackbox2 x = c(c(c(x))) 
and c x = if x mod 2 = 0 then x div 2 else 3*x+1

fun blackbox3 _ = ~42

fun blackbox4 x = 2-x

Ungolfed version:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g

Answer 7

Mathematica, 11 bytes

#2//.x_:>#&

Try it online!

Mathematica, 10 bytes

FixedPoint

Try it online!

Answer 8

Python 2, 39 37 33 bytes

thanks to @Mr.Xcoder for -2 bytes

s=lambda k:s(f(k))if k-f(k)else k

Try it online!

assumes the black-box function to be named f

Answer 9

Jelly, 3 bytes

vÐL

Try it online!

Takes the left argument as a string representing a Jelly link (2_ for instance), and the right argument as an integer

How it works

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given

Answer 10

JavaScript (Node.js), 25 22 21 bytes

thanks Herman Lauenstein for showing me this consensus
thanks to @l4m2 for -1 byte

Assumes the black-box function to be named f.

g=k=>f(k)-k?g(f(k)):k

Try it online!

Answer 11

Brain-Flak, 24 bytes

(()){{}(({})<>[({})])}{}

Try it online!

(for the black box function x -> 2-x in the example below)

The provided black box function should be a program, that given x on the top of the stack, pop x and push f(x) - in other word, it should evaluate the function f on the value on the top of the stack.

Equivalent Mini-Flak is 26 bytes (thanks to Wheat Wizard for saving 2 bytes):

(()){{}(({})( )[{}({})])}{}
             ^ put the function f here

(not counting the comments and spaces)

Take the function (inside the <>) and a number x0 from input. (note that Brain-Flak is an esoteric language and can't take functional argument as input)

---

Example blackbox functions:

x -> 2-x: Try it online!

---

Explanation:

(()){{}(({})<f>[({})])}{}   Main program.
                            Implicit input from stdin to stack.
(  )                        Push
 ()                         literal number 1.
                            Now the content of the stack: [1, x0]
    {                 }     While stack top ≠ 0:
                            current stack content: [something ≠ 0, x]
     {}                       Pop stack top (something). stack = [x]
       (             )        Push
        ({})                    Stack top = x. Current stack = [x]
             f                  Evaluate f. Current stack = [f(x)]
            < >                   (suppress the value of f(x), avoid adding it)
               [    ]           plus the negative of
                ({})            the top of the stack ( = -f(x) )
                              In conclusion, this change (x) on the stack to
                              (f(x)), and then push (x + -f(x))
                            If it's 0, break loop, else continue.
                       {}   Pop the redundant 0 on the top.
                            Implicit output stack value to stdout.

Answer 12

Swift, 47 42 bytes

func h(_ n:Int){f(n)==n ?print(n):h(f(n))}

Naive approach, assumes that the black box function is named f

Answer 13

APL (Dyalog Unicode), 14 bytes

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}

Try it online!

The function at the header is equivalent to f(x) = floor(sqrt(abs(x)))

Thanks @Adám for pointing out that the original answer wasn't valid according to PPCG consensus.

How it works:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ Main 'function' (this is actually an operator)
      :         ⍝ if
 ⍵=⍺⍺⍵          ⍝ the right argument (⍵) = the left function (⍺⍺, which is f) of ⍵
       ⍵        ⍝ return ⍵
        ⋄       ⍝ else
         ∇⍺⍺⍵   ⍝ return this function (∇) with argument f(⍵)

Answer 14

C (gcc), 40 bytes

f(n,b)int(*b)(_);{n=n^b(n)?f(b(n),b):n;}

Try it online! Note that the flags are not necessary, they are there to aid with testing the fixpoint function defined above.

This is a function that takes an int n and a function pointer b : int → int. Abusing the fact that writing to the first variable argument sets the eax register, which is equivalent to returning^†. Otherwise, this is pretty standard as far as C golf goes. n^b(n) checks for the inequality of n and the black box applied to n. When unequal, it calls the fixpoint function f again recursively with the application and black box as arguments. Otherwise, it returns the fixpoint.

^{†Citation needed, I vaguely remember reading this somewhere and google seems to confirm my suspicions}

It declares input with K&R-style parameter typing:

f(n, b)
int(*b)(_);
{
    n=n^b(n)?f(b(n),b):n;
}

The arcane bit on the second line above declares b to be a function pointer that takes an integer parameter—the default type of _ is assumed to be an integer. Similarly, n is assumed to be an integer, and f is assumed to return an integer. Hooray for implicit typing?

Answer 15

Clean, 46 bytes

import StdEnv
p x=hd[n\\n<-iterate f x|f n==n]

Assumes the function is defined as f :: !Int -> Int

It takes the head of the infinite list of applications of f f f ... x filtered for those elements where f el == el.

Try it online!

If you want to change the function in the TIO, Clean's lambda syntax is:

\argument = expression

(actually it's far more complicated, but thankfully we only need unary functions)

Answer 16

Octave, 37 bytes

function x=g(f,x);while x-(x=f(x))end

Try it online!

Octave has inline assignment but MATLAB doesn't, so this is a golfier Octave port of flawr's solution.

It also ports nicely to R.

Answer 17

Kotlin, 50 bytes

{f,k->var a=k;var b=a+1;while(b!=a){b=a;a=f(a)};a}

Try it online!

Answer 18

Forth (gforth), 36 bytes

This version just assumes f is predefined. It's not as cool as the solution below it. Both programs exit with a stack overflow if not found, or a stack underflow if found (after printing the result).

Try it online

: g dup f over = IF . THEN recurse ;

---

Forth (gforth), 52 bytes

This allows a function's execution token to be passed as a parameter, and is definitely the cooler solution.

: g 2dup execute rot over = IF . THEN swap recurse ;

Try it online

Explanation:

: g             \ x1 f          Define g. Params on the stack. f is on top
2dup execute    \ x1 f x2       duplicate both params, execute f(x1)
rot over        \ f x2 x1 x2    move x1 to top and copy x2 to top
= IF . THEN                     compare, if equal, print
swap recurse ;                  otherwise, recurse

Answer 19

Ruby, 31 28 bytes

->x,f{x=f[x]until x==f[x];x}

Try it online!

Answer 20

Clojure, 45 43 bytes

Well, this is the shortest and ugliest:

#(loop[a + b %2](if(= a b)a(recur b(% b))))

+ is there instead of a number so that it is not equal to any value of x0.

55 bytes and functional:

#(reduce(fn[a b](if(= a b)(reduced a)b))(iterate % %2))

Example:

(def f #(...))
(defn collaz [x] (if (even? x) (-> x (/ 2)) (-> x (* 3) (+ 1))))
(f (->> collaz (repeat 3) (apply comp)) 125)
; 1

Answer 21

tinylisp repl, 28 bytes

(d P(q((x)(i(e(f x)x)x(P(f x

Assumes that the function f is predefined.

Try it online! (The example function is f(x) = (x*2) mod 10.)

Ungolfed

(load library)
(def P
 (lambda (x)
  (if (equal? (f x) x)
   x
   (P (f x)))))

If f(x) equals x, then x is a fixed point; return it. Otherwise, recursively look for a fixed point starting from f(x) instead of x.

Answer 22

APL NARS 65 chars

r←(f v)n;c
   c←0⋄→B
E: r←∞⋄→0
A: n←r
B: r←f n⋄c+←1⋄→E×⍳c>1e3⋄→A×⍳r≠n

v operator would return ∞ (or possibly -oo or Nan) for error, else one value x with x=f(x). In test f=floor(sqrt(abs(x))), f1=2-x, f2=c(c(c(x))) with c=x%2==0?x/2:3*x+1

  f←⌊∘√∘|
  f v 0
0
  f v 9
1
  f1←{2-⍵}
  f1 v 1
1
  f1 v ¯10
∞
  f1 v 2
∞
  c1←{0=2∣⍵:⍵÷2⋄1+3×⍵}
  f2←c1∘c1∘c1
  f2 v 1
1
  f2 v 2
2
  f2 v 7
2
  f2 v 82
4

Answer 23

x86 opcode, 8 bytes

fun:
        call    edx          ; 2B
        cmpxchg eax,    ecx  ; 3B, on 8086 use xchg and cmp instead
        jnz     fun          ; 2B
        ret                  ; 1B

Take input: ecx (value x0), edx (function address, take input from ecx, write result to eax without modifying the value of ecx and edx)

8086 opcode, 7 bytes (but slow)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

If there exists a fixed point, looping 65536 times always drive it there.
Take input: ax (initial value x0), dx (function address, take input from ax, write output to ax without modifying the value of cx and dx).
Output the fixed point in register ax.

Answer 24

Perl 5, 18 + 1 (-p)

$_=f$_ while$_^f$_

try it online

Answer 25

Java 8, 42 bytes

This takes a Function<Integer, Integer> or IntFunction<Integer> and an int or Integer (curried) and returns the fixed point.

f->i->{while(i!=(i=f.apply(i)));return i;}

Try It Online

Takes advantage of the fact that Java evaluates subexpressions from left to right (so the old i is compared to the new), a property which I was unaware of while writing this!