The essence of the question is how to act with very large numbers, to push an array and from there to take or how?

The binary construction algorithm itself:

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; } }

Thanks for any help!

  • Ready solutions / libraries are not forbidden? - Vladimir Gamalyan
  • @ Sanja And what does "binary exponentiation" mean? - Vlad from Moscow

2 answers 2

Already wrote once, I repeat ...

It means so. To close the topic - running sketched multiplication, addition and exponentiation. Only - it was sketched for half an hour, it seems to work, but in some places 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; }
  • Nitsche so, plus!))) - Majestio

to push an array and from there to take or how?

Thanks for any help!

The main advice - read the old and very reliable))) book "Системы счисления",С.В.Фомин,5-е издание,1987г. ( here you poured ).

The main question is “how to represent very large numbers?”. In our case there are three obvious variants of representations:

  • decimal representation (1 byte per 10-digit number, use, for example, std::vector<uint8_t> )
  • binary decimal representation (select 10 bits per decimal digit, for example, use std::vector<uint8_t> for pairs of digits, or std::bitset<разрядность>
  • binary representation (we do not use 10-digit numbering system for representation, we work strictly with binary, without options std::bitset<разрядность> )

The representations listed above require their “arithmetic”. The choice is yours, for there are always pros and cons. The complexity of implementation can pay off with greater speed and / or memory savings. Conversely, ease of implementation may require excessive resources.

Not in favor of perfectionism, but in fairness ...

Look on the net for materials on the topic “The Applied Theory of Digital Machines,” and the section on “multiplying by two digits at the same time.” Although it will most likely be about hardware implementations - do not worry, the theory is good. And in the software implementation, I hope, will not let you down. In the case of cyclic multiplications (and in your case this is the case), this approach will probably make it possible to significantly speed up operations. It is about replacing a large number of hardware multiplications by a smaller number of tabular samples and shifts with addition.

There are no obstacles to the patriots (C) DMB :-)