2

Суть вопроса в том, как поступить при очень больших числах, в массив запихать и оттуда брать или как?

Сам алгоритм бинарного возведения:

int bistep(unsigned  int a,unsigned  int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow (a, n-1) * a;
    else {
        int b = binpow (a, n/2);
        return b * b;
    }
}

спасибо за любую помощь!

2
  • Готовые решения/библиотеки не возбраняются? 14 дек 2016 в 16:36
  • @Саня А что означает "бинарное возведение в степень"? 14 дек 2016 в 16:45

2 ответа 2

1

Уже писал один раз, повторюсь...

Значит, так. Чтоб закрыть тему - бегом набросал умножение, сложение и возведение в степень. Только - набросано за полчаса, вроде работает, но кое-где веревочками перевязано :) - типа нормализации после умножения вместо корректного расписывания переносов.

Об оптимальности говорить не приходится :( Тем не менее вроде работает.

Только консультаций по тому, что делает та или иная строчка кода, простите, но - не будет. Разбирайтесь сами. Числа храню для простоты в виде кусков по 9 цифр.

#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:
    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;
    }
    return s;
}

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 l1("111111111111111111111253672373");
    superLong l2("552345678012345678012898234897");
    cout << string(l1*l2) << endl<<endl;;
    cout << string(superPow(2,1000)) << endl;
}
1
  • Ниче так, плюсую!)))
    – Majestio
    14 дек 2016 в 20:28
0

в массив запихать и от туда брать или как?

спасибо за любую помощь!

Самый главный совет - почитайте старенькую и очень надежную))) книжку "Системы счисления",С.В.Фомин,5-е издание,1987г. (вот вам залил).

Самый главный вопрос - "как представлять очень большие числа?". В нашем случае очевидных вариантов представлений три:

  • десятичное представление (1 байт на 10-чную цифру, используем, например, std::vector<uint8_t>)
  • двоично-десятичное представление (на 10-чную цифру выделяем 4 бита, используем например std::vector<uint8_t> для пар цифр, или std::bitset<разрядность>
  • двоичное представление (не используем для представления 10-чную систему счисления, работаем строго с двоичной, без вариантов std::bitset<разрядность>)

Перечисленные выше представления требуют свою "арифметику". Выбор за вами, ибо всегда есть плюсы и минусы. Сложность реализации может окупиться большей скоростью и/или экономией памяти. И наоборот, простота реализаций может потребовать излишних ресурсов.

Не в угоду перфекционизму, а справедливости ради...

Поищите в сети материалы на тему "Прикладная теория цифровых автоматов", и раздел, об "умножении на два разряда одновременно". Хотя там речь пойдет скорее всего об аппаратных реализациях - не пугайтесь, теория хороша. И в программной реализации, надеюсь, не подведет. В случае циклических умножений (а в вашем случае это именно так), данный подход возможно позволит значительно ускорить операции. Речь идет о замене бОльшого числа аппаратных умножений, на мЕньшее количество табличных выборок и сдвигов со сложением.

Нет преграды патриотам (С) ДМБ :-)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.