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?

Jesse C. Slicer
  • 19,901
  • 3
  • 68
  • 87
user6048670
  • 2,861
  • 4
  • 16
  • 20
  • 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 01 '16 at 15:03
  • 9
    This isn't really fibonaci right? – n8wrl Apr 01 '16 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 01 '16 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 01 '16 at 15:06
  • 2
    fibonacci(0) = 0. Also it doesn't multiply, but sum – Matteo Umili Apr 01 '16 at 15:07
  • 1
    @codroipo depends on how you want to index (zero based or one based) and typically the sequence begins with two ones, but it could start with a zero and a one, and you can work your way backwards into alternating negative numbers if you really want to. – juharr Apr 01 '16 at 15:09
  • 2
    @juharr: no, fibonacci sequence is quite well defined as `f(1) = f(2) = 1` and `f(n) = f(n-1) + f(n-2)` for all `n>2`. If you claim your function to calculate the fibonacci sequence, you have to follow these rules. – derpirscher Apr 01 '16 at 15:17
  • 1
    @derpirscher No it's defined as f(n) = f(n-1) + f(n-2). Where you want to start is up to you as the sequence can be defined in both directions `…,−8,5,−3,2,−1,1,0,1,1,2,3,5,8,…` You can index those numbers however you choose. The two most common are for f(0) = 0 and f(1) = 1 or if you want to start with 1,1 then it would be f(0) = 1 and f(1) = 1. And then there's the additional confusion of indexing starting at 0 or 1. – juharr Apr 01 '16 at 15:20
  • 2
    @n8wrl Sorry, I accidentally wrote the formula for Factorial, but since everyone has answered based on that, I'll leave it up – user6048670 Apr 01 '16 at 15:22
  • 2
    @juharr Every math book I know sets the seeds for the fibonacci sequence as either `f(1) = f(2) = 1` or `f(0) = 0 and f(1) = 1`. So you may have the same recursion rule, but it's not a fibonacci seuqence if you have different seeds – derpirscher Apr 01 '16 at 15:27
  • 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 01 '16 at 17:10
  • 1
    Or trade memory for speed an use a lookup table for the first 10,000 values. :-P – Gort the Robot Apr 01 '16 at 22:27
  • `(N == 0 || N == 1)` can be changed to compact form `N >> 1`, but I cannot guarantee, if it would be efficient. `public uint fibn ( uint N ) { return N >> 1 ? 1 : fibn(N-1) + fibn(N-2); }` – Hitesh Apr 02 '16 at 14:01
  • 1
    But wait! Doesn't [`fibonacci(0)=0`](https://oeis.org/A000045)? – Cyoce Apr 02 '16 at 22:35
  • 2
    The most optimal solution would be to use a loop instead of making the function recursive. It's much cheaper for the code to just jump to the top of a loop rather than having to mess around with return addresses and the stack. Most tail-call optimising compilers would spot this and rewrite your code as a loop, [but C# specifically won't do tail-call optimisation.](http://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion) – Pharap Apr 03 '16 at 05:47
  • 1
    You know there's a [closed form expression](https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression) right? And that the double recursive solution is about as slow as it gets? Why are you doing this?? – Boris the Spider Apr 03 '16 at 13:34
  • @Pharap the optimal solution is likely to use the closed form express, which would be `O(1)`, rather than recurring _or_ looping... – Boris the Spider Apr 03 '16 at 13:35
  • @BoristheSpider: You still need a loop to use the closed form to an arbitrary precision. – Ry- Apr 04 '16 at 03:17
  • 5
    Was `N < 2` not obvious? – user253751 Apr 04 '16 at 04:37
  • @BoristheSpider A) Are you sure you meant to link to the mobile version of wikipedia? B) Waaay too many maths symbols for me to understand. – Pharap Apr 04 '16 at 13:05
  • 2
    @Pharap you caught me; I was using my phone. Programming is largely maths, it's worth trying to grasp the basics. The main point is that you can calculate the Nth member if the Fibonnaci sequence with a simple formula - you don't need to calculate the whole sequence. – Boris the Spider Apr 04 '16 at 13:14
  • @BoristheSpider It's still possible to be a good programmer and not get on with mathematical notation. Show me an implementation in C#, C++, Java, Lua, Python, Haskell... etc and I'd be fine with it, it's just mathematical notation I don't get on with. Also 'the basics' is relative, I'm fine with things like functions, tuples, vectors and (to a degree) matrices (though more from a programming perspective than a mathematics perspective), even though they don't teach those at GCSE level (the highest level maths qualification I have is GCSE). – Pharap Apr 04 '16 at 13:38
  • @user6048670 Do you want _compact_ code (as tiny as possible) or do you want fast code? Asking because that you have is really really slow... – ST3 Apr 19 '16 at 14:29

14 Answers14

