c++ - 编译时间斐波那契处理大量

我在玩这个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;
    }
}

结果是:



那么是否可以轻松地为meta fibonacci提供ttmath？还是我应该做些不同的事情？

最佳答案

如果您查看ttmath源，则有一个UInt<N>::Add的定义，该定义在uint数组table上迭代，该数组表示UInt<N>值，添加每个元素对并将溢出内容带入下一个迭代。基于此迭代，可以定义如下的递归模板实现:

#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;
}

添加就是斐波那契所需的一切

关于c++ - 编译时间斐波那契处理大量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31504804/