Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Long integers handled with strings
// t10e26.longNatural.cpp
// juanfc 2022-01-17
// Juan Falgueras, 1997-11-25 al 2003-12-05
//
#include <iostream>
#include <iomanip>
using namespace std;
void test(string s1, string s2);
int main() {
test("1", "1");
test("2", "10");
test("122345", "90");
return 0;
}
// PROTOTYPES
string longAdding(string a, string b, int BASE=10);
string longMult(string a, string b, int BASE=10);
string longPow(string a, string b, int BASE = 10);
void test(string s1, string s2)
{
int w = s1.length()+s2.length()+1;
cout << " " << setw(w) << s1 << endl;
cout << " " << setw(w) << s2 << " = "<< endl;
cout << "+ : " << setw(w) << longAdding(s1,s2) << endl;
cout << "* : " << setw(w) << longMult(s1,s2) << endl;
cout << "^ : " << setw(w) << longPow(s1,s2) << endl << endl;
}
// BODYS
void stringRev(string& s);
string longAdding(string a, string b, int BASE)
{
string dest;
const int OO = ((int)'0');
stringRev(a);
stringRev(b);
int la = a.length();
int lb = b.length();
if (la < lb)
for (int i = la; i < lb; ++i)
a += '0';
else
for (int i = lb; i < la; ++i)
b += '0';
int carry = 0;
la = a.length();
for (int i=0; i < la ; i++) {
int t = carry;
t += a[i] - OO;
t += b[i] - OO;
dest += (t % BASE) + OO;
carry = t / BASE;
}
if (carry > 0)
dest += '1';
stringRev(dest);
return dest;
} // LongAdding
string longMult(string a, string b, int BASE)
{
string dest;
const int O = ((int)'0');
int lena, lenb, lend;
lena= a.length();
lenb= b.length();
stringRev(a);
stringRev(b);
lend= lena+lenb+1;
for (int i=0; i < lend; i++)
dest += '0';
for (int i= 0; i < lena; i++) {
for (int j= 0; j < lenb; j++) {
int carry;
int t= ((int)dest[i+j]-O) + ((int)a[i]-O) * ((int)b[j]-O);
dest[i+j]= (char)(t % BASE + O);
carry= t / BASE;
int k= 1;
do {
t= ((int)dest[i+j+k]-O) + carry;
dest[i+j+k]= (char)(t % BASE + O);
carry= t / BASE;
++k;
} while (carry > 0);
} // for
} // for
int j= dest.length() - 1;
while (j > 0 and dest[j] == '0')
--j;
dest = dest.substr(0, j+1);
stringRev(dest);
return dest;
} // longMult
string longPow(string a, string b, int BASE)
{
string cnt = "0";
string r = "1";
while (cnt != b) {
r = longMult(a, r, BASE);
cnt = longAdding(cnt, "1");
}
return r;
} // longPow
void stringRev(string& s)
{
int i = 0;
int j = s.length()-1;
while (i<j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
++i; --j;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment