Я разрабатываю класс для арифметики большого числа, теперь он знает, как делать сложение, обрабатывать cin и cout.
Он, однако, имеет очень ограниченную и базовую функциональность вычитания и не знает, как обращаться с негативом. Но это может быть легко решено.
Мой вопрос заключается в том, как сделать умножение.
Я подробно опишу, как он справляется с Cin и Cout здесь.
Для cin будут сохранены целые числа в значение [500], например, 50 будет сохранено в значение [498] и значение [499]. НО НЕ значение [0] и значение [1]
Для cout он будет сканировать первое ненулевое значение от значения [0] до значения [499], а затем выводить это ненулевое значение до конца. Кроме того, если он не найдет ненулевое значение, он выведет 0.
Вот мой код:
#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;
}
Я включил свой способ умножения, однако он имеет недостатки.
Кстати, число, данное учителем, обещало, что результатом умножения будет число менее 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 х 500 умножений и 500 х 500 сложений. O (N * N)
Плюс: каждое умножение цифр может быть выполнено в одном байте, так что вы можете изменить структуру цифр, чтобы ваш компилятор мог векторизовать код и умножить от 16 до 32 цифр за один раз (разворачивается довольно хорошо).
Против: слишком много вычислений (почти 25-40 итераций на 500 цифр-чисел)
Примечание: исчисление на GPU может увеличить скорость примерно в 40 раз. Такие как OpenCL или Cuda.
Других решений пока нет …