C ++大数算术 [英] C++ Large Number Arithmetic
问题描述
我正在开发一个大数字运算的类，现在它知道如何添加，处理cin和cout。
但它有非常有限和基本减法功能，并不知道如何处理负数。但这很容易解决。
我的问题是如何做乘法。
如何处理cin和cout这里。
对于cin，它将整数保存为值[500]，例如，50将被保存为值[498] [499]。但是不能值[0]和值[1]
对于cout，它将从值[0]扫描到值[499]然后从该非零值输出到结束。
<$ p 这是我的代码： $ p>
#include< iostream>
using namespace std;
class largeNumber {
public：
int value [500];
largeNumber（）
{
for（int i = 0; i <500; ++ i）
{
value [i] = 0;
}
}
//下面是算术运算
largeNumber operator +（const largeNumber& ln）const
{
largeNumber result;
for（int i = 0; i< 500; ++ i）
{
result.value [i] = value [i] + ln.value [i]
}
for（int i = 499; i> = 0; - i）
{
if（result.value [i]> = 10）
{
result.value [i-1] + =（result.value [i] / 10）;
result.value [i]％= 10;
}
}
返回结果;
}
largeNumber operator-（const largeNumber& ln）const
{
largeNumber result;
for（int i = 0; i <500; ++ i）
{
result.value [i] = value [i] - ln.value [i ];
}
for（int i = 499; i> = 0; - i）
{
if（result.value [i] <0）
{
--result.value [i-1];
result.value [i] + = 10;
}
}
返回结果;
}
largeNumber运算符*（const largeNumber& ln）const
{
largeNumber result;
for（int x = 499; x> = 0; - x）
{
for（int y = 499; y> = 0; - y）
{
int dx = 499 - x;
int dy = 499-y;
int dr = dx + dy;
int r = 499 - dr;
if（r> = 0&& r< = 499）
{
result.value [r] = value [x] * ln.value [y]
}
}
}
for（int i = 499; i> = 0; - i）
{
if（result.value [i]> = 10）
{
result.value [i-1] + =（result.value [i] / 10）;
result.value [i]％= 10;
}
}
返回结果;
}
//下面是cin，cout操作符
friend ostream& operator<<<（ostream& out，const largeNumber& ln）
{
bool valueFound = false;
for（int i = 0; i <500; ++ i）
{
if（ln.value [i]！= 0）
{
valueFound = true;
}
if（valueFound == true）
{
out<< ln.value [i];
}
}
if（valueFound == false）
{
out< 0;
}
return out;
}
friend istream& operator>>>（istream& in，largeNumber& ln）// input
{
string str;
在>> str;
int length = str.length（）;
for（int i = 500 - length; i <500; ++ i）
{
ln.value [i] =（str [length-（500-i）] - 48）;
}
return in;
}
};
int main（）
{
largeNumber a，b;
string op;
cin>> a>> op>> b;
cout<< a * b;
return 0;
}
我已经包括了我的方法来做乘法，但是它有缺陷。 / p>
顺便说一下，老师给出的数字承诺乘法的结果将是一个小于500位的数字。
让我们开始简单的乘法（长乘法）：
112 * 301
1 1 2
3 0 1
______________
1 1 2
0 0 0
3 3 6
_______________________
3 3 7 1 2
因此，这需要N乘N矩阵作为要移位n次添加的行。
你在这里做什么，
对于您的问题，它需要500 x 500乘法和500 x 500添加。 O（N * N）
Pro：每个数字乘法都可以在一个字节中完成，所以你可以改变你的编译器可以向量化代码的数字结构，
Con：太多计算（每500位数字接近25-40次迭代）
注意：GPU驱动的演算可以给它大约40倍的速度。如OpenCL或Cuda。
I'm developing a class for large number arithmetic, it now knows how to do addition, handle cin and cout.
It, however has very limited and basic subtraction functionality, and does not know how to handle negative. But that can be easily resolved.
My question is this, how to do multiplication.
I will detail how it handle cin and cout here.
For cin, it will save integers to value[500], for example, 50 will be saved to value[498] and value[499]. BUT NOT value[0] and value[1]
For cout, it will scan for the first non-zero value from value[0] to value[499], and then output from that non-zero value to the end. Also, if it finds no non-zero value, it will output 0.
Here's my code:
#include <iostream>
using namespace std;
class largeNumber {
public:
int value[500];
largeNumber()
{
for ( int i = 0 ; i < 500 ; ++ i )
{
value[i] = 0;
}
}
//below are arithmetic operations
largeNumber operator+(const largeNumber &ln) const
{
largeNumber result;
for ( int i = 0 ; i < 500 ; ++ i )
{
result.value[i] = value[i] + ln.value[i];
}
for ( int i = 499 ; i >= 0 ; -- i )
{
if ( result.value[i] >= 10 )
{
result.value[i - 1] += ( result.value[i] / 10 );
result.value[i] %= 10;
}
}
return result;
}
largeNumber operator-(const largeNumber &ln) const
{
largeNumber result;
for ( int i = 0 ; i < 500 ; ++ i )
{
result.value[i] = value[i] - ln.value[i];
}
for ( int i = 499 ; i >= 0 ; -- i )
{
if ( result.value[i] < 0 )
{
--result.value[i - 1];
result.value[i] += 10;
}
}
return result;
}
largeNumber operator*(const largeNumber &ln) const
{
largeNumber result;
for ( int x = 499 ; x >= 0 ; -- x )
{
for ( int y = 499 ; y >= 0 ; -- y )
{
int dx = 499 - x;
int dy = 499 - y;
int dr = dx + dy;
int r = 499 - dr;
if ( r >= 0 && r <= 499 )
{
result.value[r] = value[x] * ln.value[y];
}
}
}
for ( int i = 499 ; i >= 0 ; -- i )
{
if ( result.value[i] >= 10 )
{
result.value[i - 1] += ( result.value[i] / 10 );
result.value[i] %= 10;
}
}
return result;
}
//below are cin, cout operators
friend ostream& operator<<(ostream& out, const largeNumber& ln)
{
bool valueFound = false;
for ( int i = 0 ; i < 500 ; ++ i )
{
if ( ln.value[i] != 0 )
{
valueFound = true;
}
if ( valueFound == true )
{
out << ln.value[i];
}
}
if ( valueFound == false )
{
out << "0";
}
return out;
}
friend istream& operator>>(istream& in, largeNumber& ln) // input
{
string str;
in >> str;
int length = str.length();
for ( int i = 500 - length ; i < 500 ; ++ i )
{
ln.value[i] = (str[length-(500-i)] - 48);
}
return in;
}
};
int main()
{
largeNumber a, b;
string op;
cin >> a >> op >> b;
cout << a * b;
return 0;
}
I've included my way to do multiplication, however it is flawed.
By the way, the number given by teacher promised that the result of multiplication will be a number less than 500 digit.
Lets start with simple multiplication(Long multiplication):
112 * 301
1 1 2
3 0 1
______________
1 1 2
0 0 0
3 3 6
_______________________
3 3 7 1 2
So, this needs N by N matrix as rows to be added with shifting-n-times.
Where are you doing this addition and where is shifting?
For your question, it would need 500 x 500 multiplications and 500 x 500 additions. O(N*N)
Pro: each digit-multiplication can be done in a single byte so you can change the structure of digits that your compiler can vectorize the code and multiply 16 to 32 digits at once(unrolls quite good).
Con: too many computing(nearly 25-40 iteration per 500 digits-num)
Note: GPU-powered calculus could give it roughly 40x more speed. Such as OpenCL or Cuda.
这篇关于C ++大数算术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
