編譯處理大量數字的斐波那契

Question

我正在玩這個compile time implementation。

我使用ttmath.org來處理大量數據。 ttmath::UInt<SIZE>適用於運行時間fib()函數，但是 我不知道如何處理我的元函數的大數字，因爲我必須更改非模板參數size_t。

#include <iostream> 
#include <omp.h> 
#include <ctime> 
#include "ttmath/ttmath.h" 
#include <type_traits> 

#define SIZE 1090 

// how can I use ttmath here ? 
template<size_t N> 
struct fibonacci : std::integral_constant<size_t, fibonacci<N-1>{} + fibonacci<N-2>{}> {}; 

template<> struct fibonacci<1> : std::integral_constant<size_t,1> {}; 
template<> struct fibonacci<0> : std::integral_constant<size_t,0> {}; 


// ttmath here works well at run time ! 
ttmath::UInt<SIZE> fib(size_t n) 
{ 
    ttmath::UInt<SIZE> a,b,c; 
    a = 1, b = 1; 
    for (size_t i = 3; i <= n; i++) { 
     ttmath::UInt<SIZE> c = a + b; 
     a = b; 
     b = c; 
    }   
    return b; 
} 

int main() { 
    const size_t N = 500; 
    if(1) 
    { 
    clock_t start = clock(); 
    std::cout << "Fibonacci(" << N << ") = " << fib(N) << std::endl; 
    std::cout << "Time : " << (double)(clock() - start)/CLOCKS_PER_SEC << " s" << std::endl; 
    } 
    if(1) 
    { 
    clock_t start = clock(); 
    std::cout << "Fibonacci(" << N << ") = " << fibonacci<N>() << std::endl; 
    std::cout << "Time : " << (double)(clock() - start)/CLOCKS_PER_SEC << " s" << std::endl; 
    } 
} 

結果是：

Fibonacci(500) = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
Time : 0.003006 s
Fibonacci(500) = 2171430676560690477
Time : 1.5e-05 s

所以是有可能的元斐波納契提供ttmath容易嗎？或者我應該做不同的事情？

Answer 1

如果看看ttmath源存在用於UInt<N>::Add它迭代表示UInt<N>值添加每個元件對和攜帶溢出到下一次迭代的UINT陣列table的定義。在此基礎上迭代一個可以定義一個遞歸模板實現這樣的：

#include <array> 
#include <ttmathuint.h> 

typedef unsigned int uint; 
namespace ttmath { 

    uint AddTwoUInt(uint a, uint b, uint carry, uint * result) 
    { 
     uint temp; 

     if(carry == 0) { 
      temp = a + b; 

      if(temp < a) 
       carry = 1; 
     } else { 
      carry = 1; 
      temp = a + b + carry; 

      if(temp > a) // !(temp<=a) 
       carry = 0; 
     } 

     *result = temp; 

     return carry; 
    } 

    template<uint N> 
    uint Add(const uint * t0, const uint * t1, uint * t2, uint c); 

    template<> 
    uint Add<1>(const uint * t0, const uint * t1, uint * t2, uint c) { 
     uint i; 
     c = AddTwoUInt(*t0, *t1, c, t2); 
     return c; 
    } 

    template<uint N> 
    uint Add(const uint * t0, const uint * t1 , uint * t2, uint c) { 
     c = Add<N-1>(t0, t1, t2, c); 
     c = AddTwoUInt(t0[N-1], t1[N-1], c, t2+N-1); 
     return c; 
    } 

} 
template<int N> 
ttmath::UInt<N> fib(size_t n) 
{ 
ttmath::UInt<N> a,b,c; 
a = 1, b = 1; 

for (size_t i = 3; i <= n; i++) { 
    ttmath::Add<N>(a.table,b.table,c.table,0); 
    a = b; 
    b = c; 
}    
return b;       
} 

int main(int argc,char ** argv) { 
std::cerr << fib<15>(500) << std::endl; 
} 

添加是所有你需要的斐波那契