大整数的平方代码

只是呼吸 · 发表于 2016-1-11 21:55:42

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

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

×

gxqcn曾经说过，大整数的平方有快速算法。经本人实践后，果然如此。虽然我写的程序显得幼稚，但平方算法确实比调用乘法要快大约一倍的时间。
以下是本人的习作。

   编译环境：Windows xp ,vc++6.0,debug模式，32位环境。
   硬件设备：AMD Athlon(tm) II X2  250       3.0GHz    2.00G的内存
   运行时间：一个14700位（十进制）数的平方，用时<2.7毫秒。
   函数原形： void _axa_( UINT32 *result, UINT32 * left,int LL)
         其中：*result 平方后的结果。 * left 待平方的数字。LL, *left的长度。
         进制：采用10000 0000（10^8)进制。十进制数高位对应数组较大的下标，十进制数的低位对应数组较小的下标。
   特别声明：1）*result 要用到的存贮空间，是待平方数* left 的实际空间的4倍。
                     2）待平方数* left 的长度不能超过14700位十进制数。

// 特别声明：1）*result 要用到的存贮空间，是待平方数* left 的实际空间的4倍。
// 2）待平方数* left 的长度不能超过14700位十进制数。
// 3) 如果采用VC++6.0以外的编译器，请确保每个存贮单元为32位。
// 4) *result的空间在使用之前要进行清零
_declspec(naked)
void _axa_( unsigned int *result, unsigned int *left,int LL)
{
#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
///------------------------------------------------------------------------////
mov RIGHT_REG, dword ptr[esp + 08h+16] ; right
mov ebx,dword ptr[esp+0Ch+16] ; //LL
sub ebx,1 ///控制外层循环。
je kkkk
loop01:
mov eax,dword ptr[esp+0Ch+16] ////每次读取新的LL。eax用于控制
mov ecx,ebx ;;///赋值给ecx控制内层循环
sub eax,ebx
mov LEFT_REG, dword ptr [esp + 08h+16] ; //left每次进入内循环时取新值。
lea LEFT_REG,[LEFT_REG+4*eax] ////这个eax控制LEFT_REG的位置
shl eax,1;;///乘以2
sub eax,1 ;;
mov RESULT_REG, dword ptr[esp + 04h+16] ;
lea RESULT_REG,[RESULT_REG+8*eax]///这个eax控制RESULT_REG的位置
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循环，用来求非平方项的乘积，
结果保存在两个相邻的RESULT[i]和RESULT[i+1]中，
不考虑最终的模10^8进位
///---------------------------------------------------------------*///
mov RESULT_REG, dword ptr[esp + 04h+16]
mov ecx,dword ptr[esp+0Ch+16] ///每次读取新的LL
shl ecx,1;;///乘以2
sub ecx,3
loop02:
mov eax,dword ptr [RESULT_REG+8]
shld dword ptr[RESULT_REG+12],eax,1
shl dword ptr[RESULT_REG+8],1
lea RESULT_REG,[RESULT_REG+8]
dec ecx
jnz loop02
/*///-----------------------------------------------------------------------------------------////
以上的loop02用来将非平方项的结果乘以2，不考虑最终的模10^8进位
////-----------------------------------------------------------------------------------------*////
kkkk:
mov ecx,dword ptr[esp+0Ch+16]
mov RESULT_REG, dword ptr[esp + 04h+16]
mov LEFT_REG, dword ptr[esp + 08h+16] ; right
loop03:
mov eax,dword ptr [LEFT_REG]
mul dword ptr [LEFT_REG]
add dword ptr [RESULT_REG],eax
adc dword ptr [RESULT_REG+4],edx
lea RESULT_REG,[RESULT_REG+16]
lea LEFT_REG,[LEFT_REG+4]
dec ecx
jnz loop03
/*///-------------------------------------------------------------------------------////
以上的loop03用来把平方项加到结果中，不考虑进位。
////-------------------------------------------------------------------------------*////
xor edx,edx
mov ebx,100000000
mov ecx,dword ptr[esp+0Ch+16]
shl ecx,1
mov RESULT_REG, dword ptr[esp + 04h+16] ; result
loop04:
mov eax,dword ptr [RESULT_REG+4] ///取本位的高32位做除法
div ebx
add dword ptr [RESULT_REG+12],eax///商加在下一个数的高32位
mov eax, dword ptr [RESULT_REG] ///取本位数的低32位做除法
div ebx
mov dword ptr [RESULT_REG],edx ///本位的余数，就是结果
xor edx,edx
add dword ptr [RESULT_REG+8],eax ///本位的商，加在下一位的低32位上。
adc dword ptr [RESULT_REG+12],edx;;
lea RESULT_REG, [RESULT_REG+8]
sub ecx,1
jnz loop04
/*///---------------------------------------------------------------------------////
以上的loop04语句用来将RESULT[i*8+4]和RESULT[i*8]组成的64位中间结果进位到
RESULT[(i+1)*8+4]和RESULT[(i+1)*8]并获得正确结果
////----------------------------------------------------------------------------*////
mov ecx,dword ptr[esp+0Ch+16]
shl ecx,1
mov edx,1
xor ebx,ebx
mov RESULT_REG, dword ptr[esp + 04h+16] ; result
loop05:
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 loop05
/*//--------------------------------------------------------------------------/////
以上的loop05语句，用来把正确结果移动到正常位置，
并将多余的数清零。
//*-------------------------------------------------------------------------*////
pop ebp
pop ebx
pop edi
pop esi
ret
}
}/////*///

复制代码

只是呼吸 · 发表于 2016-1-11 23:13:05

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

#include <stdio.h>
unsigned int bignum[2000]={0}, result[500000]={0};
//----------------------------------------//
//把一楼的代码粘贴在这里
//----------------------------------------//
void main()
{
int i,s,Len;
// ch[]=30000000000321456987100000009999999999999999993214
//将ch[]按10^8为进位的基，存入数组bignum[]中。
bignum[0]=99993214;
bignum[1]=99999999;
bignum[2]=999999;
bignum[3]=87100000;
bignum[4]=3214569;
bignum[5]=0;
bignum[6]=30;
//大整数的长度是：
Len=6+1;
//调用一楼的函数，注意函数的接口条件：
_axa_(result,bignum,Len);
i=100;
while((result[i]==0)&&(i>0))//前导零清除。
{
i--;
}
printf("%d",result[i]);//输出语句。把乘积的结果输出。
for(s=i-1;s>=0;s--)//输出语句。把乘积的结果输出。
printf("%08d",result[s]);
//这里是实际的平方结果：
//result[]=bignum[]^2=9000000000 1928741922 6103335194 5554095728 3913933484
// 0000095637 1857710787 9986428000 0000000000 046049796
// 共99位数。实际输出数字是全部连在一起的，为了方便我把它写成了10位一组，
printf("\n");
return 0;
}

复制代码

无心人 · 发表于 2016-1-13 16:30:24

有更好的算法哦~~~

只是呼吸 · 发表于 2016-1-13 20:21:16

本帖最后由只是呼吸于 2016-1-13 20:43 编辑

有更好的算法哦~~~

咳咳……。我不会哦，我只会最原始的啊。这个算法就是模拟手算的平方算法，比调用乘法快。

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

[原创] 大整数的平方代码

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