Всем привет. Такая проблема, я провожу исследования для сравнения различных методов реализации алгоритма вычисления числа Фибоначчи. Но получается что в 64 битной системе максимальное число 18446744073709551615. Его не хватает на 100е число Фибоначчи - 218922995834555169026. Как мне его можно уместить? Разумеется собирать массив из 100 чисел-строк - не подойдёт, нужно именно вычислить данное число (218922995834555169026).
Ну, еще раз вытащу из нафталина свой класс и применю его для вычисления чисел Фибоначчи :)
#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;;
}
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Читал на английском, но так и не смог разобраться
Реализовать иерархию классовВ каждом производном классе присутствует - конструктор инициализации, методы ввода-вывода данных, метод вычисления...