大整数的平方代码
gxqcn曾经说过，大整数的平方有快速算法。经本人实践后，果然如此。虽然我写的程序显得幼稚，但平方算法确实比调用乘法要快大约一倍的时间。以下是本人的习作。
编译环境：Windows xp ,vc++6.0,debug模式，32位环境。
硬件设备：AMD Athlon(tm) II X2250 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 ;right
mov ebx,dword ptr ; //LL
sub ebx,1 ///控制外层循环。
je kkkk
loop01:
mov eax,dword ptr////每次读取新的LL。eax用于控制
mov ecx,ebx ;;///赋值给ecx控制内层循环
sub eax,ebx
mov LEFT_REG,dword ptr ; //left每次进入内循环时取新值。
lea LEFT_REG, ////这个eax控制LEFT_REG的位置
shl eax,1;;///乘以2
sub eax,1 ;;
mov RESULT_REG, dword ptr ;
lea RESULT_REG,///这个eax控制RESULT_REG的位置
loop00:
mov eax,dword ptr
mul dword ptr
add dword ptr ,eax
adc dword ptr ,edx
lea LEFT_REG,
lea RESULT_REG,
dec ecx
jnz loop00;;///内层循环
lea RIGHT_REG,
dec ebx
jnz loop01/////外层循环
/*//---------------------------------------------------------------///
以上loop00和loop01循环，用来求非平方项的乘积，
结果保存在两个相邻的RESULT和RESULT中，
不考虑最终的模10^8进位
///---------------------------------------------------------------*///
mov RESULT_REG, dword ptr
mov ecx,dword ptr///每次读取新的LL
shl ecx,1;;///乘以2
sub ecx,3
loop02:
mov eax,dword ptr
shld dword ptr,eax,1
shl dword ptr,1
lea RESULT_REG,
dec ecx
jnz loop02
/*///-----------------------------------------------------------------------------------------////
以上的loop02用来将非平方项的结果乘以2， 不考虑最终的模10^8进位
////-----------------------------------------------------------------------------------------*////
kkkk:
mov ecx,dword ptr
mov RESULT_REG, dword ptr
mov LEFT_REG, dword ptr ;right
loop03:
mov eax,dword ptr
mul dword ptr
add dword ptr ,eax
adc dword ptr ,edx
lea RESULT_REG,
lea LEFT_REG,
dec ecx
jnz loop03
/*///-------------------------------------------------------------------------------////
以上的loop03用来把平方项加到结果中，不考虑进位。
////-------------------------------------------------------------------------------*////
xor edx,edx
mov ebx,100000000
mov ecx,dword ptr
shl ecx,1
mov RESULT_REG, dword ptr ; result
loop04:
mov eax,dword ptr ///取本位的高32位做除法
div ebx
add dword ptr ,eax///商加在下一个数的高32位
mov eax, dword ptr ///取本位数的低32位做除法
div ebx
mov dword ptr ,edx///本位的余数，就是结果
xor edx,edx
add dword ptr ,eax ///本位的商，加在下一位的低32位上。
adc dword ptr ,edx;;
lea RESULT_REG,
sub ecx,1
jnz loop04
/*///---------------------------------------------------------------------------////
以上的loop04语句用来将RESULT和RESULT组成的64位中间结果进位到
RESULT[(i+1)*8+4]和RESULT[(i+1)*8]并获得正确结果
////----------------------------------------------------------------------------*////
mov ecx,dword ptr
shl ecx,1
mov edx,1
xor ebx,ebx
mov RESULT_REG, dword ptr ; result
loop05:
mov eax, dword ptr
mov dword ptr ,eax
mov dword ptr,ebx
mov dword ptr,ebx
add edx,1
sub ecx,1
jnz loop05
/*//--------------------------------------------------------------------------/////
以上的loop05语句，用来把正确结果移动到正常位置，
并将多余的数清零。
//*-------------------------------------------------------------------------*////
pop ebp
pop ebx
pop edi
pop esi
ret
}
}/////*///
这里给出一楼函数的一个调用示例：
#include <stdio.h>
unsigned int bignum={0}, result={0};
//----------------------------------------//
//把一楼的代码粘贴在这里
//----------------------------------------//
void main()
{
int i,s,Len;
//ch[]=30000000000321456987100000009999999999999999993214
//将ch[]按10^8为进位的基，存入数组bignum[]中。
bignum=99993214;
bignum=99999999;
bignum=999999;
bignum=87100000;
bignum=3214569;
bignum=0;
bignum=30;
//大整数的长度是：
Len=6+1;
//调用一楼的函数，注意函数的接口条件：
_axa_(result,bignum,Len);
i=100;
while((result==0)&&(i>0))//前导零清除。
{
i--;
}
printf("%d",result);//输出语句。把乘积的结果输出。
for(s=i-1;s>=0;s--)//输出语句。把乘积的结果输出。
printf("%08d",result);
//这里是实际的平方结果：
//result[]=bignum[]^2=9000000000 1928741922 6103335194 5554095728 3913933484
// 0000095637 1857710787 9986428000 0000000000 046049796
// 共99位数。实际输出数字是全部连在一起的，为了方便我把它写成了10位一组，
printf("\n");
return 0;
}
有更好的算法哦~~~ 本帖最后由 只是呼吸 于 2016-1-13 20:43 编辑
有更好的算法哦~~~
咳咳……。我不会哦，我只会最原始的啊。这个算法就是模拟手算的平方算法，比调用乘法快。
页:
[1]