Я пытаюсь создать эффективную программу для умножения больших чисел и придумала следующее решение: -
#include <iostream>
using namespace std;
string Addem(string a,string b) // To add two large numbers,only for +ve numbers
{
string c;
int n=a.size(),m=b.size();
if(m>n)
{
swap(n,m);
swap(a,b);
}
for(int i=0; i<n-m; i++) // adding zeros to make lengths of both string equal.
b='0'+b;
int carry=0,curr=0;
for(int i=n-1; i>-1; i--)
{
curr=a[i]-'0'+b[i]-'0'+carry; //basic school math to find sum, using
carry=curr/10; //two variables to find sum of each place individually
curr=curr%10; //and passing carry to the next position.
c=(char)(curr+'0')+c;
if(i==0 && carry)
{
c=(char)(carry+'0')+c;
}
}
while(c[0]=='0' && c.size()!=1) //removing any leading zeros
c.erase(0,1);
return c;
}
string Multiplyem(string a,string b) // To multiply two large numbers.
{
bool sign=1;
if( (a[0]=='-' && b[0]=='-') || (a[0]!='-' && b[0]!='-') )
sign=0;
if(a[0]=='-')
a.erase(0,1); //taking care of sign.
if(b[0]=='-')
b.erase(0,1);
if(a=="0" || b=="0")
return "0";
string c;
int curr=0,carry=0;
int n=a.size(),m=b.size();
for(int i=m-1; i>-1; i--)
{
string tmp; //string to store result of a*(current digit of b)
for(int j=n-1; j>-1; j--)
{
curr=carry+(b[i]-'0')*(a[j]-'0'); //scroll down for this,explained
carry=curr/10; //the logic for this under EDIT
curr=curr%10;
tmp=(char)(curr+'0')+tmp;
if(j==0 && carry)
{
tmp=(char)(carry+'0')+tmp;
}
}
for(int j=m-1; j>i; j--) //adding zeros take care of number positions
tmp+='0';
c=Addem(tmp,c); //adding tmp to c
carry=0,curr=0;
}
while(c[0]=='0' && c.size()!=1) // removing any leading zeros (if any)
c.erase(0,1);
if(sign==1 && c!="0") //adding sign (if reqired)
c='-'+c;
return c;
}
int main()
{
string a,b;
cin>>a>>b;
cout<<"Multiplication = "<<Multiplyem(a,b)<<" \n \n";
}
, насколько я вижу, сложность O (m * n), но,когда я действительно пробую это, это занимает слишком много времени.Я попробовал тот же тестовый пример на другом коде с, по-видимому, такой же сложностью, но он выполняется за 0,04 секунды.тогда как мой занимает 1,02 сек.
раствор GFG (занимает 0,04 сек)
Мое решение (занимает около секунды)
Любая помощь по этому вопросу приветствуется.
РЕДАКТИРОВАТЬ: я добавил несколько комментариев, если это поможет, в основном то, что я делаю, это взять последнюю цифру одного числа и умножить его на другое число (т.е. tmp =b [m-1] * a) и сохраняя его в строке (скажем, c), повторяя это со второй последней цифрой (tmp = b [m-2] * a), добавляя ноль в конце строки (позаботиться о десятке) и добавив это к строке c, используя функцию Addem, определенную выше (в основном, c = c + tmp * 10), повторяя процесс до тех пор, пока у нас не закончатся цифры, увеличивая число ноль додобавлено в конце строки.Это должно занять O (m * n).
Я подозреваю, что это связано с использованием оператора + или std :: erase, поскольку std :: erase занимает O (n) времени, но я не совсем уверен.