博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
大数运算
阅读量:7044 次
发布时间:2019-06-28

本文共 2501 字,大约阅读时间需要 8 分钟。

大数运算

       大数运算的实现方法主要有下面几种:

1)        用字符串表示大数。将大数用十进制字符数组表示,然后依照“竖式计算”的思想进行计算。这样的方法比較easy理解,可是计算效率非常低。

2)        将大数看成二进制流进行处理。使用各种位运算和逻辑操作来实现打算的运算。该方法设计复杂,可读性较差,并且难以调试。

3)        将大数表示成一个n进制数组。n的取值越大,数组的大小越小,这样能够缩短运算的时间及空间复杂度,提高算法的效率。在32位系统中,n能够取2^32,这时每一位的取值范围是0~0xffffffff

 

以下就针对第3)种方法进行描写叙述。在RSA中涉及的大数通常都大于0,所以为了简化问题,如果运算过程中全部大数均都大于0的。

n=2^32时,大数的每一位恰好是unsigned long 的范围,考虑到加法和乘法中进位时的溢出现象不好推断,能够选取long long型(gcc, 若是VC++则为__int64)。并且对于每一个大数,包括一个变量标志其符号,一个变量来表示其长度,一个数组来存储每一位的值。于是,能够用以下结构体表示一个大数:

typedef struct LargeNumber

{

    bool tag;                          // 标志大数的符号 true  正数  false 负数

    int length;                         // 记录大数的长度

    long long bigInt[SIZE];              // 记录大数各位的值

 

    LargeNumber( const bool& t=true,const int& len=0)

    {

        tag = t;

        length = len;

        for( int i=0; i<SIZE; ++i )

        {

            bigInt[i]= 0;

        }

    }

};

 

(一)    大数加法

如果在加法中两个操作数都是大于0的。依照“竖式计算”的思想,首先将两操作数低位对齐,然后从最低位開始按“位”相加,当“位”相加的结果大于2^32-1时做进位处理(carry=1),否则不进位(carry=0)。

符号演示:op1=ABCD op2=EFG

A  B  C  D

+  E  F  G

-------------------

H  I  J  K   L

 

初始化carry=0

当中,若D+G+carry>0xffffffff L=D+G+carry-0xffffffff-1, carry=1

                                          否则L=D+G+carry carry=0

依照上述方法计算K,J,I,H

 

比如:0x1  0x1  0x1  + 0xffffffff 0xffffffff; 初始carry=0

运算过程:

10x1+0xffffffff+0>0xffffffff, 所以计算结果的最低位result.bigInt[0]=0x0,carry=1;

20x1+0xffffffff+1>0xffffffff,所以result.bigInt[1]= 0x1+0xffffffff+1-0xffffffff-1=1,carry=1;

30x1+1<0xffffffff,所以result.bigInt[2]=2;result.length=2;

 

终于结果为2  1  0

 

(二)    大数减法

为了简化计算,如果被减数总是不小于减数,这样计算的终于结果总是大于等于0。基本思路和大数加法基本一致,减法中可能须要借位,定义并初始借位变量borrow=0。显然,borrow要么等于0,要么等于1

 

比如:0x1 0x1 0x1 – 0xffffffff  0xffffffff; 初始borrow=0;

计算过程:

       (1) 0x1<0xfffffff+borrow,这时须要借位

result.bigInt[0]= 0xffffffff-(0xffffffff+0-0x1)+1=2,borrow=1;

       (2)0x1<0xffffffff+borrow,于是

result.bigInt[1]= 0xffffffff-(0xffffffff+1-0x1)+1=1,borrow=1;

       (3)0x1=0+borrow,于是result.bigInt[2]=0, borrow=0;

 

终于结果为:1  2

(三)    大数乘法

如果乘法的两个操作数均为正数。依照“竖式计算”的思想,大数的乘法能够借助大数的加法,用乘数的每一位乘以被乘数,然后将每一次的计算结果相加。在每位相乘的过程中依旧存在进位现象,并且此时进位不仅仅是1,还存在更大的数。

 

过程演示:

A   B

*   C   D

---------------

           E   F   G

  +  H  I   J

----------------------------

 K  M  N   O  P

 

当中 B*D+carry>0xffffffff,

那么进位G=(B*D+carry)%0xffffffffcarry=(B*D+carry)/0xffffffff;

否则,G=B*D+carry,carry=0;

依照上述计算原则计算,F E J I H.并依照大数加法的计算方法计算P O N M K

 

比如: 0x1  0x1  0x1 * 0xffffffff  0xffffffff.

计算过程:

10x1 0x1 0x1 * 0xffffffff =0xffffffff 0xffffffff 0xffffffff

20x1 0x1 0x1 * 0xffffffff =0xffffffff 0xffffffff 0xffffffff, 因为这是乘数的第一位,所以结果“扩展一位”,变成0xffffffff 0xffffffff 0xffffffff 0x0

3)计算0xffffffff 0xffffffff 0xffffffff + 0xffffffff 0xffffffff 0xffffffff 0x0

4)结果为1 0 0xffffffff 0xfffffffe 0xffffffff

 

(四)    大数除法

除法建立在乘法的基础上,循环搜索num 使得num*op1==op2.效率较低。

代码下载链接:

里面还有字符串实现的代码。

转载地址:http://hpqal.baihongyu.com/

你可能感兴趣的文章
Entity Framework Core 2.0的槽点
查看>>
甲骨文解散Java Mission Control团队事件新进展
查看>>
书评:实战Apache JMeter
查看>>
2014年基于Raspberry Pi的5大项目
查看>>
[deviceone开发]-openPage的动画效果示例
查看>>
EAGLEPCB7.7 gerber文件导出
查看>>
苏宁11.11:苏宁易购移动端的架构优化实践
查看>>
GitHub推出Scientist,帮助开发者重构关键路径代码
查看>>
力荐!这些工具可以帮你写出干净的代码
查看>>
优化typecho性能,使typecho可以流畅支持200w posts
查看>>
UITableView基础[ 3 ] 使用UIRefreshControl实现下拉刷新功能
查看>>
el-admin v1.7 发布,后台管理系统
查看>>
JFinal 开发的内容管理系统 JFinalCMS 1.0 发布
查看>>
Gitea Extension for Visual Studio V1.0.62 发布
查看>>
PHP7 的抽象语法树(AST)带来的变化
查看>>
如何在Mac 终端升级ruby版本
查看>>
国际编程教育权威科学家菲利普.米勒教授来访 SegmentFault 总部
查看>>
API 标准化成为技术团队面临的最大挑战
查看>>
CSS 小三角
查看>>
Ruby on Rails 曝路径穿越与任意文件读取漏洞
查看>>