本发明公开了一种利用浮点数计算指令实现大整数乘法计算加速方法。本方法为：1)将长度为n比特的被乘数A分为N段，长度为m比特乘数B分为M段；每段的长度为w比特，M≥N；2)将被乘数A、乘数B的每段分别转化为一浮点数；3)采用熔加运算对转化后的被乘数A、乘数B进行乘法运算；并将运算结果转化为一定点数；4)将该定点数分为多段，每段长度为w比特；然后对每一段定点数R[u]：R[u]对2w进行求模运算，将求模结果保存到C[u]中；然后对R[u]右移w位，结果保存到Carry1中；然后将Carry1与R[u+1]作和，并保存到R[u+1]中。本发明减少了计算的复杂度，提升了计算速度。
1.一种利用浮点数计算指令实现大整数乘法计算加速方法，其步骤为：
1)从低位到高位将长度为n比特的被乘数A分为N段，长度为m比特乘数B分为M段，若最后一段长度不足w比特，将该最后一段高位补0；其中，每段的长度为w比特，M≥N；将分段后位宽w比特的每段定义为一个字；其中，A[0:N-1]表示被乘数A的第0～(N-1)的N个字，B[0:M-1]乘数B的第0～(M-1)的M个字，
3)采用熔加运算对步骤2)转化后的被乘数A、乘数B进行乘法运算；并将运算结果转化为一定点数；
4)将该定点数分为多段，每段长度为w比特；然后对每一段定点数R[u]分别进行下列操作：R[u]对2w进行求模运算，将求模结果保存到C[u]中；然后对R[u]右移w位，结果保存到Carry1中；然后将该R[u]右移后的结果Carry1与R[u+1]作和，并保存到R[u+1]中；其中，R[u]为第u段定点数，R[u+1]为第u+1段定点数；
其中，将被乘数A的每段分别转化为一浮点数的方法为：首先初始化(N+1)个初值为0的浮点数用来表示分段后的被乘数，即用一组浮点数A’[0:N]表示转化后的被乘数；设被乘数A第u段对应的字A[u]转化的浮点数结果为A’[u]，然后从A[0]开始到A[N-1]中的每一字A[u]分别进行以下操作：判断A[u]与2w-1的大小关系，如果A[u]小于2w-1，则将长度为w的数值A[u]转化为浮点数A’[u]；否则，将(A[u]-2w)的计算结果保存到A’[u]中，并且置A[u+1]的数值为(A[u+1]+1)；最后得到存储转化后的被乘数A的一组浮点数A’[0:N]；
将乘数B的每段分别转化为一浮点数的方法为：首先初始化(M+1)个初值为0的浮点数用来表示分段后的乘数，即用一组浮点数B’[0:M]表示转化后的乘数；设乘数B第u段对应的字B[u]转化的浮点数结果为B’[u]，然后从B[0]开始到B[M-1]中的每一字B[u]分别进行以w-1 w-1下操作：判断B[u]与2 的大小关系，如果B[u]小于2 ，则将长度为w的数值B[u]转化为浮点数B’[u]；否则，将(B[u]-2w)的计算结果保存到B’[u]中，并且置B[u+1]的数值为(B[u+1]+1)；最后得到存储转化后的乘数B的一组浮点数B’[0:M]。
2.如权利要求1所述的方法，其特征在于，长度w满足公式
3.如权利要求1所述的方法，其特征在于，采用熔加运算对步骤2)转化后的被乘数A、乘数B进行乘法运算的方法为：首先初始化(M+N+1)个的浮点数，记为R’[0:M+N]；设min(a,b)操作为取a与b中的较小值，max(a,b)操作为取a与b中的较大值；然后根据一定次序累加被乘数A的一个字和乘数B的一个字相乘的乘积到浮点数R’[k]中，完成按字扫描的大整数乘法运算操作，其中R’[k]计算方法为：
4.如权利要求3所述的方法，其特征在于，将运算结果转化一定点数的方法为：R’[0:M+N]中存储浮点数形式的计算结果，对R’[0:M+N]中从R’[0]到R’[M+N]的每一R’[u]，将R’[u]转换为对应定点数R[u]，并将转化后结果保存到一组定点数R[0:M+N]中。
5.如权利要求4所述的方法，其特征在于，按照符合C语言类型的强制类型转换，将R’[u]转换为对应定点数R[u]。
一种利用浮点数计算指令实现大整数乘法计算加速方法
技术领域
[0001] 本发明属于计算技术领域，涉及一种利用浮点数计算指令实现大整数乘法计算加速方法。
背景技术
[0002] 随着计算机技术的不断发展与信息安全要求的不断提高，密码学被大量应用到生活以及工作领域中。许多非对称密码算法都建立在大整数乘法的运算基础上，包括世界上流行的非对称密码算法RSA以及椭圆曲线算法ECC等，因此大整数算数运算速度直接影响到密码运算以及数字签名的效率。提高大整数乘法的运算速度具有重要研究价值与意义。
[0003] 由于当前计算机基本数据类型的限制，大整数表示方法一般不能直接通过基本类型数据表示，因此对于超大规模数据的乘法，计算机人员一般采用编程的方式进行处理。
[0004] 同时，计算机图形处理单元的迅速发展，使得原本只适用于图形计算进而应用到通用计算当中，比如NVIDIA公司的CUDA并行计算架构，该架构通过利用GPU的处理能力，可大幅提高计算性能。由于GPU在计算机中主要负责图像处理工作，更加擅长浮点数的运算，为了适应这一发展方向，本发明采用浮点数来表示大整数，利用浮点数指令进行编程，实现大整数运算。
[0005] 本发明使用的浮点数符合IEEE 754所规定的浮点数标准。IEEE标准从逻辑上用三元组{S,E,T}表示一个数，S表示符号位，E表示阶码，T表示长度为p比特的尾码，同时尾码中还有一位隐含位。根据IEEE754国际标准常用的浮点数有两种格式。分别为单精度浮点数与双精度浮点数。
发明内容
[0006] 本发明提供一种利用浮点数计算指令实现大整数乘法计算加速方法，该方法能够减少大整数乘法计算的复杂度，提升计算速度。
[0007] 一种利用浮点数计算指令实现大整数乘法计算加速方法，其步骤为：
[0008] 1)将长度为n比特的被乘数A分为N段，长度为m比特乘数B分为M段；其中，每段的长度为w比特，M≥N；
[0009] 2)将被乘数A、乘数B的每段分别转化为一浮点数；
[0010] 3)采用熔加运算对步骤2)转化后的被乘数A、乘数B进行乘法运算；并将运算结果转化为一定点数；
[0011] 4)将该定点数分为多段，每段长度为w比特；然后对每一段定点数R[u]分别进行下列操作：R[u]对2w进行求模运算，将求模结果保存到C[u]中；然后对R[u]右移w位，结果保存到Carry1中；然后将该R[u]右移后的结果Carry1与R[u+1]作和，并保存到R[u+1]中；其中，R[u]为第u段定点数，R[u+1]为第u+1段定点数。
[0012] 进一步的，长度w满足公式 p为浮点数的尾码长度。
[0013] 进一步的，将分段后位宽w比特的每段定义为一个字；其中，A[0:N-1]表示被乘数A的第0～(N-1)的N个字，B[0:M-1]乘数B的第0～(M-1)的M个字。
[0014] 进一步的，将被乘数A的每段分别转化为一浮点数的方法为：首先初始化(N+1)个初值为0的浮点数用来表示分段后的被乘数，即用一组浮点数A’[0:N]表示转化后的被乘数；设被乘数A第u段对应的字A[u]转化的浮点数结果为A’[u]，然后从A[0]开始到A[N-1]中的每一字A[u]分别进行以下操作：判断A[u]与2w-1的大小关系，如果A[u]小于2w-1，则将长度为w的数值A[u]转化为浮点数A’[u]；否则，将(A[u]-2w)的计算结果保存到A’[u]中，并且置A[u+1]的数值为(A[u+1]+1)；最后得到存储转化后的被乘数A的一组浮点数A’[0:N]。
[0015] 进一步的，将乘数B的每段分别转化为一浮点数的方法为：首先初始化(M+1)个初值为0的浮点数用来表示分段后的乘数，即用一组浮点数B’[0:M]表示转化后的乘数；设乘数B第u段对应的字B[u]转化的浮点数结果为B’[u]，然后从B[0]开始到B[M-1]中的每一字Bw-1 w-1[u]分别进行以下操作：判断B[u]与2 的大小关系，如果B[u]小于2 ，则将长度为w的数值B[u]转化为浮点数B’[u]；否则，将(B[u]-2w)的计算结果保存到B’[u]中，并且置B[u+1]的数值为(B[u+1]+1)；最后得到存储转化后的乘数B的一组浮点数B’[0:M]。
[0016] 进一步的，采用熔加运算对步骤2)转化后的被乘数A、乘数B进行乘法运算的方法为：首先初始化(M+N+1)个的浮点数，记为R’[0:M+N]；设min(a,b)操作为取a与b中的较小值，max(a,b)操作为取a与b中的较大值；然后根据一定次序累加被乘数A的一个字和乘数B的一个字相乘的乘积到浮点数R’[k]中，完成按字扫描的大整数乘法运算操作，其中R’[k]计算方法为：
[0017] 将运算结果转化一定点数的方法为：R’[0:M+N]中存储浮点数形式的计算结果，对R’[0:M+N]中从R’[0]到R’[M+N]的每一R’[u]，将R’[u]转换为对应定点数R[u]，并将转化后结果保存到一组定点数R[0:M+N]中。
[0018] 进一步的，按照符合C语言类型的强制类型转换，将R’[u]转换为对应定点数R[u]。
[0019] 进一步的，步骤1)中，从低位到高位将长度为n比特被乘数A分为N段，长度为m比特乘数B分为M段；若最后一段长度不足w比特，将该最后一段高位补0。
[0020] 进一步的，
[0021] 与现有技术相比，本发明的积极效果为：
[0022] 在计算大整数乘法时，首先将被乘数与乘数按照上述方案拆分为一定长度的若干字；拆分后将上述字按照本方法要求转化为浮点数，在浮点数转化过程中，我们能够充分利用浮点数的符号位，有效节省浮点数存储空间，从而我们减少了存储乘数与被乘数的字节数；利用浮点数的乘加指令，根据一定次序累加被乘数每一个字与乘数每一个字乘积到对应位置，由于字节数的减少，导致乘加次数的减少；最后将计算结果转化为要求的形式。本发明利用浮点数实现大整数乘法运算，可减少计算的复杂度，提升计算速度。
[0023]乘数字长 未优化乘加操作计算量 优化后乘加操作计算量
128×128 6×6 6×6
256×256 11×11 11×11
512×512 23×23 22×22
1024×1024 45×45 43×43
2048×2048 94×94 90×90
附图说明
[0024] 图1为本发明提供的大整数乘法计算加速方法流程图。
具体实施方式
[0025] 下面结合附图对本发明进行进一步详细描述。
[0026] 一种利用浮点数计算指令实现大整数乘法的方法，其特征在于，包括：在大整数乘法中，设置被乘数A的长度为n比特，设置乘数B的长度为m比特；将位宽w比特定义为一个字，A[0:s](s>＝0)表示A的第0个字到第s个字，A[u]表示A的第u个字。
[0027] 本发明在计算过程中使用浮点式格式，其使用的浮点数符合IEEE 754所规定的浮点数标准。IEEE标准从逻辑上用三元组{S,E,T}表示一个数N，其中，S表示符号位，E表示阶码，T表示长度为p比特的尾码，同时尾码中还有一位隐含位。
[0028]S E T
[0029] 本发明计算过程包括：
[0030] (a)将长度为n比特被乘数A分为N段，长度为m比特乘数B分为M段，同时满足[0031] M≥N，每段的长度为w比特，分段从低位到高位进行，若最后一段长度不足w比特，将该段高位补0。其中段数M与N计算式为：
[0032]
[0033] 被乘数A与乘数B，按照以下格式进行分段：
[0034]
[0035] 最终A[0:N-1]与B[0:M-1]即为分段后的结果。其中w为分段后每段的长度，w取满足以下条件的最大值：
[0036]
[0037] (b)按照上述说明，被乘数A与乘数B分段后，其结果可以表示为A[0:N-1]与B[0:M-1]，将被乘数A的每段保存到单个浮点数中，本发明需要(N+1)个初值为0的浮点数用来表示分段后的被乘数，即用一组浮点数A’[0:N]表示转化后的被乘数。在此定义字长w比特的A[u]转化的浮点数结果为A’[u]。将从A[0]开始到A[N-1]中的每一字A[u]分别进行以下操作：
[0038] 1)判断A[u]与2w-1的大小关系，如果A[u]小于2w-1，转换方式为下列步骤2)，否则，转换方式为下列步骤3)。
[0039] 2)将长度为w的数值A[u]强制转化为浮点数A’[u]。
[0040] 3)将(A[u]-2w)的计算结果保存到A’[u]中，并且置A[u+1]的数值为(A[u+1]+1)。完成上述转化后便将被乘数A存储到一组浮点数A’[0:N]中。同上述操作可以将乘数B存储到另一组浮点数B’[0:M]中。
[0041] 步骤(b)之后，更包括下列步骤：
[0042] (c)为方便叙述，我们完成上述步骤(b)后，被乘数A与乘数B分别存储到浮点数A’[0:N]与B’[0:M]中，大整数乘法的计算中间结果用一组个数为(M+N+1)的浮点数R’[0:M+N]来表示，在此利用浮点数的运算指令，现定义以下操作：min(a,b)操作取a与b中的较小值，max(a,b)操作取a与b中的较大值；本发明采用的熔加运算(Fused Multiply-Add，FMA)进行大整数乘法操作，根据一定次序累加被乘数的一个字和乘数的一个字相乘的乘积到浮点数R’[k]中，完成按字扫描的大整数乘法运算操作，其中R’[k]计算方法为：
[0043]
[0044] 步骤(c)之后，更包括下列步骤：
[0045] (d)经过上述运算，计算结果以浮点数形式保存在R’[0:M+N]中，将R’[0:M+N]中的每个浮点数强制转化到能容纳上述浮点类型的单个浮点数的定点数R[0:M+N]中；具体转化方法为对从R’[0]到R’[M+N]中的每一R’[u]，分别按照符合C语言类型的强制类型转换，将R’[u]转换为R[u]。转化后将结果保存到一组定点数R[0:M+N]。
[0046] (e)在此设置计算乘积的计算结果用字母C表示，其长度为(M+N)×w位，与乘数、被乘数的表示方法类似，将位宽w比特定义为一个字，C[0:m+n-1]表示C的第0个字到第(m+n-1)个字，C[u]表示C的第u个字。将上述从R[0]到R[M+N-1]的每一定点数R[u]分别进行下列操作：
[0047] 1)R[u]对2w进行求模运算，将求模结果保存到C[u]中(C[u]＝R[u]％2w)；
[0048] 2)符合C语言类型的右移操作，对每一R[u]右移w位，结果保存到Carry1中(Carry1＝R[u]>>w)；
[0049] 3)将R[u]右移后的结果Carry1与R[u+1]作和，并保存到R[u+1]中(R[u+1]＝R[u+1]+Carry1)。
[0050] 上述右移操作具体是指正数右移前位补0，负数右移前位补1。经过上述操作，最后大整数乘法的结果保存在C[0:m+n-1]中。
