Wrong result using unsigned long long int

Dude McBee (3)
I'm playing with a simple program to learn about recursion. I've tried to calculate the Fibonacci number 50 which should be 12,586,269,025.

The result however is 18,446,744,073,410,918,753. Fibonacci numbers between 0 and 46 are calculated correctly, 47 is the first one to be wrong.

The limits have been tested as

LLONG_MAX = 9,223,372,036,854,775,807
ULLONG_MAX = 18,446,744,073,709,551,615

The result is just below ULLONG_MAX.

(All commas inserted manually for readability.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <cmath>
#include <climits>
#include <cstdint>

using namespace std;

int fib(unsigned long long int n){
  unsigned long long int r;
  if (n>=3){
    r = fib(n-1) + fib(n-2);
  } else {
    r = 1;
  }
  return r;
}

int main(int argc, char *argv[]){
	if (argc==1){
		return 1;
	}
	long long int m = atoll(argv[1]);
  unsigned long long int n = m;
  unsigned long long int r = fib(n);
  cout << r << endl;
  return 0;
}
Last edited on
Ganado (6849)
r is an unsigned long long, but you are returning an int from your function (and then casting it back into an unsigned long long).
Last edited on
dutch (2548)
(Deleted: I was thinking "factorial" instead of "fibonacci"!)
Last edited on
lastchance (6980)
Unless you memoise it, working out Fibonacci numbers by recursive function calls is going to bust the stack pretty quick.

It's a shame you can't just use the python idiom on this:
a,b=b,a+b



1
2
3
4
 
a = b = 1;   N = 50
for i in range( 3, N+1 ):
   a, b = b, a + b
print( b )


12586269025
Last edited on
Dude McBee (3)
Thanks to Ganado, that was it, just found it out :) 

 
 
unsigned long long int fib(unsigned long long int n){...}


I had been thinking already about the stack, I have to learn how to keep an eye on it during execution!

Thx, guys!
deleted account xyzzy (5768)
Returning an int from your Fibonacci function is where things get screwed up, you need to return unsigned long long.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>

using ULL = unsigned long long;

ULL GetFibNum(ULL);

int main()
{
   std::cout << "Enter index of desired Fibonacci Number: ";
   ULL index { };
   std::cin >> index;
   std::cout << '\n';

   std::cout << "Fibonacci number is: " << GetFibNum(index) << '\n';
}

ULL GetFibNum(ULL fibIndex)
{
   if (fibIndex < 2)
   {
      return fibIndex;
   }
   else // recursion if FibIndex >= 2
   {
      return GetFibNum(fibIndex - 1) + GetFibNum(fibIndex - 2);
   }
}
Enter index of desired Fibonacci Number: 50

Fibonacci number is: 12586269025

Using recursion can be SLOOOOOOOOW even with a semi-fast processor. Calculating Fib(50) took approximately 2 minutes and 20 seconds on my i5 development machine. Iteration is much speedier. And it won't "bust the stack," as could possibly happen with repeated recursions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <iostream>

using ULL = unsigned long long;

ULL GetFibNum(ULL);

int main()
{
   std::cout << "Enter index of desired Fibonacci Number: ";
   ULL index { };
   std::cin >> index;
   std::cout << '\n';

   std::cout << "Fibonacci number is: " << GetFibNum(index) << '\n';
}

ULL GetFibNum(ULL fibIndex)
{
   if (fibIndex < 2)
   {
      return fibIndex;
   }
   else // iterate if FibIndex >= 2
   {
      ULL previous { 1 };
      ULL current  { 1 };
      ULL next     { 1 };

      for (ULL i { 3 }; i <= fibIndex; ++i)
      {
         next     = current + previous;
         previous = current;
         current  = next;
      }

      return next;
   }
}
Last edited on
dutch (2548)
the Fibonacci sequence you show is not correct

I figured that out! For some reason I though it was factorials.
BTW, ! means factorial! :-)
deleted account xyzzy (5768)
So even I make mistakes, *GASP!*

I blame it on no coffee yet. Yeah! That's it! (will he buy that excuse? Probably not)
dutch (2548)
No coffee?! No wonder! Quick man, drink up!!!

