乘以两个长整数C

我正在研究C中的一个程序，作为家庭作业的一部分，在这个程序中我必须得到两个长字符作为字符串的乘积。例如：123456789021和132456789098.由于它被视为一个字符串，我将它们转换为long long int来进行乘法运算。但是由此产生的产品将会非常大（我猜大于long long int）。任何人都可以请建议我一种方法来执行这种乘法？乘以两个长整数C

来源

2009-12-06 Light_handle

这里有一种方法：考虑如何在纸上手工乘以这些数字。实施C.这种方法，你必须发现：

如何打破了一个整数（表示为字符串）成数字
如何每个数字转换回一个整数0 <= d < 10
如何管理的数字阵列（即有多大，你应该做的阵列？）
如何编写循环（一个或多个），你可能需要实现乘法
如何管理携带来自一个数字产品到下一个
如何将这些数字转换为字符以便输出

来源

2009-12-06 19:13:26

如果它不是一个事实，即你的输入和输出都在基地10，你可以通过使用基数2^32（数字保持在64位类型）或基数2^16（以32位类型）而不是基数10来更有效地完成所有这些操作。 – 2009-12-06 23:10:48

您可以使用大型整数库arithmetik，Wikipedia有一个列表here。

来源

2009-12-06 19:19:48

尽管大数量的库通常是有帮助的，但我相信它会违背问题背后的思想和目的。 – Inisheer 2009-12-06 19:24:55

通常以字节数组表示的大整数。您可以在DLR中查看Microsoft的BigInteger实现。我认为他们已经使用Knuth开发的算法

来源

2009-12-06 19:20:43

另一种方法是将数字乘以float/double并在显示结果时指定小数。

来源

2009-12-06 19:28:35

这样做可能会损失很多精度。 – 2009-12-06 19:34:07

尽管如此，如果数字太多，那不会给出确切的答案。根据使用情况，这可能是足够好的，但我认为这不是这个任务的重点。 – 2009-12-06 19:41:23

检查这个BigInteger library和一个very basic sample code世界七。

如果你有兴趣在C（仅乘法）我的一些家常代码：

//////////////////////////////////////////////////////////////////////////////// 

Code removed after I checked the home-work tag ;) 

///////////////////////////////////////////////////////////////////////////////////////

这工作在一些我曾参与早期的编程竞赛;）但是，如果你正在寻找甚至更快的乘法算法可以实现Karatsuba algorithm，我现在亲自使用这个实时比赛。

来源

2009-12-07 04:12:22

（第一个链接是_Mahbub Murshed Suman_的_BigInteger class_（版本6.7.28，2004年7月30日），第二个来自_World of Seven-Competitive Programming_，即使URL是“steven”。） – greybeard 2016-02-05 14:28:53

嗨，哥们，看看这个，我刚刚完成了它的昨天一天，我的功课的一部分：

#include<stdio.h> 
#include<string.h> 

int main() 
{ 
    char one[195]; 
    char two[195]; 
    char temp[195]; 
    int a[195],c[195],b[195]; 
    int x,i,j,k,l,p,add; 

    for(;;)/*determining the larger number...*/ 
    { 
     printf("Input A:"); 
      gets(one); 
     printf("Input B:"); 
      gets(two); 

     k=strlen(one); 
     l=strlen(two); 
     if(l>k) 
     { 
      strcpy(temp,one); 
      strcpy(one,two); 
      strcpy(two,temp); 
      break; 
     } 
     else 
     { 
      break; 
     } 
    } 
     k=strlen(one); 
     l=strlen(two); 
    for(p=0;p<195;p++)/*assigning all initial values to 0*/ 
    { 
     a[p]=0; 
     b[p]=0; 
     c[p]=0; 
    } 

    for(i=0;one[i];i++)/*converting char to integer(note:1,as a character assigned as 49.)*/ 
    { 
     a[i]=((one[--k])-48); 
    } 

    for(i=0;i<two[i];i++) 
    { 
     b[i]=((two[--l])-48); 
    } 


    for(i=0;i<=strlen(two);i++)/*main algorithm*/ 
    { 
     add=0; 
     p=0; 
     for(j=i;j<=(2*strlen(one)-1);j++) 
     { 
      x=c[j]+b[i]*a[p]+add; 
      c[j]=x%10; 
      add=x/10; 
      p++; 
     } 
    } 

    printf("\nMultiplication:"); 
    for(p=(2*strlen(one)-1);p>=0;p--) 
    { 
     if(p>strlen(one)&&c[p]==0) 
     { 
      continue; 
     } 
     printf("%d",c[p]); 
    } 
    printf("\n"); 
}

来源

2011-04-18 19:32:29

乘以两个长整数C

回答

相关问题