c++ - 函数在 karatsuba 乘法中返回 0

Question

我正在尝试通过递归调用来实现 Karatsuba 乘法。下面的代码应该可以工作，但我一直得到零作为答案。有什么想法吗？

#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;
  }
 } 

Answer 1

在这个循环之后：

while(p)
{
  p=p/10;
  n++;
}

的值p为零。您的递归停止在

if(n<2)
{
  return p*q;
}

因此，无论输入是什么，结果都是零。

Answer 2

您可能想在循环中使用pfor 计算的副本。这样你就可以保留 p 的值。像这样的东西：nwhile

ll pd = p;
while(pd)
{
  pd=pd/10;
  n++;
}