我想用大的整数值来确定第n个斐波那契数来看序列中 [英] I want to determine the nth Fibonacci term in the sequence using large integer values
问题描述
在code以下是能够确定正确的顺序最多使用的数据类型无符号很长很长的一个点，即70。我知道的顺序可能变大。因此我mod10000个结果。我想用最好的数据类型来确定第n项10000或改进算法中，计算第n项。
＃定义MOD％10000
无符号长长计算（长第n）{
返回（POW（1 + SQRT（5），第n） - POW（1 - 的sqrt（5），第n））/（POW（2.0，第n）*（SQRT（5）））;
};
诠释的main（）{
长T，第n个;
对于（给std :: cin＆GT;＆GT;吨;吨 - ＆功放;＆安培;给std :: cin＆GT;＆GT;第n）{
性病::法院＆LT;＆LT;钙（第n-2）的MOD＆LT;＆LT;＆LT;＆LT;钙（第n-1）MOD＆LT;＆LT;＆LT;＆LT;计算（第n）MOD＆LT;＆LT;的std :: ENDL;
}
返回0;
}
您算法将不计算正确结果大NS，由于sqrn的浮点错误（5）。
为了加快你的算法，你可以使用快速翻番斐波纳契：
F（2K）= F（K）2F（K + 1） - F（K）]
F（2K + 1）= F（K + 1）^ 2 + F（K）^ 2
应用模算术，你最终的最快的算法是：
F（2K）= F（K）2F（K + 1） - F（K）]％10000
F（2K + 1）=（F（K + 1）^ 2 + F（K）^ 2）％万
使用这种方法，你的函数不超过10000，这样一个 INT 键入就足够了。
编辑：好吧，我有一些空闲时间在周五晚上（不是一件好事我猜）和实现的算法。我实现了两个版本，第一个为O（1）内存和O（LG n）的时间复杂度和第二个使用缓存，为O（LG N）的内存和最坏情况下的运行时间，但带O的最好的情况下运行（1）。
的#include＆LT;的iostream＆GT;
＃包括＆LT; unordered_map＆GT;
使用名字空间std;
const int的P = 10000;
/ *为O（1）内存和O（LG n）的时间复杂度快速斐波纳契。无缓存。 * /
INT fib_uncached（INT N）
{
/ *找到MSB位* /
INT msb_position = 31;
而（（（1＆其中;！≤（msb_position-1）及n））的＆安培;＆安培; msb_position＆GT; = 0）
msb_position--;
诠释α= 0时，b = 1;
的for（int i = msb_position; I＆GT; = 0;我 - ）
{
INT D =（一％P）*（（二％的P）* 2 - （一％P）+ P），
E =（一％P）*（一％P）+（B％P）*（二％P）;
一= D％P;
B =Ë％P;
如果（（（正＆GT; I标记）及！1）= 0）
{
INT C =（A + B）％P;
A = B;
B = C;
}
}
返回;
}
/ *使用快速缓存斐波纳契* /
INT FIB（INT N）
{
静态的std :: unordered_map＆LT; INT，INT＆GT;高速缓存;
如果（cache.find（正）== cache.end（））
{
INT F;
如果（N == 0）
F = 0;
否则如果（正3;）
F = 1;
否则，如果（N％2 == 0）
{
INT K = N / 2;
F =（FIB（K）*（2 * FIB第（k + 1） - FIB（k））的）％的P;
}
其他
{
时int k =（N-1）/ 2;
F =（FIB第（k + 1）* FIB第（k + 1）+ FIB（k）的FIB *（k））的％P;
}
如果（F℃，）
F + = P;
缓存[N] = F;
}
返回cache.at（N）;
}
诠释的main（）
{
INT I;
CIN＆GT;＆GT;一世;
COUT＆LT;＆LT; I＆LT;＆LT; ：＆其中;＆其中; FIB（ⅰ）所述;＆其中; ENDL;
返回0;
}
参考不带cache的实现： http://www.nayuki.io/page /快斐波纳契-算法
The code below is able to determine the correct sequence up to a point namely 70 using the data type unsigned long long. I know the sequence can become large thus i mod 10,000 the results. I want to determine the nth term for 10,000 using the best data type or improve the algo to calculate the nth term.
#define MOD %10000
unsigned long long calc(long nth){
return (pow( 1 + sqrt(5), nth ) - pow( 1 - sqrt(5), nth )) / (pow(2.0, nth)*(sqrt(5)));
};
int main(){
long t, nth;
for(std::cin>>t;t--&&std::cin>>nth;){
std::cout<<calc(nth-2)MOD<<" "<<calc(nth-1)MOD<<" "<<calc(nth)MOD<<std::endl;
}
return 0;
}
Your algorithm will not compute the correct result for large Ns, due to the floating point errors of sqrn(5).
In order to speed up your algorithm you can use fast doubling fibonacci:
F(2k) = F(k)[2F(k+1) - F(k)]
F(2k+1) = F(k+1)^2 + F(k)^2
Applying modulo arithmetics, your final fastest algorithm would be:
F(2k) = F(k)[2F(k+1) - F(k)] % 10000
F(2k+1) = (F(k+1)^2 + F(k)^2) % 10000
Using this approach, your function never exceeds 10000, thus an int type suffices.
EDIT: Okay I had some free time on a friday night (not a good thing I guess) and implemented the algorithm. I implemented two versions, first one with O(1) memory and O(lg n) time complexity and second one using a cache, with memory and worst-case runtime of O(lg n), but with a best case runtime of O(1).
#include <iostream>
#include <unordered_map>
using namespace std;
const int P = 10000;
/* Fast fibonacci with O(1) memory and O(lg n) time complexity. No cache. */
int fib_uncached (int n)
{
/* find MSB position */
int msb_position = 31;
while (!((1 << (msb_position-1) & n)) && msb_position >= 0)
msb_position--;
int a=0, b=1;
for (int i=msb_position; i>=0;i--)
{
int d = (a%P) * ((b%P)*2 - (a%P) + P),
e = (a%P) * (a%P) + (b%P)*(b%P);
a=d%P;
b=e%P;
if (((n >> i) & 1) != 0)
{
int c = (a + b) % P;
a = b;
b = c;
}
}
return a;
}
/* Fast fibonacci using cache */
int fib (int n)
{
static std::unordered_map<int,int> cache;
if (cache.find(n) == cache.end())
{
int f;
if (n==0)
f = 0;
else if (n < 3)
f = 1;
else if (n % 2 == 0)
{
int k = n/2;
f = (fib(k) * (2*fib(k+1) - fib(k))) % P;
}
else
{
int k = (n-1)/2;
f = (fib(k+1)*fib(k+1)+ fib(k) * fib(k)) % P;
}
if (f<0)
f += P;
cache[n] = f;
}
return cache.at(n);
}
int main ()
{
int i ;
cin >> i;
cout << i << " : " << fib(i) << endl;
return 0;
}
Reference for cache-less implementations: http://www.nayuki.io/page/fast-fibonacci-algorithms
这篇关于我想用大的整数值来确定第n个斐波那契数来看序列中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
