Is it possible to simplify (x == 0 || x == 1) into a single operation?

Question

So I was trying to write the nth number in the Fibonacci sequence in as compact a function as possible:

public uint fibn ( uint N ) 
{
   return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}

But I'm wondering if I can make this even more compact and efficient by changing

(N == 0 || N == 1)

into a single comparison. Is there some fancy bit shift operation that can do this?

Answer 1

The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it. There are two types of starting points: (0,1,1,2,..) and (1,1,2,3).

-----------------------------------------
Position(N)| Value type 1 | Value type 2
-----------------------------------------  
1          |  0           |   1
2          |  1           |   1
3          |  1           |   2
4          |  2           |   3
5          |  3           |   5
6          |  5           |   8
7          |  8           |   13
-----------------------------------------

The position N in this case starts from 1, it is not 0-based as an array index.

Using C# 6 Expression-body feature and Dmitry's suggestion about ternary operator we can write a one line function with correct calculation for the type 1:

public uint fibn(uint N) => N<3? N-1: fibn(N-1)+fibn(N-2);

and for the type 2:

public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);

Answer 2

for N is uint, just use

N <= 1

Answer 3

How to do it with bitshift

If you want to use bitshift and make the code somewhat obscure (but short) you could do:

public uint fibn ( uint N ) {
   return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}

For an unsigned integer N in the language c, N>>1 tosses off the low order bit. If that result is non-zero, it implies N is greater than 1.

Note: this algorithm is horribly inefficient as it needlessly recalculates values in the sequence that have already been calculated.

Something WAY WAY faster

Calculate it one pass rather than implicitly building a fibonaci(N) sized tree:

uint faster_fibn(uint N) { //requires N > 1 to work
  uint a = 1, b = 1, c = 1;
  while(--N != 0) {
    c = b + a;
    a = b;
    b = c;
  }
  return c;
}

As some people have mentioned, it doesn't take long to overflow even a 64 bit unsigned integer. Depending on how large you're trying to go, you'll need to use arbitrary precision integers.

Answer 4

Here's my solution, there's not much in optimizing this simple function, on the other hand what I'm offering here is readability as a mathematical definition of the recursive function.

public uint fibn(uint N) 
{
    switch(N)
    {
        case  0: return 1;

        case  1: return 1;

        default: return fibn(N-1) + fibn(N-2);
    }
}

The mathematical definition of Fibonacci number in a similar fashion..

Taking it further to force the switch case to build a lookup table.

public uint fibn(uint N) 
{
    switch(N)
    {
        case  0: return 1;
        case  1: return 1;
        case  2: return 2;
        case  3: return 3;
        case  4: return 5;
        case  5: return 8;
        case  6: return 13;
        case  7: return 21;
        case  8: return 34;
        case  9: return 55;
        case 10: return 89;
        case 11: return 144;
        case 12: return 233;
        case 13: return 377;
        case 14: return 610;
        case 15: return 987;
        case 16: return 1597;
        case 17: return 2584;
        case 18: return 4181;
        case 19: return 6765;
        case 20: return 10946;
        case 21: return 17711;
        case 22: return 28657;
        case 23: return 46368;
        case 24: return 75025;
        case 25: return 121393;
        case 26: return 196418;
        case 27: return 317811;
        case 28: return 514229;
        case 29: return 832040;
        case 30: return 1346269;
        case 31: return 2178309;
        case 32: return 3524578;
        case 33: return 5702887;
        case 34: return 9227465;
        case 35: return 14930352;
        case 36: return 24157817;
        case 37: return 39088169;
        case 38: return 63245986;
        case 39: return 102334155;
        case 40: return 165580141;
        case 41: return 267914296;
        case 42: return 433494437;
        case 43: return 701408733;
        case 44: return 1134903170;
        case 45: return 1836311903;
        case 46: return 2971215073;

        default: return fibn(N-1) + fibn(N-2);
    }
}

Answer 5

So I created a List of these special integers and checked if N pertains to it.

static List<uint> ints = new List<uint> { 0, 1 };

public uint fibn(uint N) 
{
   return ints.Contains(N) ? 1 : fibn(N-1) + fibn(N-2);
}

You could also use an extension method for different purposes where Contains is called only once (e. g. when your application is starting and loading data). This provides a clearer style and clarifies the primary relation to your value (N):

static class ObjectHelper
{
    public static bool PertainsTo<T>(this T obj, IEnumerable<T> enumerable)
    {
        return (enumerable is List<T> ? (List<T>) enumerable : enumerable.ToList()).Contains(obj);
    }
}

