Errors in Fibonacci Sequence

[GonlyG]

Basically, it's fibonacci sequence reversed: which number in the sequence (1 to 1000) is a number in the fibonacci sequence? (As far as I'm concerned you're guaranteed to NOT get the first three numbers :P)

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int Fibonacci (vector<char> num){
    vector<char> sum;
    int MAX = 1000;
    int array [MAX]; //includes up to 1000 fibonacchi values
    int a=0, b=1;
    array[a]=0;  // 0th value is 0;
    array[b]=1;  //1st value is 1
    int whichnumber=3; //"well, you know that it's not gonna be number one or two or even three..."
    do {whichnumber++;
            for (int i=0; i< MAX; i++)
                {int c=a+b;
                array[c]= array[a]+array[b];
              sum.push_back (array[c]);    //  all next values are sum of two immediately preceeding. 
                a++; b++; 
                }
        } while (num!=sum);
                  return whichnumber;
}
int main() {
     int a;
     cin>>a;
     vector<char> num;
     for (int i=0; i<a;i++){
        cin>> num;
         Fibonacci(num);
     }
}

Error:

 In function 'int main()':
28:15: error: cannot bind 'std::istream {aka std::basic_istream<char>}' lvalue to 'std::basic_istream<char>&&'
In file included from /usr/include/c++/4.9/iostream:40:0,
                 from 1:
/usr/include/c++/4.9/istream:872:5: note: initializing argument 1 of 'std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&&, _Tp&) [with _CharT = char; _Traits = std::char_traits<char>; _Tp = std::vector<char>]'
     operator>>(basic_istream<_CharT, _Traits>&& __is, _Tp& __x)
     ^

I don't know how to fix that. (And no, I can't do int or even long because inputs can go up to THIS long: "507940209862363741933629736977542504466112911759105550947919604278644410414632000440025360027897499295135089622767292568657349802307299876209510138041875"

[cire]

num in cin >> num; is a vector<char> and std::istream doesn't know what to do with a vector<char>.

[GonlyG]

casting doesn't work..... what do I do?

 #include <iostream>
#include <string>
#include <vector>
using namespace std;
int Fibonacci (vector<char> num){
    vector<char> sum;
    int MAX = 1000;
    int array [MAX]; //includes up to 1000 fibonacchi values
    int a=0, b=1;
    array[a]=0;  // 0th value is 0;
    array[b]=1;  //1st value is 1
    int whichnumber=3; //"well, you know that it's not gonna be number one or two or even three..."
    do {whichnumber++;
            for (int i=0; i< MAX; i++)
                {int c=a+b;
                array[c]= array[a]+array[b];
              sum.push_back (array[c]);    //  all next values are sum of two immediately preceeding. 
                a++; b++; 
                }
        } while (num!=sum);
                  return whichnumber;
}
int main() {
     int a;
     cin>>a;
     vector<char> *num;
     for (int i=0; i<a;i++){
       *num = static_cast<char>(*num);
       cin>> num;
         Fibonacci(num);
     }
}

[cire]

casting doesn't work..... what do I do?

Why did you make it a pointer? Don't guess.

Tell it what to do. Read char-by-char and push_back the number corresponding to the digit. Depending on how you expect the order of elements in thee vector to be you may have to reverse it when you're done.

[GonlyG]

no matching operator for stuff...

 #include <iostream>
#include <string>
#include <vector>
using namespace std;
int Fibonacci (vector<char> num){
    vector<char> sum;
    int MAX = 1000;
    int array [MAX]; //includes up to 1000 fibonacchi values
    int a=0, b=1;
    array[a]=0;  // 0th value is 0;
    array[b]=1;  //1st value is 1
    int whichnumber=3; //"well, you know that it's not gonna be number one or two or even three..."
    do {whichnumber++;
            for (int i=0; i< MAX; i++)
                {int c=a+b;
                array[c]= array[a]+array[b];
              sum.push_back (array[c]);    //  all next values are sum of two immediately preceeding. 
                a++; b++; 
                }
        } while (num!=sum);
                  return whichnumber;
}
int main() {
     int a;
     cin>>a;
     vector<char> num;
     for (int i=0; i<a;i++){
         string number; //because int or long is too small
      cin>>number;
      do {num.push_back (number % 10)
      }while (number>0);
         Fibonacci(num);
     }
}

[Chervil]

There's a problem here:

    int MAX = 1000;
    int array [MAX]; //includes up to 1000 fibonacci values 

Even if you use 64-bit unsigned integers, that will only get you as far as the 93rd Fibonacci number which is 12200160415121876738.

To go beyond that, you will need to use some sort of big integer arithmetic. There are libraries available, though if all you need is to add two unsigned numbers, it isn't hard to write your own.

[GonlyG]

