# How many Fibs?

How many Fibs?

Recall the definition of the Fibonacci numbers:

```f1 := 1
f2 := 2
fn := fn-1 + fn-2     (n>=3) ```

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a<=b<=10100. The numbers a and b are given with no superfluous leading zeros.

For each test case output on a single line the number of Fibonacci numbers f i with a<=fi<=b.

``````10 100
1234567890 9876543210
0 0

``````

``````5
4``````

``````#include <iostream>
#include <string>
#include <vector>

using namespace std;

// F_n = 1/sqrt(5) * ((1/2 + sqrt(5)/2)^n - (1/2 - sqrt(5)/2)^n) <= 2^n+1
// therefore there aren't too many (less than 2*2*log(10^100) approx. 800) fibs

typedef vector <string> tVec;

string add(string s1, string s2) {
string r(101u, '0');
int carry = 0;
for (int i=100; i >= 0; i--) {
int next = carry + (s1[i]-'0') + (s2[i]-'0');
r[i] = (next % 10) + '0';
carry = next / 10;
}
return r;
}

int main() {
string s(101u, '0');
tVec   v;
s = '1';
v.push_back(s);
s = '2';
v.push_back(s);
while (1) {
if (s > "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
break;
v.push_back(s);
}

while (1) {
string a, b;
cin >> a >> b;
if (b == "0")
break;
while (a.length() < 101) a = "0" + a;
while (b.length() < 101) b = "0" + b;
int pos;
for (pos = 0; pos < v.size() && v[pos] < a; pos++);
int counter = 0;
for ( ; pos < v.size() && v[pos] <= b; pos++, counter++);
cout << counter << endl;
}

return 0;
}

``````

``````#include <iostream>
#include <string>
#include <vector>

using namespace std;

// F_n = 1/sqrt(5) * ((1/2 + sqrt(5)/2)^n - (1/2 - sqrt(5)/2)^n) <= 2^n+1
// therefore there aren't too many (less than 2*2*log(10^100) approx. 800) fibs

typedef vector <string> tVec;

string add(string s1, string s2) {
string r(101u, '0');
int carry = 0;
for (int i=100; i >= 0; i--) {
int next = carry + (s1[i]-'0') + (s2[i]-'0');
r[i] = (next % 10) + '0';
carry = next / 10;
}
return r;
}

int main() {
string s(101u, '0');
tVec   v;
s = '1';
v.push_back(s);
s = '2';
v.push_back(s);
while (1) {
if (s > "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
break;
v.push_back(s);
}

while (1) {
string a, b;
cin >> a >> b;
if (b == "0")
break;
while (a.length() < 101) a = "0" + a;
while (b.length() < 101) b = "0" + b;
int pos;
for (pos = 0; pos < v.size() && v[pos] < a; pos++);
int counter = 0;
for ( ; pos < v.size() && v[pos] <= b; pos++, counter++);
cout << counter << endl;
}

return 0;
}

``````