C语言 C 打印前一百万个斐波那契数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33733511/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C print first million Fibonacci numbers
提问by Chris Edwards
I am trying to write C code which will print the first 1million Fibonacci numbers.
我正在尝试编写将打印前 100 万个斐波那契数字的 C 代码。
The actual problem is I want to get the lats 10 digits of F(1,000,000)
实际问题是我想获得F(1,000,000)的lats 10 位数字
I understand how the sequence works and how to write the code to achieve that however as F(1,000,000)is very large I am struggling to find a way to represent it.
我了解序列是如何工作的以及如何编写代码来实现这一点，但是由于F(1,000,000)非常大，我正在努力寻找一种表示它的方法。
This is code I am using:
这是我正在使用的代码：
#include<stdio.h>
int main()
{
unsigned long long n, first = 0, second = 1, next, c;
printf("Enter the number of terms\n");
scanf("%d",&n);
printf("First %d terms of Fibonacci series are :-\n",n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
return 0;
}
I am using long longto try and make sure there are enough bits to store the number.
我正在long long尝试确保有足够的位来存储数字。
This is the output for the first 100numbers:
这是第一个100数字的输出：
First 100 terms of Fibonacci series are :-
0
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
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
...
Truncated the output but you can see the problem, I believe the size of the number generated is causing the value to overflow to negative. I don't understand how to stop it in all honesty.
截断了输出但您可以看到问题，我相信生成的数字的大小导致值溢出为负。老实说，我不明白如何阻止它。
Can anybody point me in the right direction to how to actually handle numbers of this size?
任何人都可以指出我如何实际处理这种大小的数字的正确方向吗？
I haven't tried to print the first million because if it fails on printing F(100)there isn't much hope of it printing F(1,000,000).
我还没有尝试打印第一个百万，因为如果打印失败，则打印的F(100)希望不大F(1,000,000)。
回答by Basile Starynkevitch
You want the last 10 digits of Fib(1000000). Read much more about Fibonacci numbers(and read twice).
您需要 Fib(1000000) 的最后 10 位数字。阅读更多关于斐波那契数的信息（并阅读两次）。
Without thinking much, you could use some bignumlibrary like GMPlib. You would loop to compute Fib(1000000) using a fewmpz_tbigint variables (you certainly don't need an array of a million mpz_t, but less mpz_tvariables than you have fingers in your hand). Of course, you won't print all the fibonacci numbers, only the last 1000000thone (so a cheap laptop today has enough memory, and would spit that number in less than an hour). As John Coleman answeredit has about 200K digits (i.e. 2500 lines of 80 digits each).
不用多想，您可以使用一些bignum库，例如GMPlib。您将使用一些mpz_tbigint 变量循环计算 Fib(1000000) （您当然不需要一百万个数组mpz_t，但mpz_t变量比您手中的手指要少）。当然，你不会打印所有的斐波那契数，只打印最后 1000000个（所以今天便宜的笔记本电脑有足够的内存，并且会在不到一个小时的时间内吐出那个数字）。正如约翰科尔曼回答的那样，它有大约 200K 位（即 2500 行，每行 80 位）。
(BTW, when thinking of a program producing some big output, you'll better guess-estimate the typical size of that output and the typical time to get it; if it does not fit in your desktop room -or your desktop computer-, you have a problem, perhaps an economical one: you need to buy more computing resources)
（顺便说一句，当考虑产生一些大输出的程序时，您最好猜测一下该输出的典型大小和获得它的典型时间；如果它不适合您的桌面房间-或您的台式计算机-，你有一个问题，也许是一个经济的问题：你需要购买更多的计算资源）
Notice that efficient bignum arithmetic is a hard subject. Clever algorithms exist for bignum arithmetic which are much more efficient than the naive one you would imagine.
请注意，高效的 bignum 算术是一门很难的课题。存在用于 bignum 算术的聪明算法，它们比您想象的幼稚算法要高效得多。
Actually, you don't need any bigints. Read some math textbook about modular arithmetic. The modulus of a sum (or a product) is congruent to the sum (resp. the product) of the modulus. Use that property. A 10 digits integer fits in a 64 bits int64_tso with some thinking you don't need any bignum library.
实际上，您不需要任何 bigint。阅读一些关于模算术的数学教科书。总和（或乘积）的模与模的总和（或乘积）一致。使用该属性。10 位整数适合 64 位，int64_t因此有些人认为您不需要任何 bignum 库。
(I guess that with slightly more thinking, you don't need any computer or any C program to compute that. A cheap calculator, a pencil and a paper should be enough, and probably the calculator is not needed at all.)
（我想稍微多思考一下，你不需要任何计算机或任何 C 程序来计算它。便宜的计算器，一支铅笔和一张纸就足够了，而且可能根本不需要计算器。）
The lesson to learn when programming (or when solving math exercises) is to think about the problemand try to reformulate the questionbefore starting coding. J.Pitrat (an Artificial Intelligence pioneer in France, now retired, but still working on his computer) has several interesting blogentries related to that: Is it possible to define a problem?, When Donald and Gerald meet Robert, etc.
在编程时（或在解决数学练习时）要学习的教训是在开始编码之前思考问题并尝试重新表述问题。J.Pitrat（法国的人工智能先驱，现已退休，但仍在使用他的计算机）有几个与此相关的有趣博客条目：是否可以定义问题？， 当唐纳德和杰拉德遇见罗伯特时，等等。
Understanding and thinking about the problem (and sub-problems too!) is an interesting part of software development. If you work on software developement, you'll be first asked to solve real-world problems (e.g. make a selling website, or an autonomous vacuum cleaner) and you'll need to think to transform that problem into something which is codable on a computer. Be patient, you'll need ten years to learn programming.
理解和思考问题（以及子问题！）是软件开发中一个有趣的部分。如果您从事软件开发工作，首先会要求您解决现实世界中的问题（例如制作销售网站或自动吸尘器），然后您需要考虑将该问题转化为可在计算机上编码的问题计算机。耐心点，你需要十年时间来学习编程。
回答by chux - Reinstate Monica
To "get the last 10 digits of F(1,000,000)", simply apply the remainder function %when calculating nextand use the correct format specifier: "%llu".
要“获取 F(1,000,000) 的最后 10 位数字”，只需%在计算时应用余数函数next并使用正确的格式说明符："%llu".
There is no need to sum digits more significant than the 10 least significant digits.
不需要对比 10 个最低有效数字更有效的数字求和。
// scanf("%d",&n);
scanf("%llu",&n);
...
{
// next = first + second;
next = (first + second) % 10000000000;
first = second;
second = next;
}
// printf("%d\n",next);
printf("%010llu\n",next);
My output (x'ed the last 5 digits to not give-away the final answer)
我的输出（x'ed 最后 5 位数字不放弃最终答案）
66843xxxxx
回答by John Coleman
By Binet's Formulathe nth Fibonacci Number is approximately the golden ratio (roughly 1.618) raised to the power n and then divided by the square root of 5. A simple use of logarithms shows that the millionth Fibonacci number thus has over 200,000 digits. The average length of one of the first million Fibonacci numbers is thus over 100,000 = 10^5. You are thus trying to print 10^11 = 100 billion digits. I think that you will need more than a big int library to do that.
根据比奈公式，第 n 个斐波那契数大约是黄金比例（大约 1.618）的 n 次方，然后除以 5 的平方根。对数的简单使用表明，第 100 万个斐波那契数有超过 200,000 位数字。因此，前一百万个斐波那契数之一的平均长度超过 100,000 = 10^5。因此，您试图打印 10^11 = 1000 亿位数字。我认为你需要的不仅仅是一个大的 int 库来做到这一点。
On the other hand -- if you want to simply compute the millionth number, you can do so -- though it would be better to use a method which doesn't compute all of the intermediate numbers (as simply computing rather than printing them all would still be infeasible for large enough n). It is well known (see this) that the nth Fibonacci number is one of the 4 entries of the nth power of the matrix [[1,1],[1,0]]. If you use exponentiation by squaring(which works for matrix powers as well since matrix multiplication is associative) together with a good big int library -- it becomes perfectly feasible to compute the millionth Fibonacci number.
另一方面——如果你想简单地计算百万分之一的数字，你可以这样做——尽管最好使用一种不计算所有中间数字的方法（简单地计算而不是打印它们）对于足够大的 n)，仍然不可行。众所周知（参见此），第 n 个斐波那契数是矩阵的 n 次幂的 4 个条目之一[[1,1],[1,0]]。如果您使用平方取幂（它也适用于矩阵乘法，因为矩阵乘法是关联的）和一个好的大型 int 库 - 计算百万分之一的斐波那契数变得非常可行。
[On Further Edit]: Here is a Python program to compute very large Fibonacci numbers, modified to now accept an optional modulus. Under the hood it is using a good C bignum library.
[进一步编辑]：这是一个计算非常大的斐波那契数的 Python 程序，修改后现在接受一个可选的模数。在幕后，它使用了一个很好的 C bignum 库。
def mmult(A,B,m = False):
#assumes A,B are 2x2 matrices
#m is an optional modulus
a = A[0][0]*B[0][0] + A[0][1]*B[1][0]
b = A[0][0]*B[0][1] + A[0][1]*B[1][1]
c = A[1][0]*B[0][0] + A[1][1]*B[1][0]
d = A[1][0]*B[0][1] + A[1][1]*B[1][1]
if m:
return [[a%m,b%m],[c%m,d%m]]
else:
return [[a,b],[c,d]]
def mpow(A,n,m = False):
#assumes A is 2x2
if n == 0:
return [[1,0],[0,1]]
elif n == 1: return [row[:] for row in A] #copy A
else:
d,r = divmod(n,2)
B = mpow(A,d,m)
B = mmult(B,B,m)
if r > 0:
B = mmult(B,A,m)
return B
def Fib(n,m = False):
Q = [[1,1],[1,0]]
return mpow(Q,n,m)[0][1]
n = Fib(999999)
print(len(str(n)))
print(n % 10**10)
googol = 10**100
print(Fib(googol, googol))
Output (with added whitespace):
输出（添加空格）：
208988
6684390626
3239047153240982923932796604356740872797698500591032259930505954326207529447856359183788299560546875
Note that what you call the millionth Fibonacci number, I call the 999,999th -- since it is more standard to start with 1 as the first Fibonacci number (and call 0 the 0th if you want to count it as a Fibonacci number). The first output number confirms that there are over 200,000 digits in the number and the second gives the last 10 digits (which is no longer a mystery). The final number is the last 100 digits of the googolth Fibonacci number -- computed in a small fraction of a second. I haven't been able to do a googolplex yet :)
请注意，您所说的第 100 万个斐波那契数，我称为第 999,999 个——因为以 1 作为第一个斐波那契数开始更为标准（如果您想将其算作斐波那契数，则将 0 称为第 0 个）。第一个输出数字确认数字中有超过 200,000 位数字，第二个给出最后 10 位数字（这不再是一个谜）。最后一个数字是 googolth Fibonacci 数的最后 100 位数字——在几分之一秒内计算出来。我还没有能够做一个 googolplex :)
回答by gnasher729
This question comes without doubt from some programming competition, and you have to read these questions carefully.
这道题无疑来自一些编程竞赛，你必须仔细阅读这些题。
The 1 millionth Fibonacci number is HUGE. Probably about 200,000 digits or so. Printing the first 1,000,000 Fibonacci number will kill a whole forest of trees. But read carefully: Nobody asks you for the 1 millionth Fibonacci number. You are asked for the last ten digitsof that number.
百万分之一的斐波那契数是巨大的。大概有 200,000 位左右。打印第一个 1,000,000 斐波那契数将杀死整个森林。但请仔细阅读：没有人要求您提供第 100 万个斐波那契数。要求您提供该号码的最后十位数字。
So if you have the last 10 digits of Fib(n-2) and of Fib(n-1), how can you find the last 10 digits of Fib(n)? How do you calculate the last ten digits of a Fibonacci number without calculating the number itself?
所以如果你有 Fib(n-2) 和 Fib(n-1) 的最后 10 位数字，你如何找到 Fib(n) 的最后 10 位数字？如何在不计算数字本身的情况下计算斐波那契数的最后十位数字？
PS. You can't print long long numbers with %d. Use %lld.
附注。你不能用 %d 打印长长的数字。使用 %lld。
回答by dbush
Your algorithm is actually correct. Since you're using unsigned long long, you have enough digits to capture the last 10 digits and the nature of unsigned overflow functions as modulo arithmetic, so you'll get the correct results for at least the last 10 digits.
你的算法实际上是正确的。由于您使用的是unsigned long long，因此您有足够的数字来捕获最后 10 位数字，并且无符号溢出函数的性质是模运算，因此您至少会获得最后 10 位数字的正确结果。
The problem is in the format specifier you're using for the output:
问题在于您用于输出的格式说明符：
printf("%d\n",next);
The %dformat specifier expects an int, but you're passing an unsigned long long. Using the wrong format specifier invokes undefined behavior.
该%d格式说明预计的int，但你传递的unsigned long long。使用错误的格式说明符会调用未定义的行为。
What's most likely happening in this particular case is that printfis picking up the low-order 4 bytes of next(as your system seems to be little endian) and interpreting them as a signed int. This ends up displaying the correct values for roughly the first 60 numbers or so, but incorrect ones after that.
在这种特殊情况下，最有可能发生的事情是获取（因为您的系统似乎是小端）的低位printf4 字节next并将它们解释为有符号的int. 这最终会显示大约前 60 个数字的正确值，但之后显示不正确的值。
Use the correct format specifier, and you'll get the correct results:
使用正确的格式说明符，您将得到正确的结果：
printf("%llu\n",next);
You also need to do the same when reading / printing n:
阅读/打印时您也需要这样做n：
scanf("%llu",&n);
printf("First %llu terms of Fibonacci series are :-\n",n);
Here's the output of numbers 45-60:
这是数字 45-60 的输出：
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
