使用NSDecimalNumber for Fibonacci系列与Binet的公式

Question

今天我花了相当多的时间试图计算斐波纳契第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(数字)函数的要点.我尝试使用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 Fibonacci数,X大于700但小于800.我最终得到此错误/输出:

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,我不知道如何继续解决这个问题,也许我应该使用一些数学技巧？

提前致谢.

Answer 1

您已经遇到了NSDecimalNumber可以容纳的最大值.有一个功能可以准确地告诉你它是什么.尝试:

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

它会给你:

3402823669209384634633746074317682114550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

这恰好是166位数.

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

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