大整数乘法代码

只是呼吸 · 发表于 2015-12-3 14:28:23

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

在x86上128位二进制乘法最快速算法征解这篇文章里，liangbch的程序是最快的，在我的电脑上却不能运行，十分不解。而liangbch在x86上128位二进制乘法最快速算法征解中102楼的程序在我的电脑上能运行，于是大喜，学习之。
这里就是学习102楼的汇编乘法习作。

   编译环境：Windows xp ,vc++6.0,debug模式。
   硬件设备：AMD Athlon(tm) II X2  250       3.0GHz    2.00G的内存
   运行时间：两个14700位（十进制）数相乘，用时<5毫秒。
   函数原形： void Big_mul( UINT32 *result,const UINT32 * const left,const UINT32 * const right,int LL,int LR)
         其中：*result 乘积的结果。 * left 乘数。*right 另一个乘数。LL, *left的长度，LR， *right的长度。
         进制：采用10000 0000进制。十进制数高位对应数组较大的下标，十进制数的低位对应数组较小的下标。
   特别声明：*result 要用到的存贮空间，是* left 和*right 两个乘数的空间之和的两倍。
                  * left 和*right 两个乘数的长度不能同时超过14700位十进制数。

/* 特别声明：*result 要用到的存贮空间，是* left 和*right 两个乘数的空间之和的两倍。*/
_declspec(naked)
void Big_mul( unsigned int *result,
const unsigned int * const left,
const unsigned int * const right,int LL,int LR)
{
#undef BASE10000_MASK
#define BASE10000_MASK 100000000
#undef LEFT_REG
#undef RIGHT_REG
#undef RESULT_REG
#define LEFT_REG esi
#define RIGHT_REG edi
#define RESULT_REG ebp
__asm
{
push esi
push edi
push ebx
push ebp
/*/------------------------------------------------------////
以上push语句原文如此，改一个都不行
//------------------------------------------------------*////
mov RIGHT_REG, dword ptr[esp + 0Ch+16]
mov ebx,dword ptr[esp+14h+16]
loop01:
mov eax,dword ptr[esp+14h+16]
sub eax,ebx
mov ecx,dword ptr[esp+10h+16] ; //ecx中的值是内循环的次数，每次进入内循环时取新值。
mov LEFT_REG, dword ptr [esp + 08h+16] ; // LEFT--REGk中的值是内循环的乘数，每次进入内循环时取新值。
mov RESULT_REG, dword ptr[esp + 04h+16] ; //RESULT_REG，结果，每次进入内循环时移位，
lea RESULT_REG,[RESULT_REG+8*eax]
loop00:
mov eax,dword ptr [LEFT_REG]
mul dword ptr [RIGHT_REG]
add dword ptr [RESULT_REG],eax
adc dword ptr [RESULT_REG+4],edx
lea LEFT_REG,[LEFT_REG+4]
lea RESULT_REG,[RESULT_REG+8]
dec ecx
jnz loop00;;///内循环。
lea RIGHT_REG,[RIGHT_REG+4]
dec ebx
jnz loop01///////外循环
/*/------------------------------------------------------------------------------------------------------------////
以上的loop00和loop01循环就是模拟手算的硬乘法。不考虑进位。
其中：第i列由RIGHT_REG[8*i]和RIGHT_REG[8*i+4]保存中间结果。
由于两个存贮单元只能存贮64位二进制数。故本函数要求输入的两个十进制乘数
不能同时超过14700位。
//-----------------------------------------------------------------------------------------------------------*////
xor edx,edx
mov ebx,BASE10000_MASK
mov ecx,dword ptr [esp + 10h+16]
add ecx,dword ptr [esp + 14h+16]
mov RESULT_REG, dword ptr[esp + 04h+16] ; result
loop02:
mov eax,dword ptr [RESULT_REG+4] ///取本位的高位做除法
div ebx
add dword ptr [RESULT_REG+12],eax///商加在下一个数的高位
mov eax, dword ptr [RESULT_REG] ///取本位数的低位，做除法
div ebx
mov dword ptr [RESULT_REG],edx ///本位的余数就是结果。
xor edx,edx
add dword ptr [RESULT_REG+8],eax ///本位的商，加在下一位上面
adc dword ptr [RESULT_REG+12],edx
lea RESULT_REG, [RESULT_REG+8]
sub ecx,1
jnz loop02
/*/---------------------------------------------------------------------------------------------------------------------------------------///
以上loop02语句是将第i列RIGHT_REG[8*i]和RIGHT_REG[8*i+4]保存的中间结果。进位到第i+1列。
//---------------------------------------------------------------------------------------------------------------------------------------*///
mov ecx,dword ptr [esp + 10h+16]
add ecx,dword ptr [esp + 14h+16]
mov edx,1
xor ebx,ebx
mov RESULT_REG, dword ptr[esp + 04h+16] ; result
loop03:
mov eax, dword ptr [RESULT_REG+8*edx]
mov dword ptr [RESULT_REG+4*edx],eax
mov dword ptr[RESULT_REG+8*edx],ebx
mov dword ptr[RESULT_REG+8*edx+4],ebx
add edx,1
sub ecx,1
jnz loop03
/*/----------------------------------------------------------------------------------------////
以上loop03循环语句将结果移动到正常位置，并将多余的数清零。
//*--------------------------------------------------------------------------------------*////
pop ebp
pop ebx
pop edi
pop esi
/*/------------------------------------------------------////
以上pop语句原文如此，改一个都不行
//------------------------------------------------------*////
ret
}
}

复制代码

只是呼吸 · 发表于 2015-12-3 15:05:42

这里给出1楼函数的一个调用示例：

#include <stdio.h>
#define NA 14700
char a[1500000]={0},b[1500000]={0};
unsigned int c[10000]={0},e[10000]={0},result[40001]={0};
int main()
{
void Big_mul( unsigned int *result,
const unsigned int * const left,
const unsigned int * const right,int LL,int LR)；
int i,s,m1,m2;
// c[]=3014720201400230214565;
// e[]=999999926201254508952102;
//计算c[]xe[]
c[0]=30214565;
c[1]=2014002;
c[2]=301472;
e[0]=8952102;
e[1]=62012545;
e[2]=99999992;
m1=3;
m2=3;
Big_mul(result,c,e,m1,m2);///
i=m1+m2+5;
while((result[i]==0)&&(i>0))//前导零清除。
{
i--;
}
printf("%u",result[i]);//输出语句。把乘积的结果输出。
for(s=i-1;s>=0;s--)//输出语句。把乘积的结果输出。
printf("%08u",result[s]);//输出语句。
printf("\n");
return 0;
}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[原创] 大整数乘法代码

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。