Interview question: f(f(x)) == 1/x

Question

Design a function f such that:

f(f(x)) == 1/x

Where x is a 32 bit float

Or how about

Given a function f, find a function g such that

f(x) == g(g(x))

---

See Also

Interview question: f(f(n)) == -n

Answer 1

I like the javascript/lambda suggestion from the earlier thread:

function f(x)
{
   if (typeof x == "function")
       return x();
   else
       return function () {return 1/x;}
}

Answer 2

Again, it's specified as a 32-bit number. Make the return have more bits, use them to carry your state information between calls.

Const
    Flag = $100000000;

Function F(X : 32bit) : 64bit;

Begin
    If (64BitInt(X) And Flag) > 0 then
        Result := g(32bit(X))
    Else
        Result := 32BitInt(X) Or Flag;
End;

for any function g and any 32-bit datatype 32bit.

Answer 3

For the first part: this one is more trivial than f(f(x)) = -x, IMO:

float f(float x)
{
    return x >= 0 ? -1.0/x : -x;
}

The second part is an interesting question and an obvious generalization of the original question that this question was based on. There are two basic approaches:

• a numerical method, such that x ≠ f(x) ≠ f(f(x)), which I believe was more in the spirit of the original question, but I don't think is possible in the general case
• a method that involves g(g(x)) invoking f exactly once

Answer 4

The other solutions hint at needing extra state. Here's a more mathematical justification of that:

let f(x) = 1/(x^i)= x^-i

(where ^ denotes exponent, and i is the imaginary constant sqrt(-1) )

f(f(x)) = (x^-i)^-i) = x^(-i*-i) = x^(-1) = 1/x

So a solution exists for complex numbers. I don't know if there is a general solution sticking strictly to Real numbers.

Answer 5

Based on this answer, a solution to the generalized version (as a Perl one-liner):

sub g { $_[0] > 0 ? -f($_[0]) : -$_[0] }

Should always flip the variable's sign (a.k.a. state) twice, and should always call f() only once. For those languages not fortunate enough for Perl's implicit returns, just pop in a return before the { and you're good.

This solution works as long as f() does not change the variable's sign. In that case, it returns the original result (for negative numbers) or the result of f(f()) (for positive numbers). An alternative could store the variable's state in even/odd like the answers to the previous question, but then it breaks if f() changes (or can change) the variable's value. A better answer, as has been said, is the lambda solution. Here is a similar but different solution in Perl (uses references, but same concept):

sub g {
  if(ref $_[0]) {
    return ${$_[0]};
  } else {
    local $var = f($_[0]);
    return \$var;
  }
}

Note: This is tested, and does not work. It always returns a reference to a scalar (and it's always the same reference). I've tried a few things, but this code shows the general idea, and though my implementation is wrong and the approach may even be flawed, it's a step in the right direction. With a few tricks, you could even use a string:

use String::Util qw(looks_like_number);

sub g {
  return "s" . f($_[0]) if looks_like_number $_[0];
  return substr $_[0], 1;
}

Answer 6

There is another way to solve this and it uses the concept of fractional linear transformations. These are functions that send x->(ax+b)/(cx+d) where a,b,c,d are real numbers.

For example you can prove using some algebra that if f is defined by f(x)=(ax+1)(-x+d) where a^2=d^2=1 and a+d<>0 then f(f(x))=1/x for all real x. Choosing a=1,d=1, this give a solution to the problem in C++:

float f(float x)
{
    return (x+1)/(-x+1);
}

The proof is f(f(x))=f((x+1)/(-x+1))=((x+1)/(-x+1)+1)/(-(x+1)/(-x+1)+1) = (2/(1-x))/(2x/(1-x))=1/x on cancelling (1-x).

This doesn't work for x=1 or x=0 unless we allow an "infinite" value to be defined that satisfies 1/inf = 0, 1/0 = inf.

Answer 7

a C++ solution for g(g(x)) == f(x):

struct X{
    double val;
};

X g(double x){
    X ret = {x};
    return ret;
}

double g(X x){
    return f(x.val);
}

here is one a bit shorter version (i like this one better :-) )

struct X{
    X(double){}
    bool operator==(double) const{
        return true
    }
};

X g(X x){
    return X();
}

Answer 8

If f(x) == g(g(x)), then g is known as the functional square root of f. I don't think there's closed form in general even if you allow x to be complex (you may want to go to mathoverflow to discuss :) ).