Вычислить 100е число Фибоначчи

284
20 декабря 2016, 22:50

Всем привет. Такая проблема, я провожу исследования для сравнения различных методов реализации алгоритма вычисления числа Фибоначчи. Но получается что в 64 битной системе максимальное число 18446744073709551615. Его не хватает на 100е число Фибоначчи - 218922995834555169026. Как мне его можно уместить? Разумеется собирать массив из 100 чисел-строк - не подойдёт, нужно именно вычислить данное число (218922995834555169026).

Answer 1

Ну, еще раз вытащу из нафталина свой класс и применю его для вычисления чисел Фибоначчи :)

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
class superLong
{
public:
    using ullong = unsigned long long;
    superLong(ullong x = 0) { d.push_back(x); };
    superLong(string s);
    operator string() const;
    friend superLong operator *(const superLong&a, const superLong&b);
    friend superLong operator +(const superLong&a, const superLong&b);
private:
    // Хранение чисел для простоты в виде кусков по 9 десятичных цифр
    vector<ullong> d;
    static constexpr ullong max = 1000000000ull;
};

superLong operator *(const superLong&a, const superLong&b)
{
    superLong r;
    for(size_t i = 0, e = a.d.size(); i < e; ++i)
    {
        for(size_t j = 0, f = b.d.size(); j < f; ++j)
        {
            superLong::ullong v = a.d[i]*b.d[j];
            superLong::ullong carry = v/superLong::max;
            v = v%superLong::max;
            if (i+j >= r.d.size()) r.d.resize(i+j+1,0);
            r.d[i+j] += v;
            if (carry)
            {
                if (i+j+1 >= r.d.size()) r.d.resize(i+j+2,0);
                r.d[i+j+1] += carry;
            }
        }
    }
    for(size_t i = 0, e = r.d.size(); i < e-1; ++i)
    {
        if (r.d[i] > superLong::max)
        {
            r.d[i+1] += r.d[i] / superLong::max;
            r.d[i] %= superLong::max;
        }
    }
    return r;
}
superLong operator +(const superLong&a, const superLong&b)
{
    superLong d((a.d.size() > b.d.size()) ? a : b);
    superLong c((a.d.size() > b.d.size()) ? b : a);
    c.d.resize(d.d.size(),0);
    superLong::ullong carry = 0;
    for(size_t i = 0; i < d.d.size(); ++i)
    {
        d.d[i] += c.d[i]+carry;
        carry = d.d[i]/superLong::max;
        d.d[i] %= superLong::max;
    }
    if (carry) d.d.push_back(carry);
    return d;
}
superLong::superLong(string s)
{
    superLong q;
    int len = s.length()%9;
    if (len)
    {
        string val = s.substr(0,len);
        s = s.substr(len,s.length()-len);
        q = stoll(val);
    }
    while (s.length())
    {
        string val = s.substr(0,9);
        s = s.substr(9,s.length()-9);
        q = q * superLong::max + stoll(val);
    }
    d = std::move(q.d);
}
superLong::operator string() const
{
    string s;
    for(size_t i = 0; i < d.size(); ++i)
    {
        char buf[12];
        snprintf(buf,12,"%09lld",d[i]);
        s = buf + s;
    }
    int i = 0;
    while(s[i] == '0') ++i;
    if (s[i] == 0) --i;
    return s.substr(i);
}
superLong superPow(superLong x, unsigned long long p)
{
    superLong r(1);
    while(p)
    {
        if (p&0x01) r = r * x;
        p >>= 1;
        x = x*x;
    }
    return r;
}
int main(int argc, const char * argv[])
{
    superLong f0(1);
    superLong f1(1);
    for(int i = 3; i < 100; ++i)
    {
        superLong f = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    cout << string(f1) << endl<<endl;;
}
READ ALSO
В чем разница между константой x и &amp;xx?

В чем разница между константой x и &xx?

В чем разница между константой x и &xx?

284
Что такое standard-layout в C++ и зачем он нужен?

Что такое standard-layout в C++ и зачем он нужен?

Читал на английском, но так и не смог разобраться

259
Определение типа

Определение типа

Как определить тип результата арифметического выражения?

210
Реализовать иерархию классов [требует правки]

Реализовать иерархию классов [требует правки]

Реализовать иерархию классовВ каждом производном классе присутствует - конструктор инициализации, методы ввода-вывода данных, метод вычисления...

310