How to calculate a 1000-digit precision Fibonacci number?

本文共计541个文字，预计阅读时间需要3分钟。

100位数字的斐波那契数问题25：斐波那契数列由递推关系定义：F(n)=F(n-1) + F(n-2)，其中F(1)=1和F(2)=1。因此，前12项将是：F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, F(8)=21, F(9)=34, F(10)=55, F(11)=89, F(12)=144。

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n= F_n−1+ F_n−2, where F₁= 1 and F₂= 1.

Hence the first 12 terms will be:

F₁= 1
F₂= 1
F₃= 2
F₄= 3
F₅= 5
F₆= 8
F₇= 13
F₈= 21
F₉= 34
F₁₀= 55
F₁₁= 89
F₁₂= 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

Answer:

4782

Completed on Fri, 28 Oct 2016, 06:13

题解：高精度fibonacci。

#include <bits/stdc++.h>
using namespace std;

class BigNumber //大数类
{
private:
int num[1000];

public:
BigNumber(int tmp)
{
for(int i=999; i>=0; i--) //1000位
{
num[i] = tmp%10;
tmp /=10;
}
}

public:
bool isThousand()
{
return num[0]>0;
}
BigNumber operator+(const BigNumber& bigNumber)
{
BigNumber sum(0);
int tmp;
int over =0;
for(int i=999; i>=0; --i)//1000位
{
tmp = num[i]+bigNumber.num[i]+over;
sum.num[i] = tmp%10;
over = tmp/10;
}
return sum;
}

void print() //打印输出结果
{
for(int i=0; i<1000; i++)
{
cout << num[i];
}
cout<<endl;
}
};

int main()
{
BigNumber A1(1);
BigNumber A2(1);
int i=2;
while(1)
{
i++;
A1 = A1+A2;
if(A1.isThousand())
{
break;
}

i++;
A2 = A1+A2;
if(A2.isThousand())
{
break;
}
}
cout<<i<<endl;
return 0;

}

评论区的数学方法：