2

当 n 是一个非常大的数字时，我今天花了相当多的时间试图计算斐波那契第 n 项。我决定使用 Objective-C，考虑到它花了多长时间，事后看来这可能不是最好的决定。我研究并决定使用 Binet 的公式，该公式似乎适用于使用其他编程语言的其他人。

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

是 C 中 fibonacci(number) 函数的要点。我尝试使用 NSDecimalNumber 将其转换为 Objective-C，我的方法如下所示：

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 斐波那契数。我最终得到此错误/输出：

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

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

*** 首先抛出调用堆栈：

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，我不确定如何进一步解决这个问题，也许我应该使用一些数学技巧？

提前致谢。

4

1 回答 1

5

NSDecimalNumber您已经达到了 a可以容纳的最大值。有一个函数可以准确地告诉你它是什么。尝试： 

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

它会给你：

3402823669209384634633746074317682114550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

恰好是 166 位数字。

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

编辑：
另外，正如 Metabble 在下面提到的，尾数中的最大位数是 38 位。这意味着任何导致值大于 38 位的计算都将被截断并使用尾数存储，以跟踪剩余位数。当您访问结果时，第 38 位之后的每个数字都将为 0，这会导致值不正确。

于 2013-02-02T03:41:55.393 回答