Find a Fixed Point

Question

Given an integer \$x_1\$ and some black box function \$f: ℤ → ℤ\$ find a fixed point of \$f\$ in the sequence defined by \$x_{k+1} := f(x_k)\$.

Details

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

For instance if \$f(x) = \text{round}(\frac{x}{\pi})\$ and we have a starting point \$x_1 = 10\$ then we get \$x_2 = f(x_1) = f(10) = 3\$, then \$x_3 = f(x_2) = f(3) = 1\$, then \$x_4 = f(x_3) = f(1) = 0\$, and finally \$x_5 = f(x_4) = 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

Mathematica, 11 bytes

#2//.x_:>#&

Try it online!

Mathematica, 10 bytes

FixedPoint

Try it online!

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

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

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 10

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

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 14

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 15

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

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 21

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 22

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 23

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!

Answer 24

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 25

J, 3 bytes

^:_

Try it online!

When a conjunction in J is missing an operand, it becomes an adjective. This program produces an adjective which takes as an argument a verb. ^: is the power or "repeat" verb, and the idiom f^:_, that is, f repeated infinitely, is J's limit application, which exactly solves this challenge:

An infinite power n produces the limit of the application of u .

Answer 26

dc, 30 bytes

[pq][Smrd3Rd3Rxd3R=mLmlmx]dsmx

Try it online!

Takes as input the function in the form of a macro and initial value on the stack(pushed in that order). Prints the fixed point.

Answer 27

Perl 5, 18 + 1 (-p)

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

try it online

Answer 28

Vyxal, 1 byte

Ẋ

Try it Online!

Builtin lol

Answer 29

J-uby, 3 bytes

J-uby has a built-in operator for this:

:!~

Attempt This Online!

Answer 30

Japt, 14 bytes

gOvV
¥W?U:ßW

Try it

Japt doesn't have any built-in "repeat until the output is constant" functionality, or the ability to take functions directly as input. This program takes x as the first input, and a string defining a Japt function as the second input.

Explanation:

/n      # Store first input as U

/n      # Store second input as V

gOvV
 OvV    # Interpret V as Japt code
g       # Apply that function to U
        # Store the result as W

¥W      # Check whether U and W are the same
  ?U    # If they are, output U
    :ßW # Otherwise repeat the program with W and V as the inputs

A theoretical alternative would work if the function were assumed to already be stored in V, but there isn't really a good way to actually accomplish that in Japt so it's not really a reasonable input method.