Функция возвращает 0 при умножении каратсуба
Я пытаюсь реализовать умножение Карацубы с помощью рекурсивных вызовов. Код ниже должен работать, но я продолжаю получать ноль в качестве ответа. Какие-нибудь мысли?
#define ll long long int
ll kmul(ll p, ll q)
{
ll a,b,c,d,ans;
ll n=0;
while(p)
{
p=p/10;
n++;
}
//cout<<n<<endl;
if(n<2)
{
return p*q;
}
else
{
int k=n/2;
ll j=pow(10,k);
a=p/j;
b=p%j;
c=q/(j);
b=q%j;
ans=(pow(10,n)*(kmul(a,c)))+(j*kmul(a,d)*kmul(b,c))+kmul(b,d);
return ans;
}
}
Решение
После этого цикла:
while(p)
{
p=p/10;
n++;
}
Значение p это ноль. Ваша рекурсия останавливается на
if(n<2)
{
return p*q;
}
Таким образом, независимо от того, что является входом, вы получите ноль в качестве результата.
Другие решения
Вы можете использовать копию p для расчета n в while петля. Таким образом, вы можете сохранить значение р. Что-то вроде этого:
ll pd = p;
while(pd)
{
pd=pd/10;
n++;
}