Take the 2-minute tour ×

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

share|improve this question
I sense a flood of these coming on... –  matt b Apr 9 '09 at 1:44
Is it Interview week? Or is someone vetting interview questions? –  jeffamaphone Apr 9 '09 at 1:52
"Inspired"? It's like the same question! –  Chuck Apr 9 '09 at 1:55
what position is this for? –  Dustin Getz Apr 9 '09 at 1:56
Question to Interviewer: "and exactly how does that prove anything about your skills as a professional developer?" –  Euro Micelli Apr 9 '09 at 3:26
show 6 more comments

10 Answers

up vote 21 down vote accepted

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
share|improve this answer
Good solution - it's worth noting that it won't work for 0 of course ;) –  markt Apr 9 '09 at 3:48
Great idea using sign to store the state. The caveat (won't work for 0) is universal, and doesn't need to be mentioned here. –  Chris Lutz Apr 9 '09 at 3:49
Well if you pass 0 to this function, you will get a divide by 0 error. I think it's worth mentioning. –  markt Apr 9 '09 at 4:24
You could always handle +0 and -0 as special cases. Both exist in the double precision standard, they're just hard to distinguish in C. Map +0 to -inf and -0 to +inf. –  rampion Apr 9 '09 at 11:55
actually, this won't give divide by zero error, at least not in C/C++/Java. it will give inf, which is the correct answer. it fails for -0.0f, because that is considered equal to 0. it works with -inf as input, but fails for +inf. if you changed the condition to "x > 0 || x is +0.0f (but not -0.0f!)" it would work, but alas i don't know how to actually write that. :-( –  Kip Aug 27 '09 at 3:08
show 3 more comments

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.

share|improve this answer
Actually, that's pretty sneaky (in a single-threaded sort of way :-). –  paxdiablo Apr 9 '09 at 2:22
@Pax maybe he can use __thread static int parity = 0; –  Unknown Apr 9 '09 at 2:48
yeah, but it still falls down if I do x = g(3.0), y = g(4.0), z = g(x), a = g(y) => z = 3.0, a = 4.0. I'd need a better data structure for multiple values. –  rampion Apr 9 '09 at 2:58
I never thought the first time I would see first order logic again would be on a community website. –  Unknown Apr 9 '09 at 4:24
+1 for math verbosity! –  Anthony Apr 12 '09 at 19:59
add comment

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

function f(x)
   if (typeof x == "function")
       return x();
       return function () {return 1/x;}
share|improve this answer
I think that is an elegant solution. I wonder though if any math/language gurus can tell us a magic algorithm to decompose functions like this. –  Unknown Apr 9 '09 at 2:41
Works for defining g as well... –  Brian Campbell Apr 9 '09 at 2:50
Does this actually work? It seems to depend on the evaluation rules of the language. Usually, I'd assume that all arguments are evaluated first, and only their return value passed to the outer function call. –  Svante Apr 9 '09 at 3:21
Svante: the return value of the inner f(x) call is a function. –  Miles Apr 9 '09 at 3:24
It's javascript, and you bet it works. –  Joel Coehoorn Apr 9 '09 at 3:33
show 1 more comment

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.

share|improve this answer
add comment

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

    Flag = $100000000;

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

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

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

share|improve this answer
add comment

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.

share|improve this answer
Actually a really nice try. However, I get f(f(x)) = -1/x and unfortunately solving for some correct a,b,c,d always gives some complex values. –  Accipitridae Aug 22 '09 at 9:34
True - apologies! Should have realised since composition of these transformations is matrix multiplication of 2x2 matrices and therefore f(f(x))=1/x implies that there is a 2x2 real matrix A s.t A^2 = {{0,1},{1,0}} taking determinants we have (det A)^2 = -1, so no real solution! –  Ivan Feb 16 '11 at 12:32
add comment

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{
    bool operator==(double) const{
        return true

X g(X x){
    return X();
share|improve this answer
add comment

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

share|improve this answer
add comment

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;
share|improve this answer
add comment

try this

MessageBox.Show( "x = " + x );
MessageBox.Show( "value of x + x is " + ( x + x ) );
MessageBox.Show( "x =" );
MessageBox.Show( ( x + y ) + " = " + ( y + x ) );
share|improve this answer
This answer lacks of a description and code indention (prepend four spaces to each code line) in its current version. Please consider editing it. –  Matthias Dec 8 '12 at 9:06
add comment

Your Answer


