1

введите сюда описание изображениявведите сюда описание изображенияЯ уже пару раз сегодня просил помощи и вот что получилось. Программа должна выполнять возведение в степень длинных чисел. Число и степень записаны в string. Проблема - возведение вроде и работает, но рандомно, в прямом смысле слова. При степени больше 10 иногда считает верно, а иногда вообще некорректные значения. Например, при a=25 и n=30 программа должна вывести 867361737988403547205962240695953369140625, а выводит 9607807733118534088134765625. При a=2555555555 и n=25 выводятся вообще какие-то символы и цифры случайные... Кракозябры выводятся при вводе большого основания. Например 132^1000 считает верно. Также неверно считает и 13265563353646646453454^165, но если взять значения поменьше, то все отлично. Проверяю с помощью вольфрамальфа. Я уже не знаю с чего начать, вообще не могу установить закономерность проблемы. Прошу помощи, очень надо, осталось совсем немного доработать!!! Спасибо.

#include "stdafx.h"
#include <string>
#include <iostream>
#include <climits>
using namespace std;
 char A[100000000],B[100], C[10000000000];
 long long int length;
void DeleteNull(string &str){
    int i = 0;
    while(str[i] == '0'|| str[i] < '0' || str [i] > '9')
        i++;
    str.erase(0,i);
}
void inc(string &s){
    int l = s.length();
    bool state = true;
    for(int i = l-1; state && i >= 0; --i)
    {
        if (state) 
            s[i]++;
        if (state = (s[i] > '9')) 
            s[i] = '0';
    }
    if (state) 
        s = '1' + s;
}
void Umnoj(string &a, string &temp, int size){
    temp="";
    for (int ix = 0; ix < length+100; ix++){
        C[ix] = 0;
        A[ix] = 0;
    }
    for (int i=0; i<a.size(); i++)
        A[i]=a[a.size()-i-1]-'0';
    length += size+1;   
    for (int ix = 0; ix < a.size(); ix++)
        for (int jx = 0; jx < size; jx++)
            C[ix + jx] += A[ix] * B[jx];
    for (int ix = 0; ix < length-1; ix++)
    {
        C[ix + 1] +=  C[ix] / 10;
        C[ix] %= 10;
    }
    while (C[length] == 0)
        length-- ;
    for(int i=length; i>-1; i--)
        temp+=C[i]+'0';//перевод числа в string
    DeleteNull(temp);//удаление всякого мусора перед числом
    a=temp;
}
int main()
{
    string a,n,t,count="1",temp;
    int size;   
    // cin>>a;
    // cin>>n;
    a="13444645";//основание
    n="30";//степень
    size=a.size();
    temp=a;
    length=size;
    for (int i=0; i<size; i++)
        B[i]=a[a.size()-i-1]-'0';
    while(n.compare(count)!=0){     
        inc(count);
        Umnoj(a,temp,size);
    }
    cout<<a<<endl;
    system("PAUSE");    
}
5
  • А почему у вас массивы А С только 100 символов очищаются?.. Там побольше надо.
    – pavel
    27 ноя 2016 в 8:38
  • Там переменная length в которой накапливается длина числа + 100 символов на запас.
    – Maxitt
    27 ноя 2016 в 8:39
  • А кстати, если вы умножите число знаков 20, то у вас в массив C пойдёт сумма 20 пар умножений однозначных чисел... Короче в char не влезет точно. Замените на int.
    – pavel
    27 ноя 2016 в 8:42
  • Да, заменил на long long int, занчения расширились, но не до конца, если ввести огромное число, ситуация аналогично. Другая проблема в неправильном подсчете самом: мелкие значения считает отлично, если вводить очень большие, то неправильный ответ вообще.
    – Maxitt
    27 ноя 2016 в 8:49
  • Попробуйте переделать само умножение 2-х чисел. Храните перенос и сразу пишите в результат правильную цифру.
    – avp
    27 ноя 2016 в 15:28

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;
}
3
  • e-maxx.ru/algo/fft_multiply e-maxx.ru/algo/big_integer ссылки по теме.
    – pavel
    27 ноя 2016 в 8:47
  • 1
    Спасибо конечно, но вот я только начал изучать с++, векторы и классы мы даже не проходили еще, так что ну скопирую я код - толку ноль для меня. Мне бы мой довести до ума, совсем немного осталось. Надо только разобраться, почему иногда происходит неправильный подсчет!. Помогите пожалуйста.
    – Maxitt
    27 ноя 2016 в 8:59
  • Мне кажется, что у меня ошибка в подсчете переменной length
    – Maxitt
    27 ноя 2016 в 9:47