It looks like fib(93) is the highest that will fit in a uint64_t:

  0:                    0
  1:                    1
  2:                    1
  3:                    2
  4:                    3
  5:                    5
  6:                    8
  7:                   13
  8:                   21
  9:                   34
 10:                   55
 11:                   89
 12:                  144
 13:                  233
 14:                  377
 15:                  610
 16:                  987
 17:                 1597
 18:                 2584
 19:                 4181
 20:                 6765
 21:                10946
 22:                17711
 23:                28657
 24:                46368
 25:                75025
 26:               121393
 27:               196418
 28:               317811
 29:               514229
 30:               832040
 31:              1346269
 32:              2178309
 33:              3524578
 34:              5702887
 35:              9227465
 36:             14930352
 37:             24157817
 38:             39088169
 39:             63245986
 40:            102334155
 41:            165580141
 42:            267914296
 43:            433494437
 44:            701408733
 45:           1134903170
 46:           1836311903
 47:           2971215073
 48:           4807526976
 49:           7778742049
 50:          12586269025
 51:          20365011074
 52:          32951280099
 53:          53316291173
 54:          86267571272
 55:         139583862445
 56:         225851433717
 57:         365435296162
 58:         591286729879
 59:         956722026041
 60:        1548008755920
 61:        2504730781961
 62:        4052739537881
 63:        6557470319842
 64:       10610209857723
 65:       17167680177565
 66:       27777890035288
 67:       44945570212853
 68:       72723460248141
 69:      117669030460994
 70:      190392490709135
 71:      308061521170129
 72:      498454011879264
 73:      806515533049393
 74:     1304969544928657
 75:     2111485077978050
 76:     3416454622906707
 77:     5527939700884757
 78:     8944394323791464
 79:    14472334024676221
 80:    23416728348467685
 81:    37889062373143906
 82:    61305790721611591
 83:    99194853094755497
 84:   160500643816367088
 85:   259695496911122585
 86:   420196140727489673
 87:   679891637638612258
 88:  1100087778366101931
 89:  1779979416004714189
 90:  2880067194370816120
 91:  4660046610375530309
 92:  7540113804746346429
 93: 12200160415121876738


FIrst 300 fibs (factored): http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
Last edited on
Dude McBee (3)
Thanks a lot to all of you, we all learn from errors :)
deleted account xyzzy (5768)
It looks like fib(93) is the highest that will fit in a uint64_t

I have never tested a C/C++ Fibonacci app above 50 or so, nice to know what the potential upper limit with the built-in types is. Thanks, dutch.
jonnin (11495)
Furry, I got 90 values in an eyeblink. its all in how you write the recursion, that even includes a sluggish cout statement in the function so you get a list of all the values.
Granted, its not the slickest looking, but its recursion and its fast

edit, a little smoother, now just call it with say fib(90) or whatever to get that many. 

1
2
3
4
5
6
7
8
9
10
11
12
 
void fib(int counter, uint64_t a = 0, uint64_t b = 1)
{
  static uint64_t res = 0;
  static int count = counter;
  if(a == 0) count = counter;
  if(--count)  
  {
   cout << a+b << endl;   	  	  
   fib(count,b, a+b);         
   return;
  }  
}


however, just like factorials, if you are stuck in int land (64 bits or less) then a lookup table is the fast way, no need to compute things like this unless you have a big-int class and a need for going farther out.
Last edited on
deleted account xyzzy (5768)
@jonnin, you are reducing the recursion by considerable amounts by restructuring how the function is called and how the Fibonacci number is calculated. So yeah, your recursion algorithm would be speedier than the commonly used method the OP and I used.

Less likely to blow up the stack too.
jonnin (11495)
Yes, I cheated, to be honest. Its really just the simplest of loops rewritten as 'recursion'. The commonly used method is... well, poor.
dutch (2548)
Optimized tail recursion only uses one stack frame. It's equivalent to a loop.

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <iostream>

void fib(int n, uint64_t a = 0, uint64_t b = 1)
{
    std::cout << a << '\n';
    if (n) fib(n - 1, b, a + b);
}

int main()
{
    fib(93);
}

deleted account xyzzy (5768)
I wouldn't call it cheating. It's 'creative.' Well done, James Tiberius Kirk!

Calculating a Fibonacci number using the common recursion method uses the by-hand algorithm. Slow and inefficient was the rule of the day.
JLBorges (13770)
> Optimized tail recursion only uses one stack frame. It's equivalent to a loop.

In some cases, the generated code may be a wee bit faster with TCO. Optimisers tend to like TCO.
From an old thread: https://www.cplusplus.com/forum/general/132632/#msg713383
Topic archived. No new replies allowed.