对于Fibonacci系列，使用NSDecimalNumber和Binet的公式 [英] Using NSDecimalNumber for Fibonacci series with Binet's formula

问题描述

当n是一个非常大的数字时，我花了相当多的时间试图计算Fibonacci nth项。我决定使用Objective-C，事后看来可能不是最好的决定，考虑已经采取了多长时间。我研究并决定使用Binet的公式，似乎对其他人使用其他编程语言。

I've spent considerable time today trying to calculate the Fibonacci nth term when n is a very large number. I decided to use Objective-C which in hindsight may not have been the best decision, considering how long it has taken. I researched and decided to use Binet's formula which seems to work for other people using other programming languages.

double phi = (sqrt(5) + 1) / 2.0;
long long j = (long long) round(pow(phi, number) / sqrt(5));

是C中斐波纳契数字函数的要点。我试图将其转换为Objective-C使用NSDecimalNumber，我的方法如下：

Is the gist of a fibonacci(number) function in C. I tried converting this to Objective-C using NSDecimalNumber, my method looks like this:

NSDecimalNumber* squareRootOfFive = [NSDecimalNumber decimalNumberWithString: [[NSNumber numberWithDouble:sqrt(5)] stringValue]];
NSDecimalNumber* phi = [[squareRootOfFive decimalNumberByAdding:[NSDecimalNumber one]] decimalNumberByDividingBy:[NSDecimalNumber decimalNumberWithString:@"2"]];

return [[[phi decimalNumberByRaisingToPower: number] decimalNumberByDividingBy:squareRootOfFive] decimalNumberByRoundingAccordingToBehavior: [NSDecimalNumberHandler decimalNumberHandlerWithRoundingMode:  NSRoundPlain scale:2 raiseOnExactness:NO raiseOnOverflow:YES raiseOnUnderflow:NO raiseOnDivideByZero:NO ]];

奇迹可读我知道。这个代码适用于X大于700但小于800的第一个X斐波那契数字。我最终得到这个错误/输出：

Wonderfully readable I know. This code works for the first X Fibonacci number with X being greater than 700 but less than 800. I eventually get this error/output:

2013-02-01 17： 27：19.977 Euler25 [14907：303]斐波纳契数字792有166位数字

2013-02-01 17:27:19.977 Euler25[14907:303] Fibonacci number 792 has 166 digits

2013-02-01 17：27：19.989 Euler25 [14907：303] ***应用程序由于未捕获异常'NSDecimalNumberOverflowException'，原因：'NSDecimalNumber溢出异常'

2013-02-01 17:27:19.989 Euler25[14907:303] *** Terminating app due to uncaught exception 'NSDecimalNumberOverflowException', reason: 'NSDecimalNumber overflow exception'

***第一次调用堆栈：

*** First throw call stack:

0   CoreFoundation   0x00007fff8c3b10a6 __exceptionPreprocess + 198

1   libobjc.A.dylib  0x00007fff880443f0 objc_exception_throw + 43

2   CoreFoundation   0x00007fff8c3b0e7c +[NSException raise:format:] + 204

3   Foundation       0x00007fff8c88bc3d -[NSDecimalNumberHandler exceptionDuringOperation:error:leftOperand:rightOperand:] + 193

4   Foundation       0x00007fff8c88ad46 _checkErrorAndRound + 60

5   Foundation       0x00007fff8c88b1e2 -[NSDecimalNumber decimalNumberByRaisingToPower:withBehavior:] + 156

6   Euler25          0x0000000100001bb2 +[Euler25 fibonacci:] + 402

7   Euler25          0x0000000100001978 main + 184

8   libdyld.dylib    0x00007fff8a5147e1 start + 0

9   ???              0x0000000000000001 0x0 + 1

我无法得到漂亮的格式。我使用这段代码来解决Project euler [问题25]（[1]： http://projecteuler.net/
[2]： https://projecteuler.net/problem=25 ），如何一个工作与大数目在Objective-C如果不与NSDecimalNumber，我不知道如何进一步与这个问题，也许有一些数学诀窍我应该使用？

Which I can't get to format pretty. I was using this code to solve Project euler [Problem 25]( [1]: http://projecteuler.net/ [2]: https://projecteuler.net/problem=25), how does one work with large number in Objective-C if not with NSDecimalNumber, I'm not sure how to proceed further with this problem, perhaps there is some math trick I should be using?

提前感谢。

推荐答案

您已达到 NSDecimalNumber 可以保存。有一个函数可以告诉你它是什么。尝试：

You have run into the maximum value that a NSDecimalNumber can hold. There is a function which can tell you exactly what it is. Try:

NSLog(@"%@", [NSDecimalNumber maximumDecimalNumber]);

它会给你：

3402823669209384634633746074317682114550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

3402823669209384634633746074317682114550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

这是166位数。

Objective-C / C不支持大于该值的数字，因此您需要使用任意精度数学库。这是另一个 SO问题，其中讨论了一些选项。

Objective-C/C does not support numbers larger than that, so you will need to use an Arbitrary Precision Math library. Here is another SO question which discusses some options.

EDIT：

此外，在下面的Metabble中，尾数的最大位数是38位数。这意味着导致大于38个数字的值的任何计算将被截断并且用尾数保持剩余数字的数量的轨迹来存储。当您访问结果时，第38个数字后面的每个数字都将为0，从而导致数值不正确。

Also, as Metabble mentions below, the maximum number of digits in the mantissa is 38 digits. This means that any calculation which results in a value larger than 38 digits will be truncated and stored with a mantissa keeping track of the number of remaining digits. When you access the results, every digit after the 38th one will be 0, which results in an incorrect value.

这篇关于对于Fibonacci系列，使用NSDecimalNumber和Binet的公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！