the big integer library doesn't work ( #include "BigIntegerLibrary.hh").
And also, why would that not work? I'm storing gigantic numbers in an array. Don't the numbers have no relation to how big the array is? I mean, let's say I wanted to store two ridiculously big numbers in a 3-number array.
Int array [3] //creates array of 3 numbers
array[1] = 92345029348609234860283460982340682056802346394860398560170967
array[2] =9348590234786029569257069873409568394856093845690834056893045680
array[3] = 4923876029347602973460927834069820493786012974360973016890

wouldn't that work?

(if that doesn't work, would an alternate solution be viable treating the numbers as string instead?)

[Chervil]

the big integer library doesn't work ( #include "BigIntegerLibrary.hh").

I had a quick look and it didn't compile for me. There are other libraries, but I don't have an immediate recommendation.

Did you try assigning a number such as
92345029348609234860283460982340682056802346394860398560170967
to an integer and then output the value which was actually stored? It gives some interesting error messages when compiled.

would an alternate solution be viable treating the numbers as string instead?

That is a viable solution. But it means you have to write the code to add two strings one digit at a time. Not too hard, but it is tricky to make sure the carry does not get lost. e.g. 7 + 8 = 15. the '1' digit is a carry from the next column.


Edit: one of the simpler libraries is ttmath
http://www.ttmath.org/

#include <iostream>
#include "ttmath.h"

int main() 
{
    ttmath::UInt<30> a,b,next;
    
    a = 0;
    b = 1;
    
    for (int i=0; i<100; i++)
    {
        std::cout << a << '\n';
        next = a + b;
        a = b;
        b = next;
    }
   
    return 0;
}

[GonlyG]

fatal error: ttmath.h: No such file or directory
Also, are you sure I can't just assign a value to a vector? In that case, I wouldn't need an array. In pseudo code, it would look like this:
vector one = 0;
vector two = 2;
vector sum = vector one plus vector two;
Make one = two, Two = sum, and sum = new vector one plus new vector two.
Do this until the ridiculously big number matches the vector SUM.
For each "Push_back" of vector, I plus one to the last number, starting from three, since sum starts from the third number.

so let's see, the basic skeleton of the code would probably be something like,

int a; cin>>a; //number of crazy-big numbers
int whichnumber;
for (int i=0; i<a;i++)
{
string/char/vector? crazybignumber;
cin>>crazybignumber;
vector <int> one = 0 /*note that the storage value is obv. way bigger than int, int is just a placeholder */
vector <int> two = 1
do 
       {vector <int> sum = one + two;
one=two;
 two=sum; 
sum=one + two;
whichnumber++;
        }while (sum!=crazybignumber);
cout << whichnumber<<" ";
}

[GonlyG]

also, dammit, it seems it's too large:

#include <iostream>
using namespace std;
int main(){
    long int array[1000];
    array[1] = 92345029348609234860283460982340682056802346394860398560170967;
    cout<<array;
}

5:16: warning: integer constant is too large for its type

String also fails *sad face

#include <iostream>
#include <string>
using namespace std;
int main(){
    string array[1000];
    array[1] = 92345029348609234860283460982340682056802346394860398560170967;
    cout<<array;
}

6:16: warning: integer constant is too large for its type
In function 'int main()':
6:14: warning: overflow in implicit constant conversion [-Woverflow]

But wait! I suddenly have an idea!
This method DOES work for numbers up to 14 digits:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    long int num;
    long int backup;
    cin>>num;
    backup = num%1000000;
    num=num/1000000;
    cout<<num<<backup;
}

Thus, all I need to do is to test and see if the number is bigger than long int's limits, then divide by the appropriate values!
(However, this would need at least 10 different variables due to the length of the crazy-long-numbers.... surely, there's a better way than that.)

[Chervil]

Possibly you could use a vector.

Regarding the message:

fatal error: ttmath.h: No such file or directory

You did download the library from the site I previously mentioned? I got the file
"ttmath-0.9.3-src.tar.gz" from this page, http://www.ttmath.org/_download

You have to unpack it (I use 7-zip for that). Place the folder ttmath with your project files and tell the compiler where to find it.

[TheIdeasMan]

vector<char> num
and
} while (num!=sum);

These won't work together.

fatal error: ttmath.h: No such file or directory

If you need numbers that large, well you need to get hold of that file or install the package it is part of, it clearly won't work with built in types

Basically, it's fibonacci sequence reversed: which number in the sequence (1 to 1000) is a number in the fibonacci sequence?

Why are you trying to calculate the 1000'th Fib number? Instead calc fib numbers to a max of 1000.

So there is some confusion as to what the question actually is. Can you post the actual question?

[GonlyG]

the actual question is asking, which number in the fibonacci sequence is a gigantic number which I will input?
Example:
The fibonacci sequence's beginning is:
0 1 1 2 3 5 8 13....
which number in the sequence is the number, "13"? Well, it's number 8. Obviously those gigantic numbers are far harder, but this is just a demonstration.

