/*
Name: 高精度運算
Copyright:始發于goal00001111的專欄；允許自由轉載，但必須注明作者和出處
Author: goal00001111
Date: 01-12-08 15:04
Description:
高精度運算：加減乘除，乘方，階乘
*/
#include<iostream>
#include<string>
using namespace std;
void Reverse(string & str);
void AddInt(string & c, string a, string b);
void SubInt(string & c, string a, string b);
void MulInt(string & c, string a, string b);
void JieCHInt(string & c, string b);
void DivInt(string & c, string a, string b);
void PowInt(string & c, string a, string b);
int main()
{
string a, b, c;
cin >> a >> b;
AddInt(c, a, b);
cout << a << " + ";
cout << b << " = " << endl;
cout << c << endl;
SubInt(c, a, b);
cout << a << " - ";
cout << b << " = " << endl;
cout << c << endl;
MulInt(c, a, b);
cout << a << " * ";
cout << b << " = " << endl;
cout << c << endl;
//
// cin >> b;
// JieCHInt(c, b);
// cout << b << " ! = " << endl;
// cout << c << endl;
//
DivInt(c, a, b);
cout << a << " / ";
cout << b << " = " << endl;
cout << c << endl;
// PowInt(c, a, b);
// cout << a << " ^ ";
// cout << b << " = " << endl;
// cout << c << endl;
system("pause");
return 0;
}
void Reverse(string & str)
{
int left, right;
left = 0; right = str.size()-1;
while (left < right)
{
char ch = str[left];
str[left] = str[right];
str[right] = ch;
left++; right--;
}
}
void AddInt(string & c, string a, string b)//模仿遞增向量的合并方法
{
c.resize(0);
Reverse(a);
Reverse(b);
//逆序計算a+b，則從低位開始計算
int i, carry;
i = carry = 0;
while (i < a.size() && i < b.size())
{
c += (a[i]-'0' + b[i]-'0' + carry) % 10 + '0';
carry = (a[i]-'0' + b[i]-'0' + carry) / 10;
i++;
}
while (i < a.size())
{
c += (a[i]-'0' + carry) % 10 + '0';
carry = (a[i]-'0' + carry) / 10;
i++;
}
while (i < b.size())
{
c += (b[i]-'0' + carry) % 10 + '0';
carry = (b[i]-'0' + carry) / 10;
i++;
}
while (carry > 0)//計算進位部分
{
c += carry % 10 + '0';
carry /= 10;
}
i = c.size() - 1;
while (c[i] == '0')//消除多余的高位0
{
i--;
}
c = c.substr(0, i+1);
Reverse(c);
}
void SubInt(string & c, string a, string b)//模仿遞增向量的合并方法
{
c.resize(0);
if (a == b)
{
c += '0';
return ;
}
bool flag = false;
if (a.size() < b.size() || (a.size() == b.size() && a < b))//交換，并得到一個負號
{
flag = true;
string temp = a;
a = b;
b = temp;
}
Reverse(a);
Reverse(b); ;
int i = 0;
while (i < b.size())
{
if (a[i] >= b[i])
c += a[i] - b[i] + '0';
else
{
a[i+1] -= 1;
c += a[i] + 10 - b[i] + '0';
}
i++;
}
while (i < a.size())
{
if (a[i] < '0')
{
a[i+1] -= 1;
a[i] += 10;
}
c += a[i];
i++;
}
i = c.size() - 1;
while (c[i] == '0')//消除多余的高位0
{
i--;
}
c = c.substr(0, i+1);
if (flag)
c += '-';
Reverse(c);
}
void MulInt(string & c, string a, string b)
{
c.resize(0);
if (a == "0" || b == "0")
{
c += '0';
return ;
}
Reverse(a);
Reverse(b);
string ta, tb, tc;
int carry = 0;
for (int i=0; i<b.size(); i++)
{
tc.resize(0);
for (int j=0; j<i; j++)//先在臨時和tc的低位補足0
tc += '0';
carry = 0;
for (int j=0; j<a.size(); j++)
{
tc += ((a[j]-'0') * (b[i]-'0') + carry) % 10 + '0';
carry = ((a[j]-'0') * (b[i]-'0') + carry) / 10;
}
while (carry > 0)//計算進位部分
{
tc += carry % 10 + '0';
carry /= 10;
}
//累加到c中
ta = c;
Reverse(ta);
Reverse(tc);
AddInt(c, ta, tc);
Reverse(c);
//消除多余的高位0
int pos = c.size() - 1;
while (c[pos] == '0')
{
pos--;
}
c = c.substr(0, pos+1);
}
Reverse(c);
}
void JieCHInt(string & c, string b)
{
string tb = "2";
c = "1";
while (tb.size() < b.size() || (tb.size() == b.size() && tb <= b))
{
MulInt(c, c, tb);
AddInt(tb, tb, "1");
}
}
void DivInt(string & c, string a, string b)
{
c.resize(0);
if (a == "0" || b == "0")
{
c += '0';
return ;
}
string copyA = a;//存儲a的值，之后a的值會變化
while (a == b || a.size() > b.size() || (a.size() == b.size() && a > b))//直到余數小于除數
{
for (int n=1; n<=a.size(); n++)
{
string ta = a.substr(0, n);//提取不小于除數的部分被除數
if (ta == "0") //是0直接跳過
{
c += '0';
a = a.substr(n, a.size()-n);
break;
}
if (ta == b)//相等，商為1，被除數去掉前n位
{
c += '1';
a = a.substr(n, a.size()-n);
break;
}
else if (ta.size() > b.size() || (ta.size() == b.size() && ta > b))//被除數不小于除數
{
char i = 0;//記錄商
string tb = b;
while (ta.size() > tb.size() || (ta.size() == tb.size() && ta > tb))//用多次減法實現除法運算
{
AddInt(tb, tb, b);
i++;
}
if (ta == tb)//整除
{
c += i + '1';
a = a.substr(n, a.size()-n);
break;
}
else//余數不為0
{
c += i + '0';
int pos = ta.size(); //記錄上一次被除數的增添位置
SubInt(tb, tb, b);//再減回去，使tb < ta
SubInt(ta, ta, tb);//獲取余數
n = ta.size();//下一次增添被除數位置
ta += a.substr(pos, a.size()-pos);//得到新的被除數
a = ta;
}
}
else//被除數小于除數，商為0
{
c += '0';
}
}
}
while (copyA.size() > c.size())//補足低位的0
c += '0';
//消除多余的高位0
int pos = 0;
while (pos < c.size() && c[pos] == '0')
{
pos++;
}
c = c.substr(pos, c.size()-pos);
if (c.size() == 0)//商為0
c = "0";
}
void PowInt(string & c, string a, string b)
{
c.resize(0);
if (a == "0")
{
c = "0";
return ;
}
if (b == "0")
{
c = "1";
return ;
}
if (b == "1")
{
c = a;
return ;
}
string tb;
DivInt(tb, b, "2");
PowInt(c, a, tb);
MulInt(c, c, c);
if ((b[b.size()-1]-'0')%2 == 1)
MulInt(c, c, a);
}