106

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?

23
  • 113
    Why? It's readable, the intent is very clear, and it's not expensive. Why change it to some "clever" bit pattern matching that is harder to understand and does not clearly identify the intent?
    – D Stanley
    Apr 1, 2016 at 15:03
  • 9
    This isn't really fibonaci right?
    – n8wrl
    Apr 1, 2016 at 15:05
  • 9
    fibonaci adds the two previous values. Did you mean fibn(N-1) + fibn(N-2) instead of N * fibn(N-1)?
    – juharr
    Apr 1, 2016 at 15:06
  • 47
    I'm all for shaving off nanoseconds, but if you've got a simple comparison in a method that uses recursion, why spend effort on the efficiency of the comparison, and leave the recursion there?
    – Jon Hanna
    Apr 1, 2016 at 15:06
  • 26
    You use a recursive way to calculate Fabonacci number, then you want to improve the performance? Why not change it into a loop? or use fast power?
    – notbad
    Apr 1, 2016 at 17:10

14 Answers 14

217

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)
11
  • 6
    Don't forget (x & ~1) == 0 Apr 2, 2016 at 0:03
  • 73
    But don't bet on any particular one of them being "more efficient". gcc actually generates less code for x == 0 || x == 1 than for (x & ~1) == 0 or (x | 1) == 1. For the first one it's smart enough to recognize it as being equivalent to x <= 1 and outputs a simple cmpl; setbe. The others confuse it and make it generate worse code.
    – hobbs
    Apr 2, 2016 at 3:13
  • 14
    x <= 1 or x < 2 is simpler.
    – gnasher729
    Apr 2, 2016 at 6:56
  • 9
    @Kevin True for C++, because that standard tries really, really hard to make it impossible to write compliant code. Luckily this is a question about C# ;)
    – Voo
    Apr 2, 2016 at 10:01
  • 5
    Most modern compilers can already optimize comparisons like this although I don't know how smart C# compiler and .NET JITter are. Only a single comparison is needed in the real code
    – phuclv
    Apr 2, 2016 at 11:39
78

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);
1
  • 13
    If it were Code Golf, it'd be return N<2?1:f(N-1)+f(n-2). :P Apr 2, 2016 at 22:00
36

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

9
  • I like it! Thanks. Apr 1, 2016 at 15:12
  • 15
    1 less character: (N|1)==1
    – Matt
    Apr 1, 2016 at 15:56
  • 1
    @atk 3|1 is 3 because b0011|b0001 is b0011
    – René Vogt
    Apr 1, 2016 at 17:45
  • 3
    @atk This is bitwise or, not logical or. There is no shortcircuiting.
    – isaacg
    Apr 1, 2016 at 17:55
  • 2
    @Hoten Correct, but Matt said 1 less character, not 1 less operation.
    – Ivan Stoev
    Apr 1, 2016 at 18:25
21

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.

14

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.

8
  • 1
    Not only avoiding the exponential growing tree, but you also avoid the potential branching of the ternary operator which could clog up modern CPU pipelines. Apr 2, 2016 at 20:21
  • 2
    Your 'way faster' code won't work in C# because uint is not implicitly castable to bool, and the question is specifically tagged as C#.
    – Pharap
    Apr 3, 2016 at 5:43
  • 1
    @pharap then do --N != 0 instead. The point is that something O(n) is preferable to O(fibn(n)). Apr 3, 2016 at 6:13
  • 1
    to expand on @MatthewGunn's point, O(fib(n)) is O(phi^n) (see this derivation stackoverflow.com/a/360773/2788187) Apr 4, 2016 at 15:39
  • @RenéVogt I'm not a c# developer. I was mostly trying to comment on the complete absurdity of a O(fibn(N)) algorithm. Does it compile now? (I added != 0 since c# doesn't treat non-zero results as true.) It works (and worked) in straight c if you replace uint with something standard like uint64_t. Apr 5, 2016 at 22:01
11

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.

6
  • 4
    @CatthalMF: but the outcome is the same, because 1 * fibn(0) = 1 * 1 = 1 Apr 1, 2016 at 15:20
  • 3
    Isn't your function calculating factorial, not fibonacci?
    – Barmar
    Apr 5, 2016 at 18:33
  • 2
    @Barmar yes, indeed that's factorial, because that was the original question Apr 5, 2016 at 20:39
  • 3
    Might be best not to call it fibn then
    – pie3636
    Aug 11, 2016 at 12:50
  • 1
    @pie3636 i called it fibn because that's how it was called in the original question and I didn't update the answer later on Aug 11, 2016 at 17:59
