enter image description here enter image description here I have already asked for help a couple of times today and this is what happened. The program must perform raising to the power of long numbers. The number and degree are written in string. The problem - the construction seems to work, but randomly, in the literal sense of the word. With a degree greater than 10, sometimes it considers true, and sometimes incorrect values ​​in general. For example, if a = 25 and n = 30, the program should output 867361737988403547205962240695953369140625, and displays 9607807733118534088134765625. With a = 2555555555 and n = 25, some characters and random numbers are displayed ... Crackers are output when entering a large base. For example, 132 ^ 1000 considers true. 13265563353646646453454 ^ 165 also thinks wrong, but if you take smaller values, everything is fine. I check with tungsten. I do not know where to start, I can’t establish the pattern of the problem at all. I ask for help, it is very necessary, it remains to finish quite a bit !!! Thank.

#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"); }
  • And why do you have arrays A With only 100 characters cleared? .. There is more necessary. - pavel
  • There variable length in which accumulates the length of the number + 100 characters per stock. - Maxitt
  • And by the way, if you multiply the number of characters 20, then you will have the sum of 20 pairs of multiplications of single-valued numbers in the array C ... In short, the char does not fit exactly. Replace with int. - pavel
  • Yes, I replaced it with long long int, the values ​​have expanded, but not completely, if you enter a huge number, the situation is similar. Another problem in the wrong counting itself: fine values ​​are fine, if you enter very large, then the wrong answer in general. - Maxitt
  • Try to remake the very multiplication of 2 numbers. Keep the transfer and immediately write the correct number to the result. - avp

2 answers 2

It means so. To close the topic - running sketched multiplication, addition and exponentiation. Only - it is sketched for half an hour, it seems to work, but here and there it is tied up with strings :) - like normalization after multiplication instead of correct hyphenation.

About optimality does not have to say: (Nevertheless, it seems to work.

Only consultations on what does one or another line of code, I'm sorry, but - will not. Understand yourself. The numbers I keep for simplicity in the form of pieces of 9 digits.

 #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 = adsize(); i < e; ++i) { for(size_t j = 0, f = bdsize(); j < f; ++j) { superLong::ullong v = ad[i]*bd[j]; superLong::ullong carry = v/superLong::max; v = v%superLong::max; if (i+j >= rdsize()) rdresize(i+j+1,0); rd[i+j] += v; if (carry) { if (i+j+1 >= rdsize()) rdresize(i+j+2,0); rd[i+j+1] += carry; } } } for(size_t i = 0, e = rdsize(); i < e-1; ++i) { if (rd[i] > superLong::max) { rd[i+1] += rd[i] / superLong::max; rd[i] %= superLong::max; } } return r; } superLong operator +(const superLong&a, const superLong&b) { superLong d((adsize() > bdsize()) ? a : b); superLong c((adsize() > bdsize()) ? b : a); cdresize(ddsize(),0); superLong::ullong carry = 0; for(size_t i = 0; i < ddsize(); ++i) { dd[i] += cd[i]+carry; carry = dd[i]/superLong::max; dd[i] %= superLong::max; } if (carry) ddpush_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(qd); } 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; }
  • e-maxx.ru/algo/fft_multiply e-maxx.ru/algo/big_integer related links. - pavel
  • one
    Thanks, of course, but I just started to study with ++, we haven't even passed vectors and classes yet, so well, I copy the code - zero sense for me. I would bring my mind to mind, quite a bit left. It is only necessary to figure out why wrong counting sometimes happens !. Help me please. - Maxitt
  • It seems to me that I have an error in calculating the length variable - Maxitt

You made the right decision to keep the factors in reverse order of numbers.

However, it seems to me that simply multiplying 2 numbers is better programmed in a more obvious way, immediately recording the correct number in the result and remembering the transfer.

 /* Умножение целых десятичных чисел без знака 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; }

Try to modify your multiplication code in the same way and I think that everything will work.

Obviously, all intermediate multiplications can be done with such a representation of numbers when calculating a degree, i.e. translate back to the string only the final result.

Update

Here is an example of calculating a degree (with an exponent I operate on 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'; }
  • I can't integrate your piece of code into my method, some values ​​are output - Maxitt
  • @Maxitt, well, how easy it is to embed a mult() call into your code, I didn’t think up right away I wrote an example in the update of the answer. - avp