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

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 2

Well, here's the C quick hack:

extern double f(double x);
double g(double x)
{
  static int parity = 0;
  parity ^= 1;
  return (parity ? x : f(x));
}

However, this breaks down if you do:

a = g(4.0); // => a = 4.0, parity = 1
b = g(2.0); // => b = f(2.0), parity = 0
c = g(a);   // => c = 4.0, parity = 1
d = g(b);   // => d = f(f(2.0)), parity = 0

In general, if f is a bijection f : D → D, what you need is a function σ that partitions the domain D into A and B such that:

1. D = A ∪ B, ( the partition is total )
2. ∅ = A ∩ B (the partition is disjoint )
3. σ(a) ∈ B, f(a) ∈ A ∀ a ∈ A,
4. σ(b) ∈ A, f(b) ∈ B ∀ b ∈ B,
5. σ has an inverse σ^-1 s.t. σ(σ^-1(d)) = σ^-1(σ(d)) = d ∀ d ∈ D.
6. σ(f(d)) = f(σ(d)) ∀ d ∈ D

Then, you can define g thusly:

• g(a) = σ(f(a)) ∀ a ∈ A
• g(b) = σ^-1(b) ∀ b ∈ B

This works b/c

• ∀ a ∈ A, g(g(a)) = g(σ(f(a)). By (3), f(a) ∈ A so σ(f(a)) ∈ B so g(σ(f(a)) = σ^-1(σ(f(a))) = f(a).
• ∀ b ∈ B, g(g(b)) = g(σ^-1(b)). By (4), σ^-1(b) ∈ A so g(σ^-1(b)) = σ(f(σ^-1(b))) = f(σ(σ^-1(b))) = f(b).

You can see from Miles answer that, if we ignore 0, then the operation σ(x) = -x works for f(x) = 1/x. You can check 1-6 (for D = nonzero reals), with A being the positive numbers, and B being the negative numbers yourself. With the double precision standard, there's a +0, a -0, a +inf, and a -inf, and these can be used to make the domain total (apply to all double precision numbers, not just the nonzero).

The same method can be applied to the f(x) = -1 problem - the accepted solution there partitions the space by the remainder mod 2, using σ(x) = (x - 1), handling the zero case specially.

Answer 3

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 4

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 :) ).

Answer 5

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 6

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 7

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 8

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 9

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 10

try this

MessageBox.Show( "x = " + x );
MessageBox.Show( "value of x + x is " + ( x + x ) );
MessageBox.Show( "x =" );
MessageBox.Show( ( x + y ) + " = " + ( y + x ) );