Apply it:

N.PertainsTo(ints)

This might be not the fastest way to do it, but to me, it appears to be a better style.

Answer 6

There are a number of ways to implement your arithmetic test using bitwise arithmetic. Your expression:

• x == 0 || x == 1

is logically equivalent to each one of these:

• (x & 1) == x
• (x & ~1) == 0
• (x | 1) == 1
• (~x | 1) == (uint)-1
• x >> 1 == 0

Bonus:

• x * x == x (the proof takes a bit of effort)

But practically speaking, these forms are the most readable, and the tiny difference in performance isn't really worth using bitwise arithmetic:

• x == 0 || x == 1
• x <= 1 (because x is an unsigned integer)
• x < 2 (because x is an unsigned integer)

Answer 7

Bit late to the party, but you could also do (x==!!x)

!!x converts the a value to 1 if it's not 0, and leaves it at 0 if it is.
I use this kinda thing in C obfuscation a lot.

Note: This is C, not sure if it works in C#

Answer 8

If what you want to do is to make the function more efficient, then use a lookup table. The lookup table is surprisingly small at only 47 entries - the next entry would overflow a 32-bit unsigned integer. It also of course makes the function trivial to write.

class Sequences
{
    // Store the complete list of values that will fit in a 32-bit unsigned integer without overflow.
    private static readonly uint[] FibonacciSequence = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
        233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
        317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
        63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073
    };

    public uint fibn(uint N)
    {
        return FibonacciSequence[N];
    }
}

You can obviously do the same thing for factorials.

Answer 9

Disclaimer: I don't know C#, and didn't test this code:

But I'm wondering if I can make this even more compact and efficient by changing [...] into a single comparison...

No need for bitshifting or such, this uses just one comparison, and it should be a lot more efficient ( O(n) vs O(2^n) I think? ). The body of the function is more compact, though it ends being a bit longer with the declaration.

(To remove overhead from recursion, there's the iterative version, as in Mathew Gunn's answer)

public uint fibn ( uint N, uint B=1, uint A=0 ) 
{
    return N == 0 ? A : fibn( N--, A+B, B );
}

                     fibn( 5 ) =
                     fibn( 5,   1,   0 ) =
return 5  == 0 ? 0 : fibn( 5--, 0+1, 1 ) =
                     fibn( 4,   1,   1 ) =
return 4  == 0 ? 1 : fibn( 4--, 1+1, 1 ) =
                     fibn( 3,   2,   1 ) =
return 3  == 0 ? 1 : fibn( 3--, 1+2, 2 ) =
                     fibn( 2,   3,   2 ) =
return 2  == 0 ? 2 : fibn( 2--, 2+3, 3 ) =
                     fibn( 1,   5,   3 ) =
return 1  == 0 ? 3 : fibn( 1--, 3+5, 5 ) =
                     fibn( 0,   8,   5 ) =
return 0  == 0 ? 5 : fibn( 0--, 5+8, 8 ) =
                 5
fibn(5)=5

PS: This is a common functional pattern for iteration with accumulators. If you replace N-- with N-1 you're effectively using no mutation, which makes it usable in a pure functional approach.

Answer 10

As you use an uint, which can't get negative, you could check if n < 2

EDIT

Or for that special function case you could write it as follows:

public uint fibn(uint N)
    return (N == 0) ? 1 : N * fibn(N-1);
}

which will lead to the same result, of course at the cost of an additional recursion step.

Answer 11

You could also check that all other bits are 0 like this:

return (N & ~1) == 0 ? 1 : N * fibn(N-1);

For completeness thanks to Matt the even better solution:

return (N | 1) == 1 ? 1 : N * fibn(N-1);

In both cases you need to take care of the parenthesis because bitwise operators have lower priority than ==.

Answer 12

Simply check to see if N is <= 1 since you know N is unsigned there can only be 2 conditions that N <= 1 that results in TRUE: 0 and 1

public uint fibn ( uint N ) 
{
   return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}

Answer 13

Since argument is uint (unsigned) you can put

  return (N <= 1) ? 1 : N * fibn(N-1);

Less readable (IMHO) but if you count each character (Code Golf or alike)

  return N < 2 ? 1 : N * fibn(N-1);

Edit: for your edited question:

  return (N <= 1) ? 1 : fibn(N-1) + fibn(N-2);

Or

  return N < 2 ? 1 : fibn(N-1) + fibn(N-2);

Answer 14

Dmitry's answer is best but if it was an Int32 return type and you had a larger set of integers to choose from you could do this.

return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);