1

Вы приняли правильное решение хранить сомножители с обратным порядком цифр.

Однако, мне кажется, что просто умножение 2-х чисел лучше запрограммировать более очевидным способом, сразу записывая в результат правильную цифру и запоминая перенос.

/* 
   Умножение целых десятичных чисел без знака
   c = a * b
   a[], b[] содержат значимые цифры чисел в обратном порядке
   (старшие цифры числа справа), 
   la -- количество цифр в a[]
   lb -- количество цифр в b[]
   Результат получается в массиве c[], 
   под который в вызывающем коде должно быть выделено достатчно памяти (la + lb)
   Возвращает количество значимых цифр в результате
*/
int
mult (char a[], int la, char b[], int lb, char c[])
{
  int cc = 0,     // цифра переноса
    lc = la + lb; // максимальное количество значимых цифр результата


  for (int i = 0; i < lc; i++)
    c[i] = 0;
  for (int i = 0; i < la; i++) {
    for (int j = 0; j < lb; j++) {
      int r = c[i + j] + cc + a[i] * b[j];
      c[i + j] = r % 10;
      cc = r / 10;
    }
    c[i + lb] = cc;
    cc = 0;
  }

  return c[lc - 1] ? lc : lc - 1;
}

Попробуйте модифицировать свой код умножения таким же образом и думаю, что все будет работать.

Очевидно, что все промежуточные умножения при вычислении степени можно делать именно с таким представлением чисел, т.е. переводить обратно в строку только окончательный результат.

Update

Вот пример вычислений степени (с показателем степени оперирую в int)

#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>

using namespace std;

int
mult (char a[], int la, char b[], int lb, char c[])
{
   ....
}

int 
main (int ac, char *av[])
{
  string s = av[1] ? av[1] : "123";
  int p = av[1] && av[2] ? atoi(av[2]) : 2;

  if (p < 1) {
    cout << "invalid power: " << p << '\n';
    return 1;
  }
  int i, j, l = s.size(), lr = l;
  char a[l];
  for (i = l - 1, j = 0; i >= 0; --i)
    if (s[i] >= '0' && s[i] <= '9')
      a[j++] = s[i] - '0';
    else {
      cout << "invalid number: " << s << '\n';
      return 1;
    }

  char b[l * p + 1], r[l * p + 2];
  cout << s << " ** " << p << " = ";

  memcpy(b, a, l);
  while (--p) {
    lr = mult(a, l, b, lr, r);
    if (p > 1)
      memcpy(b, r, lr);
  }

  for (i = 0, j = lr - 1; i < j; i++, j--) {
    r[i] += '0';
    char t = r[j] + '0';
    r[j] = r[i];
    r[i] = t;
  }
  if (i == j)
    r[i] += '0';
  r[lr] = 0;

  cout << r << '\n';
}
2
  • не получается интегрировать ваш кусок кода в мой метод, лишний значения выводятся какие-то
    – Maxitt
    27 ноя 2016 в 16:31
  • @Maxitt, ну, как легко встроить вызов mult() в ваш код, сходу не придумал. Написал в update ответа свой пример.
    – avp
    27 ноя 2016 в 18:36

Ваш ответ

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

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