216

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)
Nayuki
  • 17,911
  • 6
  • 53
  • 80
  • 6
    Don't forget `(x & ~1) == 0` – Lee Daniel Crocker Apr 02 '16 at 00: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 02 '16 at 03:13
  • 14
    x <= 1 or x < 2 is simpler. – gnasher729 Apr 02 '16 at 06:56
  • `(uint) -1` is not guaranteed to be `UINT_MAX`. The standard does not require twos complement. – Kevin Apr 02 '16 at 07:08
  • 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 02 '16 at 10:01
  • 5
    Most modern compilers can already [optimize comparisons like this](https://godbolt.org/g/R1pzEu) 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 02 '16 at 11:39
  • 1
    @Kevin for those cases you can use the compliant variants `(unsigned)0-(unsigned)1` or `~(unsigned)0`. The C standard doesnt promise that twos complement is in use for signed integers, but it does guarantee that the unsigned integers wrap modulo N. – Steve Cox Apr 02 '16 at 13:33
  • 4
    @Kevin: The result of a conversion does not depend on the representation. If signed is converted to unsigned, and the value cannot be represented (-1 cannot be represented), then the maximum value + 1 is added, which gives UINT_MAX. Doesn't matter if it is one's complement or signed-magnitude or whatever. – gnasher729 Apr 02 '16 at 14:13
  • 1
    If a particular approach *was* faster, you could always encapsulate it in a method called `IsZeroOrOne` to mitigate the readability hit. I'm sure the JIT would inline it for you. – Blorgbeard Apr 05 '16 at 22:27
  • 1
    Not very useful bonus: `N - 2 > N`, because unsigned integers wrap. – gengkev Apr 06 '16 at 21:52
  • 1
    @Pieter888 Multiplication isn't particularly efficient, though – Nayuki Apr 12 '16 at 16:20
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);
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
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 ==.

Community
  • 1
  • 1
René Vogt
  • 43,056
  • 14
  • 77
  • 99
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.

Adam
  • 882
  • 5
  • 10
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.

Matthew Gunn
  • 4,451
  • 1
  • 12
  • 30
  • 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. – mathreadler Apr 02 '16 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 03 '16 at 05:43
  • 1
    @pharap then do `--N != 0` instead. The point is that something O(n) is preferable to O(fibn(n)). – Matthew Gunn Apr 03 '16 at 06:13
  • 1
    to expand on @MatthewGunn's point, O(fib(n)) is O(phi^n) (see this derivation http://stackoverflow.com/a/360773/2788187) – Connor Clark Apr 04 '16 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. – Matthew Gunn Apr 05 '16 at 22:01
  • @RenéVogt I think some programmers delight in finding esoteric ways to check whether `x < 2`. There's also great humor in that the original question writer did not realize his/her condition was `x < 2`. – Matthew Gunn Apr 05 '16 at 22:18
  • The calculation can be optimised further (if not WAY WAY further) by seeing the steps operating on ℕ² as matrix multiplications so that fib(n) involves taking a matrix power, optimising that to the minimal number of multiplications needed (c.f. the binary form of the exponent) and optimising away the 2x2 matrix calculations because of redundancy in the form of ((01)(11))ⁿ — see _Programming: The Derivation of Algorithms_ (Kaldewaij / Prentice Hall). Of course it only makes much sense in arbitrary precision (`BigInteger`) arithmetic. – PJTraill Apr 06 '16 at 22:32
  • @PJTraill Yeah, you'll need arbitrary precision arithmetic for anything interesting because it doesn't take long at all to overflow a uint64_t going through the fibonaci sequence. – Matthew Gunn Apr 06 '16 at 22:38
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.

Hatchet
  • 5,320
  • 1
  • 30
  • 42
derpirscher
  • 14,418
  • 3
  • 18
  • 35
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);
}
james
  • 26,141
  • 19
  • 95
  • 113
  • 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 05 '16 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 '19 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 '19 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 '19 at 19:07
  • @Barmar pretty sure uint will always be converted to unsigned if you try to set to negative – james Apr 17 '19 at 19:58
  • I said "if it were declared `int N`" so there's no conversion. – Barmar Apr 17 '19 at 19:59
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.

fede s.
  • 582
  • 3
  • 17
5

for N is uint, just use

N <= 1
yanghaogn
  • 833
  • 7
  • 15
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);
    }
}
Khaled.K
  • 5,828
  • 1
  • 33
  • 51
  • 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 06 '16 at 07: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 06 '16 at 10:18
  • 1
    How does this answer the question? – Clark Kent Apr 06 '16 at 12:30
  • @SaviourSelf it comes down to a lookup table, and there's the visual aspect explained in the answer. http://stackoverflow.com/a/395965/2128327 – Khaled.K Apr 06 '16 at 15:10
  • Why would you use a `switch` when you can have an array of answers? – Nayuki May 18 '16 at 06:11
  • @Nayuki either way it's a lookup table, but I'm going for the aesthetic, to show the function as readable as the mathematical definition. – Khaled.K May 18 '16 at 06:44
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);
CathalMF
  • 9,705
  • 6
  • 70
  • 106
  • 2
    How is that shorter than the original? – MCMastery Apr 01 '16 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 02 '16 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 03 '16 at 08:42
  • @Groo And what if the values were -10, -2, 5, 7, 13 – CathalMF Apr 03 '16 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 03 '16 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);
Artur A
  • 7,115
  • 57
  • 60
-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#

One Normal Night
  • 332
  • 1
  • 2
  • 12
  • 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 ` 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 04 '16 at 07:41
  • 2
    Oh. Okay. I'm sorry :( – One Normal Night Apr 04 '16 at 15:48
  • @OneNormalNight (x==!!x) How this will work. Consider my input is 5. (5 == !!5). It will give result as true – VINOTH ENERGETIC Jun 02 '16 at 18:29
  • 1
    @VinothKumar !!5 evaluates to 1. (5 == !!5) evaluates (5 == 1) which evaluates to false. – One Normal Night Jun 02 '16 at 19:14
  • @OneNormalNight yeah i got it now. !(5) gives 1 again applied it gives 0. Not 1. – VINOTH ENERGETIC Jun 03 '16 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.

KnorxThieus
  • 567
  • 8
  • 17