精华内容
下载资源
问答
  • 大数运算c语言代码

    2013-11-01 20:08:42
    C语言无符号整形的大数加法和乘除法的源代码,自己编译通过,并且加有自己理解的注释!大数除法.cpp 大数乘法.cpp 大数加法.cpp
  • 大数运算C语言实现

    千次阅读 2019-04-19 00:26:42
    利用字符数组进行大数乘法的位运算 #include<stdio.h> #include<math.h> #include<string.h> void print_cheng(char s1[],char s2[]); void main() { char s1[1000],s2[1000]; while...

    大数乘法

    利用字符数组进行大数乘法的位运算

    #include<stdio.h>
    #include<math.h>
    #include<string.h>
    void print_cheng(char s1[],char s2[]);
    void main()
    {
    char s1[1000],s2[1000];
    while(scanf("%s%s",s1,s2))
    print_cheng(s1,s2);
    }
    
    void print_cheng(char s1[],char s2[])
    {
    int a[1000],b[1000],c[1000]={0};
    //当然用memset(c,0,sizeof(c));且应用memset方法需要调用#include<>是等价于c[1000]={0},同样表示将c数组全部初始化为0
    int i,j;
    int len_a,len_b,len;
    len_a=strlen(s1);  len_b=strlen(s2);
    printf("s1=%d  s2=%d  ",len_a,len_b);
    len=len_a+len_b;                   //两个大数相乘所得的结果的最大项便是len_a+len_b
    
    	for(i=0;i<len_a;i++)           //将大数s1倒序传递给整型数组a
    		a[i]=s1[len_a-1-i]-'0';
    	
    	for(i=0;i<len_b;i++)      //将大数s2倒序传递给整型数组b
    		b[i]=s2[len_b-1-i]-'0';
    
    	for(i=0;i<len_a;i++)
    		for(j=0;j<len_b;j++)
    			c[i+j]+=a[i]*b[j];   //用大数b的每一项乘以大数a的所有项
    
    		for(i=0;i<len;i++){    //进位取整
    			if(c[i]>=10){
    			c[i+1]+=c[i]/10;
    			c[i]%=10;
    			}
    		}  //此时i的值为len
    
    		i=len-1;   
    		if(c[i]==0)i--;    //判断首位是否为零
    		if(i<0)printf("0");   
    		else{
    		for(;i>=0;i--)
    			printf("%d",c[i]);   //倒序输出结果
    		}
    printf("\n");
    }
    

    大数加法

    利用字符数组进行大数加法的位运算

    #include<stdio.h>
    #include<string.h>
    void print_Big(char a[],char b[]);
    void main()
    {
    char a[1000],b[1000];
    scanf("%s%s",a,b);
    print_Big(a,b);
    }
    
    //大数求和
    void print_Big(char a[],char b[])
    {
    char c[1000];    //定义字符数组c并且初始化使其a[0]为1,其他为0;    用于存放大数求和后的结果
    int i,sum,t=0;
    int len,len_a,len_b;
    len_a=strlen(a); 
    len_b=strlen(b);
    len=strlen(a)>strlen(b)? strlen(a):strlen(b);
    c[len+1]='\0';   //使其和的最大项的可能的项的后一项赋空
    		for(i=0;i<len;i++)     //进行倒序相加,从最小为开始相加
    		{
    			if(len_a-1-i>=0&&len_b-1-i>=0){     //满10进位,不满则不进位
    			sum=a[len_a-1-i]-'0'+b[len_b-1-i]-'0'+t;
    			c[len-i]=sum%10+'0';
    			t=sum/10;
    			}
    			else if(len_a-1-i>=0&&len_b-1-i<0){
    				sum=a[len_a-1-i]-'0'+t;
    				c[len-i]=sum%10 + '0' ;
    				t=sum/10;
    			}
    			else if(len_a-1-i<0&&len_b-1-i>=0){
    				sum=b[len_b-1-i]-'0'+t;
    				c[len-i]=sum%10+'0';
    				t=sum/10;
    			}
    		}
    	c[0]='0'+t;
    	//正序输出
    	if(c[0]=='0')printf("%s\n",c+1);    //如果第一位为0,便从a[1]开始输出
    	else printf("%s\n",c);     //第一位不为0,直接输出
    }
    
    

    大数阶乘

    利用整型数组进行大数阶乘的位运算

    #include<stdio.h>
    void print_Big(int n);
    void main()
    {
    int n;  
    while(1){
    	scanf("%d",&n);
    	print_Big(n);
    }
    }
    
    //大数阶乘
    void print_Big(int n)
    {
    int i,j,len;
    int a[1000]={1};
    	if(n<0){printf("error\n"); return; }
    	else if(n==1||n==0){printf("%d\n",1); return; }
    	
    	len=1;   //大数阶乘前,它的位数为1位
    	for(i=2;i<=n;i++)
    	{
    	int t=0;  int sum;
    		for(j=0;j<len;j++)
    		{
    		sum=a[j]*i+t;     
    		a[j]=sum%10;
    		t=sum/10;
    		//进位的条件是:进位数t不等于0,并且算到最后现有的最高项
    		if(t!=0&&j==len-1)len++;
    		}
    	}
    	//倒叙输出
    	for(i=len-1;i>=0;i--)
    		printf("%d",a[i]);
    printf("\n");
    }
    

    大数幂

    利用整型数组进行大数幂的位运算

    //大数幂
    #include<stdio.h>
    void print_Big(int x,int n);
    void main()
    {
    int x,n;
    	while(1){
    		scanf("%d%d",&x,&n);  //x的n次方
    		print_Big(x,n);  
    	}
    }
    
    void print_Big(int x,int n)
    {
    int a[100000]={1};
    int i,j,t,sum,len=1;   //默认阶乘初始项数为1
    	if(n==0){ printf("%d\n",1); return ; }
    	for(i=1;i<=n;i++){
    		t=0;
    		for(j=0;j<len;j++){
    			sum=a[j]*x+t;
    			a[j]=sum%10;
    			t=sum/10;
    			if(t!=0&&j==len-1)
    				len++;
    		}
    	}
    	for(i=len-1;i>=0;i--)
    		printf("%d",a[i]);
    	printf("\n");
    }
    

    多次运用函数进行大数运行,是为了方便代码的移植性
    本人新手程序员,都是个人的代码感悟,可能不够简洁,老练,但新手易懂
    代码会友交天下朋友,用心处事结四海豪杰
    第一次写,若有瑕疵还请见谅。
    自写代码,如有雷同纯属意外。
    在这里插入图片描述

    展开全文
  • 大数运算-RSA-c语言大数运算

    热门讨论 2009-03-04 12:55:06
    大数运算 RSA c语言大数运算库 英文PDf 中文PDF 源码
  • 大数运算C语言

    2012-07-10 13:30:17
    大数的加减乘除 C语言版 可以进行大数加法大数减法大数乘法大数除法
  • C语言大数运算-大数运算库篇

    千次阅读 2017-04-04 16:38:26
    big.h就是头文件只要将函数的声明放到该文件中,然后在其它程序中引用该文件就可以使用大数运算的方法。重复的代码我就不再写了,其实有了算法你们自己就可以实现,所以我就简单的说几句。文件命名: 头文件: b

    前言 :
    通过前面的3篇文章我们已经实现了大数的四则运算,本篇博客我们会把这是几个个方法做成一个库文件,可以供自己日后使用。细心的读者可能意到了,每个程序都引用了big.h但是都被注释掉了。big.h就是头文件只要将函数的声明放到该文件中,然后在其它程序中引用该文件就可以使用大数运算的方法。重复的代码我就不再写了,其实有了算法你们自己就可以实现,所以我就简单的说几句。

    文件命名:
    头文件: big.h 源码在本篇
    大数加法:big_add.c 完整源码在加法篇
    大数减法:big_sub.c 完整源码在减法篇
    大数乘法:big_mul.c 完整源码在乘除法篇
    大数除法:big_div.c 完整源码在乘除法篇
    测试文件:main.c 源码在本篇

    实现:
    1.将每个源码文件中的main函数去掉,将big.h注释取消。
    2.编写big.h代码如下。

      1 char * bigadd(char *adda,int lena,char *addb,int lenb);
      2 char * bigsub(char *suba,int lena,char *subb,int lenb);
      3 char * bigmul(char *m,int lena,char *f,int lenb);
      4 char * bigdiv(char *diva,int lena,char *divb,int lenb);

    3.编写一个测式的文件,代码如下。

      1 #include"big.h"
      2 #include<string.h>
      3 #include<stdlib.h>
      4 #include<stdio.h>
      5    int lena,lenb;
      6    char *result;
      7    char sa[BUFSIZ],sb[BUFSIZ];
      8 void getdata(){
      9    scanf("%s",sa);
     10    scanf("%s",sb);
     11    lena=strlen(sa);
     12    lenb=strlen(sb);
     13 
     14 }
     15 void myadd(void){
     16    getdata();
     17    result=bigadd(sa,lena,sb,lenb);
     18    puts(result);
     19 }
     20 void mysub(void){
     21    getdata();
     22    result=bigsub(sa,lena,sb,lenb);
     23    puts(result);
     24 }
     25 void mymul(void){
     26    getdata();
     27    result=bigmul(sa,lena,sb,lenb);
     28    puts(result);
     29 }
     30 void mydiv(void){
     31    getdata();
     32    result=bigdiv(sa,lena,sb,lenb);
     33    puts(result);
     34 }
     35 
     36 int main(){
     37    myadd();
     38    mysub();
     39    mymul();
     40    mydiv();
     41    return 0;
     42 }

    编译和测试:

    gcc big_add.c big_sub.c big_mul.c big_div.h
    
    ./a.out

    C语言大数运算,参考了很多人的博客和代码,学到了很多,在这里表示感谢。这次对大数运算的小小总结也是希望可以帮到有需求的人,哪怕一点点。

    展开全文
  • 关于c语言中的大数运算思想是怎么回事!关于c语言中的大数运算思想是怎么回事!关于c语言中的大数运算思想是怎么回事!关于c语言中的大数运算思想是怎么回事!关于c语言中的大数运算思想是怎么回事!关于c语言中的...
  • RSA与大数运算C语言

    千次阅读 2011-10-18 09:05:43
    ========================================================================== 前言:此文来自于www.pediy.com一位Cracker---afanty之手。他建立了一个VC++(MFC)版的大数运算
     
    

    ==========================================================================
    前言:此文来自于www.pediy.com一位Cracker---afanty之手。他建立了一个VC++(MFC)版的大数运算库。用Delphi的朋友们请到http://ace.ulyssis.student.kuleuven.ac.be/~triade/去下载Pascal的GInt大数运算库。当然,所有基于大素数分解难题的公开密匙算法都可以使用这两个库。不过请你小心里面可能存在的Bug...


    --- Crossbow
    ==========================================================================


    基于以下原因,俺估计RSA算法会被越来越多的共享软件采用:


    1、原理简洁易懂
    2、加密强度高
    3、专利限制已过期
    4、看雪老大三番五次呼吁共享软件采用成熟的非对称加密技术


    所以,大家应该对RSA算法进行深入了解。


    俺写了一个简单易懂的大数运算库,并使用该库作了一个RSA Demo,大家可以使用这一
    Demo生成真正随机的、各种长度的RSA 密钥对。其中生成1024位的RSA 密钥耗时不超过
    五分钟,而对1024位以内的密文进行解密则不超过三秒钟,应该是可以接受的。


    有一点需要说明的是,假如类似于这个Demo的RSA工具被共享软件作者广泛用于注册码
    的生成与验证,俺认为Cracker们的日子就会过得很无趣了,唉!


    RSA 依赖大数运算,目前主流RSA 算法都建立在512 位到1024位的大数运算之上,所以
    我们在现阶段首先需要掌握1024位的大数运算原理。


    大多数的编译器只能支持到64位的整数运算,即我们在运算中所使用的整数必须小于等
    于64位,即:0xffffffffffffffff,也就是18446744073709551615,这远远达不到RSA
    的需要,于是需要专门建立大数运算库来解决这一问题。


    最简单的办法是将大数当作字符串进行处理,也就是将大数用10进制字符数组进行表示,
    然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低,
    因为1024位的大数其10进制数字个数就有数百个,对于任何一种运算,都需要在两个有
    数百个元素的数组空间上做多重循环,还需要许多额外的空间存放计算的进位退位标志
    及中间结果。当然其优点是算法符合人们的日常习惯,易于理解。


    另一种思路是将大数当作一个二进制流进行处理,使用各种移位和逻辑操作来进行加减
    乘除运算,但是这样做代码设计非常复杂,可读性很低,难以理解也难以调试。
    于是俺琢磨了一种介于两者之间的思路:


    将大数看作一个n进制数组,对于目前的32位系统而言n可以取值为2的32次方,即0x100
    00000,假如将一个1024位的大数转化成0x10000000 进制,它就变成了32位,而每一位
    的取值范围就不是0-1或0-9,而是0-0xffffffff。我们正好可以用一个无符号长整数来
    表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x1
    00000000进制的数组排列与2 进制流对于计算机来说,实际上是一回事,但是我们完全
    可以针对unsigned long 数组进行“竖式计算”,而循环规模被降低到了32次之内,并
    且算法很容易理解。


    例如大数18446744073709551615,等于“ffffffff ffffffff”,它就相当于10
    进制的“99”:有两位,每位都是ffffffff。而大数18446744073709551616,等于“00000001
    00000000 00000000”,它就相当于10进制的“100”:有三位,第一位是1 ,其它两位
    是0。如果我们要计算18446744073709551616-18446744073709551615,就类似于100-99:


    00000001 00000000 00000000
    - ffffffff ffffffff
    -----------------------------
    = 0 0 1
    当然,因为在VC里面存在一个__int64类型可以用来计算进位与借位值,所以将大数当作
    0x100000000进制进行运算是可能的,而在其他编译系统中如果不存在64位整形,则可以
    采用0x40000000进制,由于在0x40000000进制中,对任何两个“数字”进行四则运算,
    结果都在0x3fffffff*03fffffff之间,小于0xffffffff,都可以用一个32位无符号整数
    来表示。


    /****************************************************************/
    file://大数运算库头文件:BigInt.h
    file://作者:afanty@vip.sina.com
    file://版本:1.0 (2003.4.26)
    file://说明:适用于MFC
    /****************************************************************/


    #define BI_MAXLEN 40
    #define DEC 10
    #define HEX 16


    class CBigInt
    {
    public:
    int m_nSign; file://记录大数的符号,支持负值运算
    int m_nLength; file://记录0x10000000进制的位数,0-40之间,相当于2进制的0-1280位
    unsigned long m_ulvalue[BI_MAXLEN]; file://记录每一位的“数字”


    CBigInt();
    ~CBigInt();



    file://将大数赋值为另一个大数
    CBigInt& Mov(CBigInt& A);


    file://将大数赋值为编译器能够理解的任何整形常数或变量
    CBigInt& Mov(unsigned __int64 A);


    file://比较两个大数大小
    int Cmp(CBigInt& A);


    file://计算两个大数的和
    CBigInt Add(CBigInt& A);


    file://重载函数以支持大数与普通整数相加
    CBigInt Add(long A);


    file://计算两个大数的差
    CBigInt Sub(CBigInt& A);


    file://重载函数以支持大数与普通整数相减
    CBigInt Sub(long A);


    file://计算两个大数的积
    CBigInt Mul(CBigInt& A);


    file://重载函数以支持大数与普通整数相乘
    CBigInt Mul(long A);


    file://计算两个大数的商
    CBigInt Div(CBigInt& A);


    file://重载函数以支持大数与普通整数相除
    CBigInt Div(long A);


    file://计算两个大数相除的余数
    CBigInt Mod(CBigInt& A);


    file://重载函数以支持大数与普通整数相除求模
    long Mod(long A);


    file://将输入的10进制或16进制字符串转换成大数
    int InPutFromStr(CString& str, const unsigned int system);


    file://将大数按10进制或16进制格式输出到字符串
    int OutPutToStr(CString& str, const unsigned int system);


    file://欧几里德算法求:Y=X.Euc(A),使满足:YX mod A = 1
    CBigInt Euc(CBigInt& A);


    file://蒙哥马利算法求:Y=X.Mon(A,B),使满足:X^A mod B = Y
    CBigInt Mon(CBigInt& A, CBigInt& B);
    };



    注意以上函数的声明格式,完全遵循普通整数运算的习惯,例如大数
    Y=X+Z 相当于 Y.Mov(X.(Add(Z)),这样似乎没有Mov(Y,Add(X,Z))
    看起来舒服,但是一旦我们重载运算符“=”为“Mov”,“+”为“Add”,
    则Y.Mov(X.(Add(Z))的形式就等价于 Y=X+Z。


    俺不知道其他编程语言里是否支持运算浮重载,至少这样定义函数格式
    在C++里可以带来很大的方便。



    下面让我们来实现大数类的主要成员函数:
    /****************************************************************/
    file://大数运算库源文件:BigInt.cpp
    file://作者:afanty@vip.sina.com
    file://版本:1.0 (2003.4.26)
    file://说明:适用于MFC
    /****************************************************************/


    #include "stdafx.h"
    #include "BigInt.h"


    file://初始化大数为0
    CBigInt::CBigInt()
    {
    m_nSign=1;
    m_nLength=1;
    for(int i=0;i<BI_MAXLEN;i++)m_ulvalue=0;
    }


    file://采用缺省的解构函数
    CBigInt::~CBigInt()
    {
    }


    file://大数比较,如果大数A位数比大数B多,当然A>B
    file://如果位数相同,则从高位开始比较,直到分出大小
    int CBigInt::Cmp(CBigInt& A)
    {
    if(m_nLength>A.m_nLength)return 1;
    if(m_nLength<A.m_nLength)return -1;
    for(int i=m_nLength-1;i>=0;i--)
    {
    if(m_ulvalue>A.m_ulvalue)return 1;
    if(m_ulvalue<A.m_ulvalue)return -1;
    }
    return 0;
    }


    file://照搬参数的各属性
    CBigInt& CBigInt::Mov(CBigInt& A)
    {
    m_nLength=A.m_nLength;
    for(int i=0;i<BI_MAXLEN;i++)m_ulvalue=A.m_ulvalue;
    return *this;
    }


    file://大数相加
    file://调用形式:N.Add(A),返回值:N+A
    file://若两大数符号相同,其值相加,否则改变参数符号再调用大数相减函数
    /******************************************************************/
    例如:
    A B C
    + D E
    --------------
    = S F G H


    其中,若C+E<=0xffffffff,则H=C+E,carry(进位标志)=0
    若C+E>0xffffffff,则H=C+E-0x100000000,carry=1


    若B+D+carry<=0xfffffff,则G=B+D,carry=0
    若B+D+carry>0xfffffff,则G=B+D+carry-0x10000000,carry=1


    若carry=0,则F=A,S=0
    若carry=1,A<0xfffffff,则F=A+1,S=0
    若carry=1,A=0xfffffff,则F=0,S=1
    /*****************************************************************/
    CBigInt CBigInt::Add(CBigInt& A)
    {
    CBigInt X;
    if(X.m_nSign==A.m_nSign)
    {
    X.Mov(*this);
    int carry=0;
    unsigned __int64 sum=0;
    if(X.m_nLength<A.m_nLength)X.m_nLength=A.m_nLength;
    for(int i=0;i<X.m_nLength;i++)
    {
    sum=A.m_ulvalue;
    sum=sum+X.m_ulvalue+carry;
    X.m_ulvalue=(unsigned long)sum;
    if(sum>0xffffffff)carry=1;
    else carry=0;
    }
    if(X.m_nLength<BI_MAXLEN)
    {
    X.m_ulvalue[X.m_nLength]=carry;
    X.m_nLength+=carry;
    }
    return X;
    }
    else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Sub(X);}
    }


    file://大数相减
    file://调用形式:N.Sub(A),返回值:N-A
    file://若两大数符号相同,其值相减,否则改变参数符号再调用大数相加函数
    /******************************************************************/
    例如:
    A B C
    - D E
    --------------
    = F G H


    其中,若C>=E,则H=C-E,carry(借位标志)=0
    若C<E,则H=C-E+0x100000000,carry=1


    若B-carry>=D,则G=B-carry-D,carry=0
    若B-carry<D,则G=B-carry-D+0x10000000,carry=1


    若carry=0,则F=A
    若carry=1,A>1,则F=A-1
    若carry=1,A=1,则F=0
    /*****************************************************************/
    CBigInt CBigInt::Sub(CBigInt& A)
    {
    CBigInt X;
    if(m_nSign==A.m_nSign)
    {
    X.Mov(*this);
    int cmp=X.Cmp(A);
    if(cmp==0){X.Mov(0);return X;}
    int len,carry=0;
    unsigned __int64 num;
    unsigned long *s,*d;
    if(cmp>0)
    {
    s=X.m_ulvalue;
    d=A.m_ulvalue;
    len=X.m_nLength;
    }
    if(cmp<0)
    {
    s=A.m_ulvalue;
    d=X.m_ulvalue;
    len=A.m_nLength;
    X.m_nSign=1-X.m_nSign;
    }
    for(int i=0;i<len;i++)
    {
    if((s-carry)>=d)
    {
    X.m_ulvalue=s-carry-d;
    carry=0;
    }
    else
    {
    num=0x100000000+s;
    X.m_ulvalue=(unsigned long)(num-carry-d);
    carry=1;
    }
    }
    while(X.m_ulvalue[len-1]==0)len--;
    X.m_nLength=len;
    return X;
    }
    else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Add(X);}
    }


    file://大数相乘
    file://调用形式:N.Mul(A),返回值:N*A
    /******************************************************************/
    例如:
    A B C
    * D E
    ----------------
    = S F G H
    + T I J K
    ----------------
    = U V L M N


    其中,SFGH=ABC*E,TIJK=ABC*D


    而对于:
    A B C
    * E
    -------------
    = S F G H


    其中,若C*E<=0xffffffff,则H=C*E,carry(进位标志)=0
    若C*E>0xffffffff,则H=(C*E)&0xffffffff
    carry=(C*E)/0xffffffff
    若B*E+carry<=0xffffffff,则G=B*E+carry,carry=0
    若B*E+carry>0xffffffff,则G=(B*E+carry)&0xffffffff
    carry=(B*E+carry)/0xffffffff
    若A*E+carry<=0xffffffff,则F=A*E+carry,carry=0
    若A*E+carry>0xffffffff,则F=(A*E+carry)&0xffffffff
    carry=(A*E+carry)/0xffffffff
    S=carry
    /*****************************************************************/
    CBigInt CBigInt::Mul(CBigInt& A)
    {
    CBigInt X,Y;
    unsigned __int64 mul;
    unsigned long carry;
    for(int i=0;i<A.m_nLength;i++)
    {
    Y.m_nLength=m_nLength;
    carry=0;
    for(int j=0;j<m_nLength;j++)
    {
    mul=m_ulvalue[j];
    mul=mul*A.m_ulvalue+carry;
    Y.m_ulvalue[j]=(unsigned long)mul;
    carry=(unsigned long)(mul>>32);
    }
    if(carry&&(Y.m_nLength<BI_MAXLEN))
    {
    Y.m_nLength++;
    Y.m_ulvalue[Y.m_nLength-1]=carry;
    }
    if(Y.m_nLength<BI_MAXLEN-i)
    {
    Y.m_nLength+=i;
    for(int k=Y.m_nLength-1;k>=i;k--)Y.m_ulvalue[k]=Y.m_ulvalue[k-i];
    for(k=0;k<i;k++)Y.m_ulvalue[k]=0;
    }
    X.Mov(X.Add(Y));
    }
    if(m_nSign+A.m_nSign==1)X.m_nSign=0;
    else X.m_nSign=1;
    return X;
    }


    file://大数相除
    file://调用形式:N.Div(A),返回值:N/A
    file://除法的关键在于“试商”,然后就变成了乘法和减法
    file://这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商
    CBigInt CBigInt:iv(CBigInt& A)
    {
    CBigInt X,Y,Z;
    int len;
    unsigned __int64 num,div;
    unsigned long carry=0;
    Y.Mov(*this);
    while(Y.Cmp(A)>0)
    {
    if(Y.m_ulvalue[Y.m_nLength-1]>A.m_ulvalue[A.m_nLength-1])
    {
    len=Y.m_nLength-A.m_nLength;
    div=Y.m_ulvalue[Y.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1);
    }
    else if(Y.m_nLength>A.m_nLength)
    {
    len=Y.m_nLength-A.m_nLength-1;
    num=Y.m_ulvalue[Y.m_nLength-1];
    num=(num<<32)+Y.m_ulvalue[Y.m_nLength-2];
    if(A.m_ulvalue[A.m_nLength-1]==0xffffffff)div=(num>>32);
    else div=num/(A.m_ulvalue[A.m_nLength-1]+1);
    }
    else
    {
    X.Mov(X.Add(1));
    break;
    }
    Z.Mov(div);
    Z.m_nLength+=len;
    for(int i=Z.m_nLength-1;i>=len;i--)Z.m_ulvalue=Z.m_ulvalue[i-len];
    for(i=0;i<len;i++)Z.m_ulvalue=0;
    X.Mov(X.Add(Z));
    Z.Mov(Z.Mul(A));
    Y.Mov(Y.Sub(Z));
    }
    if(Y.Cmp(A)==0)X.Mov(X.Add(1));
    if(m_nSign+A.m_nSign==1)X.m_nSign=0;
    else X.m_nSign=1;
    return X;
    }


    file://大数求模
    file://调用形式:N.Mod(A),返回值:N%A
    file://求模与求商原理相同
    CBigInt CBigInt::Mod(CBigInt& A)
    {
    CBigInt X,Y;
    int len;
    unsigned __int64 num,div;
    unsigned long carry=0;
    X.Mov(*this);
    while(X.Cmp(A)>0)
    {
    if(X.m_ulvalue[X.m_nLength-1]>A.m_ulvalue[A.m_nLength-1])
    {
    len=X.m_nLength-A.m_nLength;
    div=X.m_ulvalue[X.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1);
    }
    else if(X.m_nLength>A.m_nLength)
    {
    len=X.m_nLength-A.m_nLength-1;
    num=X.m_ulvalue[X.m_nLength-1];
    num=(num<<32)+X.m_ulvalue[X.m_nLength-2];
    if(A.m_ulvalue[A.m_nLength-1]==0xffffffff)div=(num>>32);
    else div=num/(A.m_ulvalue[A.m_nLength-1]+1);
    }
    else
    {
    X.Mov(X.Sub(A));
    break;
    }
    Y.Mov(div);
    Y.Mov(Y.Mul(A));
    Y.m_nLength+=len;
    for(int i=Y.m_nLength-1;i>=len;i--)Y.m_ulvalue=Y.m_ulvalue[i-len];
    for(i=0;i<len;i++)Y.m_ulvalue=0;
    X.Mov(X.Sub(Y));
    }
    if(X.Cmp(A)==0)X.Mov(0);
    return X;
    }



    file://暂时只给出了十进制字符串的转化
    int CBigInt::InPutFromStr(CString& str, const unsigned int system=DEC)
    {
    int len=str.GetLength();
    Mov(0);
    for(int i=0;i<len;i++)
    {
    Mov(Mul(system));
    int k=str-48;
    Mov(Add(k));
    }
    return 0;
    }


    file://暂时只给出了十进制字符串的转化
    int CBigInt::OutPutToStr(CString& str, const unsigned int system=DEC)
    {
    str="";
    char ch;
    CBigInt X;
    X.Mov(*this);
    while(X.m_ulvalue[X.m_nLength-1]>0)
    {
    ch=X.Mod(system)+48;
    str.Insert(0,ch);
    X.Mov(X.Div(system));
    }
    return 0;
    }


    file://欧几里德算法求:Y=X.Euc(A),使满足:YX mod A=1
    file://相当于对不定方程ax-by=1求最小整数解
    file://实际上就是初中学过的辗转相除法
    /********************************************************************/
    例如:11x-49y=1,求x


    11 x - 49 y = 1 a)
    49%11=5 -> 11 x - 5 y = 1 b)
    11%5 =1 -> x - 5 y = 1 c)


    令y=1 代入c)式 得x=6
    令x=6 代入b)式 得y=13
    令y=13 代入a)式 得x=58
    /********************************************************************/
    CBigInt CBigInt::Euc(CBigInt& A)
    {
    CBigInt X,Y;
    X.Mov(*this);
    Y.Mov(A);
    if((X.m_nLength==1)&&(X.m_ulvalue[0]==1))return X;
    if((Y.m_nLength==1)&&(Y.m_ulvalue[0]==1)){X.Mov(X.Sub(1));return X;}
    if(X.Cmp(Y)==1)X.Mov(X.Mod(Y));
    else Y.Mov(Y.Mod(X));
    X.Mov(X.Euc(Y));
    Y.Mov(*this);
    if(Y.Cmp(A)==1)
    {
    X.Mov(X.Mul(Y));
    X.Mov(X.Sub(1));
    X.Mov(X.Div(A));
    }
    else
    {
    X.Mov(X.Mul(A));
    X.Mov(X.Add(1));
    X.Mov(X.Div(Y));
    }
    return X;
    }


    file://蒙哥马利算法求:Y=X.Mon(A,B),使满足:X^A mod B=Y
    file://俺估计就是高中学过的反复平方法
    CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
    {
    CBigInt X,Y,Z;
    X.Mov(1);
    Y.Mov(*this);
    Z.Mov(A);
    while((Z.m_nLength!=1)||Z.m_ulvalue[0])
    {
    if(Z.m_ulvalue[0]&1)
    {
    Z.Mov(Z.Sub(1));
    X.Mov(X.Mul(Y));
    X.Mov(X.Mod(B));
    }
    else
    {
    Z.Mov(Z.Div(2));
    Y.Mov(Y.Mul(Y));
    Y.Mov(Y.Mod(B));
    }
    }
    return X;
    }



    最后需要说明的是因为在VC里面存在一个__int64类型可以
    用来计算进位与借位值,所以将大数当作0x100000000进制
    进行运算是可能的,而在其他编译系统中如果不存在64位
    整形,则可以采用0x40000000进制,由于在0x40000000
    进制中,对任何两个“数字”进行四则运算,结果都在
    0x3fffffff*03fffffff之间,小于0xffffffff,都可以用
    一个32位无符号整数来表示。事实上《楚汉棋缘》采用的
    freelip大数库正是运用了0x40000000进制来表示大数的,
    所以其反汇编后大数的值在内存中表现出来有些“奇怪”。


    展开全文
  • C语言大数运算-加法篇

    万次阅读 多人点赞 2017-04-03 14:31:17
    虽然大多主流的编程语言如java,c++,都有大数运算库,可是c语言标准库并没有提供的大数运算,网上的c语言大数运算大多散而不周或过于复杂,所以本人决定写博客做一些简单的介绍,由于本人水平有限,如有错误或者bug...

    前言:
    本篇博客将分为4到5篇来和大家一块讨论大数的加减乘除,然后再将运算做成一个大数运算库。其中除法较为棘手,但如果作完前三个运算后就没有什么难度了。虽然大多主流的编程语言如java,c++,都有大数运算库,可是c语言标准库并没有提供的大数运算,网上的c语言大数运算大多散而不周或过于复杂,所以本人决定写博客做一些简单的介绍,由于本人水平有限,如有错误或者bug请大家批评指正我会第一时间更正。

    开发环境:
    本人没有windows电脑,所有的编写测试都是在centos 3.10.-514.6.1.el7.x86_64 和 gcc 4.8.5 下做的,windows平台下没有任何测试,所以如果windows下出现错误我也无能为力。

    总体思路:
    加法和减法类似,乘法和除法类似,我们会先从大数加减法开始然后是乘除法。使用数组作为数据结构保存用户的输入和结果,主要就是将大数的整体运算转换为每一个数组元素的运算,难点也就在转换上。

    大数减法:
    假设 :
    用户输入的数据保存在数组adda与数组addb中,adda={1,2,3,4,5,6,7,8,9};addb={1,2,3,4}。如果模仿手工计算,从低位到高位以次先加,满十则进一,那么将会有两个问题要解决。

    问题:
    1.用数组保存结果那么结果的长度是多少位?
    2.如何写一个满十进一的算法。
    其实这两个问题也很简单:
    1.二个数相加结果最大只会比较大的数多一位,所以:用lensum代表结果的长度lena代表adda的长度,lenb代表addb的长度。
    lensum=lena>lenb?lena:lenb;
    lensum++;
    就可以确定结果数组的长度。
    2.如果每加一位就判断是否进一的话问题就会复杂一点,所以我们可以先保存每一位相加的结果然后在对结果进行处理如图。这里写图片描述
    一次性对result进行处理就很好实现:

    for(i=lensum-1;i>0;i--){    
        if(result[i]>9){
            result[i]=result[i]%10;
            result[i-1] += 1;
        }
    }

    注意实际的程序,会把9+4的结果存在result[0]中,8+3的结果存在result[1]中,上面的图是为了简化方便理解,其实也可以像图中那样存把循环控制的i由递增改成递减就可以了。

    实现:
    我会将加法写成方法,然后在main函数中调用,这样方便以后做成一个自己的库,代码很完整注释也很多。很好懂的。

    1 //#include"big.h"
      2 //将整个加法写成一个方法,然后在main函数中调用。
      3 #include<stdlib.h>
      4 #include<stdio.h>
      5 #include<string.h>
      6 char * bigadd(char *adda,int lena,char *addb,int lenb){     //加法运算的方法。
      7   int num='0',i,k,j,tmp;
      8   for(i=0;i<lena;i++){                                      //将字符编码的数字转换为对应的数,
      9       adda[i]=adda[i]-num;                                  //例如6实际在字符串中存储的是54,
     10   }                                                         //减去0对应的48得到真实的6存储在字符数组中。
     11   for(i=0;i<lenb;i++){
     12       addb[i]=addb[i]-num;
     13   }
     14     int lensum;                                             //求出结果数组的长度。
     15     lensum = lena>lenb?lena:lenb;
     16     lensum++;
     17     char *result,final[BUFSIZ];                             //result用于返回结果集,final数组用于整理结果集。
     18     result=(char*)calloc(lensum,1);
     19     for(i=0,j=0;i<lena&&j<lenb;i++,j++){                    //循环的给每一位作加法
     20       result[i]=adda[lena-i-1]+addb[lenb-i-1];
     21     }
     22     if(lena>lenb){                                          //使用判断将较大数的高位也写入结果数组
     23       for(i=lenb;i<lena;i++){
     24          result[i]=adda[lena-i-1];
     25       }
     26     }
     27     if(lenb>lena){
     28       for(i=lena;i<lenb;i++){
     29          result[i]=addb[lenb-i-1];
     30       }
     31     }
     32     for(k=0;k<lensum-1;k++){                                //整理结果数组的每一位,满10进一。
     33       if(result[k]>9){
     34          tmp=result[k]/10;
     35          result[k]=result[k]%10;
     36          result[k+1] += tmp;
     37       }
     38     }
     39    j=0;
     40    if(result[lensum-1]!=0){                                 //去掉前前导0将结果处理后写到final数组中。
     41       final[j]=result[lensum-1]+'0';
           j++;
     43    }
     44    for(i=lensum-2;i>=0;i--){
     45       final[j++]=result[i]+'0';
     46    }
     47    result=final;                                            //再把result指针指向final数组中,并返回result指针。    
     48    return result;
     49 }
     50 int main(){                                                 //利用main测试方法,用puts打印结果。               
     51    int lena,lenb;
     52    char *result,sa[BUFSIZ],sb[BUFSIZ];
     53    scanf("%s",sa);
     54    scanf("%s",sb);
     55    lena=strlen(sa);
     56    lenb=strlen(sb);
     57    result=bigadd(sa,lena,sb,lenb);
     58    puts(result);
     59 
     60 }
    
    

    下篇介绍大数减法。

    展开全文
  • C语言实现大数运算

    万次阅读 多人点赞 2018-01-16 14:43:55
    由于整型数的位数有限,因此整型数不能满足大整数(超长整数)的运算要求 。大整数计算是利用字符串来...大数的结构 typedef struct bigint { char *num; //指向长整数数组(序号0中保存着最高位) char sign;
  • C语言大数运算

    2019-10-05 17:31:34
    运算存入 36 { 37 for (j= 0 ;j(s2);j++ ) 38 c[i+j]+=a[i]*b[j]; // 重点 39 } 40 for (i= 0 ;i;i++ ) 41 { 42 c[i+ 1 ]=c[i+ 1 ]+c[i]/ 10 ; 43 c[i]=c[i]% 10 ; 44 } 45 for ...
  • 所开发的一套关于大数运算函数库,用来设计与大数运算相关的密码学之应用,包含了RSA 公开密码学、Diffie-Hellman密钥交换(Key Exchange)、AES、DSA数字签名,还包含了较新的椭圆曲线密码学(Elliptic ...
  • 大数 加法 c语言

    万次阅读 多人点赞 2016-07-20 19:02:23
    最近遇到一个关于大数的问题顿时感觉好方,决定系统学...注意:关于大数问题,由于数组不好界定输入数的大小(数组的长度),因此主要思想就是先用字符串输入保存在字符串数组中,再逆序存入整形数组进行最后逐位运算
  • 还是大数运算,这次是乘法的。具体都写在代码里面了,就不多说。 /****************************************************************************************/ /* 大数运算篇——乘法 */ /*...
  • C语言 大数运算(无限大小)头文件 支持 + , - , * , / , % ,> , ,>=,,==.流输入>>,流输出<<.
  • 大数运算模板(C语言

    千次阅读 2016-07-20 22:08:58
    代码说明: //大数相加#include #include #define MAXN 100 int an1[MAXN+10]; int an2[MAXN+10]; char str1[MAXN+10]; char str2[MAXN+10]; int main() { memset(an1,0,sizeof(an1)); int i,j;
  • C语言大数运算——加法

    千次阅读 2019-01-30 19:28:15
    这个老到掉牙的大数运算问题,本人一个初学者,在这里发了给自己看吧—,如果可以帮助别人,我也是很开心的哈,不过我这表诉能力,emmm,废话不多说,上干货 123456 + 126 主要问题: 1.大数用什么存放? 2.两个大数...
  • 关于大数C语言

    2020-12-03 01:19:38
    因其位数过大,在c语言中不能对其进行直接运算;若想实现运算,则需要一些奇淫小技巧。 大数相加 两数相加的手算操作: 将两数右对齐,由右至左对位相加,结果上再加上一位的进位(如果有的话);保留该结果个位为这...
  • 接着加法之后写了个减法,大数减法主要有几个问题 1.减完了后是负数怎么办? 2.减完了后有几位数? 3.减法的操作是如何进行的? /******************************.../* 大数运算篇——减法 */ /* 1...
  • 大数乘方运算-C语言

    千次阅读 2018-05-27 15:23:50
    c语言中计算乘方一般使用pow函数就行了,但是有时候我们计算的乘方的结果超出了double或者int能表示的范围,这个时候就不能使用简单的pow函数进行运算,那么怎么办呢???下面就是我的一种思路,大家参考下 先...
  • 大数乘法运算(C语言)

    2020-06-02 15:21:27
    大数运算 利用乘法法则,相乘,然后进位,取余 详细过程-如图 源代码 #include<stdio.h> #include<string.h> #define N 100 int main() { int i,j,L[N]; char m[N],n[N]; scanf("%s %s",m,n); ...
  • C语言大数运算加法

    2018-05-05 22:07:13
    #include&lt;stdio.h&gt; /*用于大数加法运算*/ #include&lt;string.h&gt;int main(void){ char a[10000],b[10000],*pa,*pb; ...
  • 大数相乘C语言(转)

    2018-11-09 19:45:34
    进一步学习来到 了大数乘法,关于大数乘法的思路前面也简单提过, 其核心就是:两个大数,从末尾开始逐位相乘。相乘结果保存在另外一个数组里面(也从数组末尾开始依次往前...由运算例子可知;相乘后的位数k不会超...
  • C语言大数运算-减法篇

    万次阅读 2017-04-03 17:04:03
    与加法类似,还是将用户的输入和结果放入变长的数组中然后模仿手工运算从低位到高位依次相减,会有三个需要解决的问题,其中前二个和大数加法的问题很相似,所以就不再详细说明。问题: 1.结果最多有多少位? 2....
  • 1、引子 在C语言中,因为预定义的自然数类型的大小是有上下限度的,这就决定了在... 为了在C中进行大数运算,不能简单的用C中预定义的数据类型和运算方法进行,因此必须寻求一种新的方法。本文讨论怎样来设计一种...
  • C语言加法大数运算

    2012-01-13 16:48:26
    大家贴上一个大数加法运算的程序,请详细的写上注释,要中文注释哦,我想好好研究一下,谢谢了

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 314
精华内容 125
关键字:

大数运算c语言

c语言 订阅