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

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 2

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 3

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 4

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