Fibonacci using 1 variable

Question

I was asked the following question in an interview:

Is there any way in which Fibonacci series can be generated using only 1 variable ?

I didn't know what to answer. What should I have said?

Answer 1

Yes, but you still need to remember 2 values. You could take a 64-bit variable and use it as 2 32-bit vars.

Answer 2

Sure, using recursion:

public class Test {

    public static int fib(int n) {
        return n < 2 ? n : fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        for(int i = 0; i <= 10; i++) {
            System.out.print(fib(i)+", ");
        }
        System.out.println("...");
    }
}

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Answer 3

The answer is "yes", but maybe you could be more specific.

The first example I could think of, using double recursion (that leads to an exponential complexity, not recommended):

int fib(int a) {
  if (a < 2) {
    return 1
  } else {
    return fib(a-1) + fib(a-2);
  }
}

Assuming a >= 0 (you could add a check for that).

(Edit - used the wrong convention of F(0) undefined, F(1) = 1)

Answer 4

Yes, you can used the closed-form expression:

where

You can calculate the expression using a double and round the result to the nearest integer. Because of the finite precision of floating point arithmetic this formula will give a wrong answer for large enough n, but I think it will work in the case when the result fits into a Java 32-bit integer.

Answer 5

Up to a point, yes (though in C, you could convert it to Java - it would look much uglier).

#include <stdio.h>
#include <stdlib.h>

int main (void) {
    unsigned long i = 1;
    printf ("0\n");
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
        printf ("%d\n", i & 0xffff);
        i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
    }
    return 0;
}

which produces:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657

:-)

The real question, of course, is: Why would you want to?

Answer 6

After the initial 1 1, it is in theory possible to generate one value from the previous one (until machine precision comes around to bite you) via:

f = Math.round(f * PHI)

where PHI is the constant defined in another comment:

static final double PHI = (1 + Math.sqrt(5))/2;

Answer 7

You can always do something like this:

    String theOneVar = "100;0;1";
    while (true) {
        if (theOneVar.split(";")[0].equals("0")) break;
        System.out.println(theOneVar.split(";")[1]);
        theOneVar = String.format("%s;%s;%s",
            Integer.parseInt(theOneVar.split(";")[0]) - 1,
            theOneVar.split(";")[2],
            new BigInteger(theOneVar.split(";")[1]).add(
                new BigInteger(theOneVar.split(";")[2])
            )
        );
    }

This prints (as seen on ideone.com):

0
1
1
2
3
5
8
13
:
:
83621143489848422977
135301852344706746049
218922995834555169026

This uses only one explicit variable, and it's essentially a linear non-recursive algorithm. It needs to be said that this is an abuse of String, though.

Answer 8

Here's an example in C#. Shows the first 100 terms. The ratio between terms in the Fibonacci approaches the golden ratio (1.618033...), so a single variable approach simply requires a multiplication by a constant for each term.

Yay math!

double fib = 1;
for (int i = 0; i < 100; i++)
{
    Console.WriteLine("" + fib);
    fib = Math.Round(fib *= 1.6180339887d);
}

Answer 9

So this is evil, but:

static String fibRecord = "x;";

static int nextFib() {
  try {
    return fibRecord.indexOf(';');
  } finally {
    fibRecord = fibRecord.replaceAll("(x*);(x*)", "$1$2;$1");
  }
}

public static void main(String[] ignored) {
  for (int i=0; i < 30; i++) {
    System.out.println(nextFib());
  }
}

My machine here starts to fall over around the 38th Fibonacci number.