6

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);
}
6
  • Does it even matter if it's signed or unsigned? The algorithm produces infinite recursion with negative inputs, so there's no harm in treating them equivalent to 0 or 1.
    – Barmar
    Apr 5, 2016 at 18:36
  • @Barmar sure it matters, especially in this specific case. The OP asked if he could simplify exactly (N == 0 || N == 1). You know it won't be less than 0 (because then it would be signed!), and the maximum could be 1. N <= 1 simplifies it. I guess the unsigned type is not guaranteed, but that should be handled elsewhere, I'd say.
    – james
    Apr 17, 2019 at 18:56
  • My point is that if it were declared int N, and you kept the original condition, it would recurse infinitely when N is negative with his original condition. Since that's undefined behavior, we don't actually need to worry about it. So we can assume that N is non-negative, regardless of the declaration.
    – Barmar
    Apr 17, 2019 at 19:06
  • Or we can do anything we want with negative inputs, including treating them as the base case of the recursion.
    – Barmar
    Apr 17, 2019 at 19:07
  • @Barmar pretty sure uint will always be converted to unsigned if you try to set to negative
    – james
    Apr 17, 2019 at 19:58
6

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.

5

for N is uint, just use

N <= 1
1
  • Exactly what I was thinking; N is uint! This should be the answer, really. May 24, 2018 at 19:52
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..

enter image description here

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);
    }
}
6
  • 1
    The advantage of your solution is that it only gets calculated when needed. Best would be a lookup table. alternative bonus: f(n-1) = someCalcOf( f(n-2) ), so not the complete re-run is needed.
    – Karsten
    Apr 6, 2016 at 7:58
  • @Karsten I've added enough values for the switch to create a lookup table for it. I'm not sure on how the alternative bonus works.
    – Khaled.K
    Apr 6, 2016 at 10:18
  • 1
    How does this answer the question?
    – Clark Kent
    Apr 6, 2016 at 12:30
  • @SaviourSelf it comes down to a lookup table, and there's the visual aspect explained in the answer. stackoverflow.com/a/395965/2128327
    – Khaled.K
    Apr 6, 2016 at 15:10
  • Why would you use a switch when you can have an array of answers?
    – Nayuki
    May 18, 2016 at 6:11
1

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);
5
  • 2
    How is that shorter than the original?
    – MCMastery
    Apr 1, 2016 at 20:33
  • 2
    @MCMastery Its not shorter. As I mentioned its only better if the original return type is an int32 and he is selecting from a large set of valid numbers. Insead of having to write (N == -1 || N == 0 || N == 1 || N == 2)
    – CathalMF
    Apr 2, 2016 at 12:13
  • 1
    OP's reasons seems to be related to optimization. This is a bad idea for several reasons: 1) instantiating a new object inside each recursive call is a really bad idea, 2) List.Contains is O(n), 3) simply making two comparisons instead (N > -3 && N < 3) would give shorter and more readable code.
    – vgru
    Apr 3, 2016 at 8:42
  • @Groo And what if the values were -10, -2, 5, 7, 13
    – CathalMF
    Apr 3, 2016 at 17:36
  • It's not what OP asked. But anyway, you still 1) wouldn't want to create a new instance in each call, 2) would better use a (single) hashset instead, 3) for a specific problem, you would also be able to optimize the hash function to be pure, or even use cleverly arranged bitwise operations like suggested in other answers.
    – vgru
    Apr 3, 2016 at 17:41
0

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);
-2

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#

5
  • 4
    Not sure why this got upvoted. Even cursory attempting this as uint n = 1; if (n == !!n) { } gives Operator '!' cannot be applied to operand of type 'uint' on the !n in C#. Just because something works in C doesn't mean it works in C#; even #include <stdio.h> doesn't work in C#, because C# doesn't have the "include" preprocessor directive. The languages are more different than are C and C++.
    – user
    Apr 4, 2016 at 7:41
  • 2
    Oh. Okay. I'm sorry :( Apr 4, 2016 at 15:48
  • @OneNormalNight (x==!!x) How this will work. Consider my input is 5. (5 == !!5). It will give result as true Jun 2, 2016 at 18:29
  • 1
    @VinothKumar !!5 evaluates to 1. (5 == !!5) evaluates (5 == 1) which evaluates to false. Jun 2, 2016 at 19:14
  • @OneNormalNight yeah i got it now. !(5) gives 1 again applied it gives 0. Not 1. Jun 3, 2016 at 17:35
-3

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.