[TheIdeasMan]

which number in the fibonacci sequence is a gigantic number which I will input?

OK, so you will definitely need a big number library as mentioned by Chervil, then it should be easy.

I have seen before, certain short cuts involving the modulo operation, not sure how they may be applied to this particular problem though.

Google wiki fibonacci modulo

http://webspace.ship.edu/msrenault/fibonacci/fib.htm

These sort of questions often come from on line challenge forums such as Euler project or Online Judge & many others. Invariably brute force is not the answer, and there is a very clever technique used to arrive at the answer.

[Chervil]

One way to solve this is the one you already considered, that is, to store an array of Fibonacci numbers.

Another way might be to use some of the formulas on this page:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

see Detecting when N is a Fibonacci Number
and under the same heading "To detect which Fibonacci number it is"

It depends how comfortable you are with using those formulae. In any case to get accurate results you would still need to be able to calculate to a higher precision than is possible with the built-in types.

[GonlyG]

I tried the Fibonacci formula but got "45" all as my answers.

#include <iostream>
#include <vector>
#include <complex>
#include <math.h>
#include <string.h>
using namespace std;
int main()
{ 
    long int a, i;
    int c=0;
    vector<int> n (c);
    cin>>a;
    float PHI = 1.6180339887;
    for (int b=0; b<a; b++)
    {
    cin>> c;
  i = round(log(c) + log(5)/2)/log(PHI);
  cout<< i<<" ";
    }
}

Input: 28
2140935670430744807574135096594352867870326513691554414255291365439899896195338574650391023831983407002010606771661694359511889901760895623747987191521
35029596967131343602213497450232647402139968983372205851566400021802909132390757909314
32875480819871550678637491032482982278929937521851455903100411081023032472796271490080295935690254600725412811190800664285130802019106060377555012507763097668031393332428584361077500513775809227496
22308937193354610669694603807015405539076350041834573454258697396983045914199271188275511370006539363802678264614779314564883890417798143615755904634632669881611012219869
690168906931029935139391829792095612517948949963798093315456
86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501
433494437
27713991332898951849369141694887577580844268614029932119435071462261690126253987857716252505338630328337483625842233853861187686551179198305850552365314432013776222604488073014165694290306137408859517
460305632946475974913289730008650724589274111744942847887625709814486715061925402183981910630305243949549859833815445248241405116508941501309518517980434947055657314482912443773
4439590603858869180288980079727269710383226601574882557289218773109235779343341990738294004603210334397661407832357095801092424716112702801064428066697907999685333994717357
30464466237021013443716776226800834957182606015969344302751396920321847653300991
20341574322680408081083829243820203612317308197211964554628215486203974898255803242740333222721700974747
308061521170129
5521577958796399352092495436683350598124375604156506038828319671569975838863744971896028280751218827164657336
55770816383139792841788949999913921345356178355268512101896904567668081960045169650757076826495336494165460988846493606642669121439650917
2143402371193585144275731144820024112622791843221056597232
21327100234463183349497947550385773274930109
16873133642056375905587710582599649871950164914626667247549740605066847393904820916710717780724785740147644757432744668969451486247747335959167429000482522247
13582369791278266616906284494806735565776939502107183075612628409034209452901850178519363189834336113240870247715060398192490855
609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595
348548520675021628424024078524038024981674935849553053830206986267617333
1429534386761117496218850990648231216953367996806038580031624220600185789744424675546498909702825612297777197190134402501047224251346762776435775100647520636533096272723314165
21624566574033249908479058525261934298547801008518093327427828213794236274252366061503132978728550110978101030934864543624309608482456326210698525158753672353459406510105385364770
51680708854858323072
5034645418285014325766435419644478339818233
23014966658090829951746935523702727869822794703356214747054654403691485011029871625049155977166003140263732538789372154130496999553676394481459148745385952301569
4585371016945309254695820765383405232040578837489482816555438621189665
5193981023518027157495786850488117

Output: 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45

[cire]

I tried the Fibonacci formula but got "45" all as my answers.

That's because the values you've entered are too large for cin to extract them into a variable of type int.

[Chervil]

Line 16 cin>> c; is not goint to work with such large inputs where c is type int. To give the program even half a chance of working, try using type double or maybe long double for c, and in the subsequent calculation.

Hmm.. I just tried the above code using long double, it gave results which were approximately correct. ... ah. there's an error, the round() function is applied to only part of the expression at line 17.

[GonlyG]

huzzah!

#include <iostream>
#include <vector>
#include <complex>
#include <math.h>
#include <string.h>
using namespace std;
int main()
{ 
    long int a, i;
    long double c=0;
    vector<int> n (c);
    cin>>a;
    float PHI = 1.6180339887;
    for (int b=0; b<a; b++)
    {
    cin>> c;
  i = round((log(c) + log(5)/2)/log(PHI));
  cout<< i<<" ";
    }
}