Compile time fibonacci which handle large numbers

Question

I was playing around with this compile time implementation.

I use ttmath.org in order to handle large numbers. ttmath::UInt<SIZE> works well for run time fib() function but I don't know how I can handle large big numbers for my meta functions since I have to change the non template parameter 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;
    }
}

Result is :

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

So is it possible to provide ttmath for the meta fibonacci easily ? Or should I do things differently ?

because ttmath can handle bigger than size_t numbers, but fibbonachi tries to read size_t, which is probably 64 bits on your system, and you cant fit 105 digits into 64 bits — Creris, Jul 19 '15 at 19:11

Oncaphillis · Accepted Answer · 2015-07-19T21:02:10.607

1

If you look at the ttmath source there is a definition for UInt<N>::Add which iterates over the uint array table representing the UInt<N> value adding each element pair and carrying the overflow to the next iteration. Based on this iteration one may define a recursive templated implementation like this:

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

Add is all you need for the Fibonacci

edited Jul 19 '15 at 21:02

answered Jul 19 '15 at 20:38

Oncaphillis

1,888
13
15

The problem is that I need to pass a ttmath::Uint inside the template parameter with the current design. I guess it can be possible somehow with a different approach using constexpr for instance and call a fibonacci function with a very large return value. – coincoin Jul 19 '15 at 20:58
You simply have to replace `a + b` with `ttmath::Add(a.table,b.table,c.table,0)` in your orig. code See additions in my answer – Oncaphillis Jul 19 '15 at 21:04
Thank you but I don't see how your solution is done at compile time ? You just copied my fib function and modified it. This function worked fine ~~ wtf – coincoin Jul 19 '15 at 21:05
The iteration over `UInt::table[...]` which is done during runtime in the ttmath library has been replaced by a recursive template expansion in my approach. If your intention was to also replace the parameter `n` to `fib(n)` with an template arg nothing at all would be variable and the whole thing would be a constexpr anyway. It also could be done recursively but it definitely wouldn't be worth the fuzz (except for a nice homework or mental exercise). – Oncaphillis Jul 19 '15 at 21:12
`error: ‘Add’ is not a member of ‘ttmath’` it seems not available in last ttmath version unfortunately. I still don't understand why is your solution done at compile time ? The problem is not the `fib` function which works fine but rather on the meta `fibonacci` ! – coincoin Jul 19 '15 at 21:22
`ttmath::Add` is part of my example – Oncaphillis Jul 19 '15 at 21:32
Oh sorry right... Ok trying to understand how you did that thanks for the hard work ! (I still don't understand why it's compile time) – coincoin Jul 19 '15 at 21:40

Compile time fibonacci which handle large numbers

1 Answers1