内存释放有问题,实在搞不定了...
#include "stdafx.h"#include "conio.h"
#include "stdlib.h"
#include "malloc.h"
#include "time.h"
void generate(unsigned int *R)
{
int i,temp1,temp2;
time_t t; int h=0;
srand((unsigned) time(&t));
for(i=0; i<8; i++)
{
temp1=rand();
temp2=rand();
R[31-i]=temp1;
R[31-i]=R[31-i]<<16;
R[31-i]=temp2+R[31-i];
}
for(i=0; i<24; i++)
{
R[i]=0x0;
}
R[0]=R[0]|0x1;
R[31]=R[31]|0x80000000;
/*for(i=0;i<32;i++)
printf("%08x",R[31-i]);
printf("\n");*/
}
int count_l(unsigned int *R1,int L_R1)
{
unsigned int temp;int i,j,flag=1;int num=1;
temp=0;
if(R1[0]!=0x1)
{
for(i=1;i<32;i++)
{
temp=(R1[0]<<(31-i))>>31;
if(temp==1)
break;
else
continue;
}
}
else
{
for(j=1;j<L_R1;j++)
{
if(R1[j]==0)
continue;
else
break;
}
for(i=0;i<32;i++)
{
temp=(R1[j]<<(31-i))>>31;
if(temp==1)
break;
else
continue;
}
num=32*j+i;
}
return num;
}
void sub(unsigned int *R1,int h,unsigned int *R2,int t,unsigned int *R_sub,unsigned int* L_r)
{
int i,max,min;
unsigned int temp;
temp=0;
if(h<t)
{
min=h;
max=t;
}
else if(h>t)
{
min=t;
max=h;
}
else
{
max=t;min=t;
}
for(i=0;i<min;i++)//将两个数组的前min个元素进行相减
{
R_sub[i]=R1[i]-R2[i]-temp;
if((R1[i]-temp<R2[i])||((R_sub[i]==R1[i])&&(R2[i]!=0)))
{
temp=1;
}
else temp=0;
}
if(max==min)
{
while(temp)
{
max++;
R_sub[max-1]=0;
temp=0;
}
}
else{
for(i=min;i<max;i++)//将剩余的元素复制给和
{ if(max==h)
{
R_sub[i]=R1[i]-temp;
temp=0;
}
else
{
R_sub[i]=R1[i]-temp;
temp=0;
}
}
}
while(R_sub[max-1]==0)
{
max--;
}
L_r[0]=max;
}
int count(unsigned int *R1,int L_R1)
{ unsigned int temp;int i,j,flag=1;int num=0;
temp=0;
for(j=L_R1-1;j>=0;j--)
{
if(R1[j]==0)
continue;
else
break;
}
for(i=31;i>=0;i--)
{
temp=R1[L_R1-1]>>i;
if(temp==1)
break;
else
continue;
}
num=32*j+i+1;
return num;
}
void multiply(unsigned int *R1,unsigned int *R2,unsigned int *R_mul,int h,int t,unsigned int *L_r)
{
int i,j,temp,r;
unsigned int tempa,tempb,tempc;
__int64 tempm,temp1;
for(i=0;i<h+t;i++)
{
R_mul[i]=0;
}
for(i=0;i<t;i++)
{
tempc=0;
for(j=0;j<h;j++)
{
tempm=(__int64)R1[j]*R2[i];
temp1=(R_mul[i+j]+tempm+tempc);
tempa=temp1>>32;
tempb=(unsigned int)temp1&0xffffffff;
R_mul[i+j]=tempb;
tempc=tempa;
}
R_mul[i+h]=(unsigned int)tempa;
}
R_mul[h+t-1]=(unsigned int)tempc;
temp=h+t;
while(R_mul[temp]==0)
{temp--;
}
L_r[0]=temp;
}
void Right_shift(unsigned int* R1,unsigned int* Result,int R1_length,int move,unsigned int *L_r)
{
int k = move/32;
int m = move%32;
int i,j,L,intLength;
L=count(R1,R1_length);
if((L-move)%32==0)
{
intLength=(L-move)/32;
}
else
intLength=(L-move)/32+1;
for(j=0;j<1;j++)
Result[j+k] = R1[j]>>m;
for(j=0;j<intLength-1;j++)
{
if(m==0)
Result[j] = R1[j+k];
else
Result[j] = (R1[j+k+1]<<(32-m)) +(R1[j+k]>>m);
}
Result[intLength-1] = R1[intLength+k-1]>>m;
L_r[0]=intLength;
}
void Left_shift(unsigned int* R1,unsigned int* Result,int R1_length,int move,unsigned int *L_r)
{
int L1,intLength = R1_length; int i,j;
int k = move/32;
int m = move%32;
L1=count(R1,R1_length);
if(((L1+move)%32)==0)
L_r[0]=(L1+move)/32;
else
L_r[0]=(L1+move)/32+1;
for(i=0;i<L_r[0];i++)
{
Result[i] = 0;
}
if(m==0)
{
for(j=0;j<intLength+k;j++)
Result[j+k] = R1[j];
}
else
{
for(j=0;j<1;j++)
Result[j+k] = R1[j]<<m;
for(j=1;j<intLength;j++)
{
if(m==0)
Result[j+k] = R1[j-1]>>m;
else
Result[j+k] = (R1[j-1]>>(32-m)) +(R1[j]<<m);
}
Result[intLength+k] = R1[intLength-1]>>(32-m);
}
}
void square(unsigned int *R1,int t, unsigned int *R_square,unsigned int *L_r)
{
unsigned __int64 tempxy,temp1,temp2,temp3,tempc,tempz,x,c;int i,j;
unsigned int y,temp,tempnum=0;
c=0;
for(i=0;i<t;i++)
{
R_square[i]=0;
}
if(t==1)
{
temp1=(unsigned __int64)R1[0]*R1[0];
R_square[0]=(unsigned int)temp1&0xffffffff;
R_square[1]=(unsigned int)(temp1>>32);
if(R_square[1]!=0)
L_r[0]=2;
else
L_r[0]=1;
}
else
{
for(i=0;i<t;i++)
{
tempxy=R_square[2*i]+(__int64)R1[i]*R1[i];
x=tempxy>>32;
y=(unsigned int)tempxy&0xffffffff;
c=x;
R_square[2*i]=y;
for(j=i+1;j<t;j++)
{
temp1=(__int64)R1[i]*R1[i];
temp2=(__int64)temp1+R_square[i+j];
temp3=(__int64)temp1+c;
tempxy=(__int64)temp2+temp3;
if(tempxy<temp2||tempxy<temp3)
temp=1;
else
temp=0;
x=tempxy>>32;
y=(unsigned int)tempxy&0xffffffff;
c=x;
tempc=temp<<32;
c=c|tempc;
R_square[i+j]=y;
}
R_square[i+t]+=x;
if(temp)
R_square[i+t+1]=temp;
else
;
}
tempnum=2*t;
while(R_square[tempnum-1]==0)
{
tempnum--;
}
L_r[0]=tempnum;
}
}
void divide(unsigned int* R1,unsigned int* R2,unsigned int* remainder,int L_R1,int L_R2,unsigned int *L_r)
{
int L1,L2,Ld,temp1,temp2,L_shift,c1,c2,c3,temp,s=1;int i;int max;
unsigned int *R_temp=NULL;unsigned int cmp,tpnum=0;
unsigned int *R_temp1;
unsigned int *R_temp2;
unsigned int *R_sub;
R_temp2=(unsigned int *)malloc((L_R1-L_R2) * sizeof(unsigned int));
R_temp1=(unsigned int *)malloc(L_R1 * sizeof(unsigned int));
R_temp=(unsigned int *)malloc(L_R1 * sizeof(unsigned int));
R_sub=(unsigned int *)malloc(L_R1 * sizeof(unsigned int));
L_r[0]=1;
for(i=0;i<(L_R1-L_R2);i++)
R_temp2[i]=0x0;
L1=count(R1,L_R1);
L2=count(R2,L_R2);
if(L1<L2)
{
for(i=0;i<L_R1;i++)
remainder[i]=R1[i];
L_r[0]=L_R1;
}
else if (L1==L2)
{
cmp=L_R1;
while(R1[cmp-1]==R2[cmp-1])
cmp--;
if(R1[cmp-1]<R2[cmp-1])
{
for(i=0;i<L_R1;i++)
remainder[i]=R1[i];
L_r[0]=L_R1;
}
else
{
sub(R1,L_R1,R2,L_R1,R_sub,L_r);
for(i=0;i<L_r[0];i++)
remainder[i]=R_sub[i];
};
}
else
{
while(L1>L2)
{
c1=L1%32;c3=L1/32;
c2=L2%32;
L_shift=L1-L2;
Left_shift(R2,R_temp,L_R2,L_shift,L_r);
c3=L_r[0];
while((R1[c3-1]==R_temp[c3-1])&&(c3>0))
{
c3--;
}
if(R1[c3-1]<R_temp[c3-1])
Left_shift(R2,R_temp,L_R2,L_shift-1,L_r);
else
Left_shift(R2,R_temp,L_R2,L_shift,L_r);
tpnum=L_r[0];
sub(R1,L_R1,R_temp,tpnum,R_sub,L_r);
for(i=0;i<L_r[0];i++)
R1[i]=0;
for(i=0;i<L_r[0];i++)
R1[i]=R_sub[i];
L_R1=L_r[0];
L1=count(R1,L_R1);
L2=count(R2,L_R2);
//
}
if(L1==L2)
{
c1=L1%32;
c3=L1/32;
if((L1%32)==0)
{
cmp=L1/32;
}
else
cmp=L1/32+1;
while((R1[cmp]==R2[cmp])&&cmp>0)
{
cmp--;
}
if(R1[cmp-1]<R2[cmp-1])
{ for(i=0;i<L_r[0];i++)
remainder[i]=R_sub[i];
}
else
{
sub(R1,L_R1,R2,L_R1,R_sub,L_r);
for(i=0;i<L_r[0];i++)
remainder[i]=R_sub[i];
};
}
else
{
for(i=0;i<L_r[0];i++)
remainder[i]=R1[i];
};
while(R_sub[L_r[0]-1]==0)
L_r[0]--;
for(i=0;i<L_r[0];i++)
{
remainder[i]=R_sub[i];
}
}
free(R_temp2);
free(R_temp1);
free(R_temp);
free(R_sub);
}
void mod(unsigned int *M,int L_m,unsigned int *P,int L_p,unsigned int *Re,unsigned int *L_r)
{
unsigned int x;unsigned int *A,*B;int l,i,j,k1,k2;unsigned int temp,La,Lb,tpnum;int h;int t;
unsigned int *A_temp=NULL;
unsigned int * remainder;
A=(unsigned int *)malloc(L_p * sizeof(unsigned int));
B=(unsigned int *)malloc(L_p * sizeof(unsigned int));
A_temp=(unsigned int *)malloc(2*L_p * sizeof(unsigned int));
remainder=(unsigned int *)malloc(2*L_p * sizeof(unsigned int));
//完成s1
for(i=0;i<2*L_p;i++)
A[i]=0;
A[0]=1;
B[0]=0x523452fe;
l=count(M,L_m);//计算m的长度；
//i=l-1;
if((L_m==1)&&M[0]==1)
{
A[0]=B[0];
divide(A,P,remainder,1,L_p,L_r);
}
else{
for(i=l-1;i>=0;i--)
{//printf("test %x!\n",L_r[0]);
square(A,L_p,A_temp,L_r);
tpnum=L_r[0];
divide(A_temp,P,remainder,tpnum,L_p,L_r);
for(j=0;j<L_r[0];j++)
{
A[j]=remainder[j];
}
k1=i/32;
k2=i%32;
temp=(M[k1]<<(31-k2))>>31;
if(temp)
{
multiply(A,B,A_temp,L_p,L_p,L_r);
tpnum=L_r[0];
divide(A_temp,P,remainder,tpnum,L_p,L_r);
for(j=0;j<L_r[0];j++)
{
A[j]=remainder[j];
}
}
else
;
}
}
while(A[L_r[0]-1]==0)
L_r[0]--;
for(j=0;j<L_r[0];j++)
{
Re[j]=A[j];
}
//free(A);
free(B);
free(A_temp);
free(remainder);
}
void Miller_test(unsigned int *P,int L_p,unsigned int *Re,unsigned int *L_r)
{ unsigned int *M=NULL;int count,temp,i;
unsigned int *Result=NULL;
Result=(unsigned int *)malloc(2*L_p * sizeof(unsigned int));
M=(unsigned int *)malloc(2*L_p * sizeof(unsigned int));
count=count_l(P,L_p);
Right_shift(P, M,L_p,count,L_r);
temp=L_r[0];
mod(M,temp,P,L_p,Result,L_r);
for(i=1;i<L_r[0];i++)
{if(Result[0]==1&&Result[i]==0)
continue;
else
break;
}
free(M);
free(Result);
}
int _tmain(int argc, _TCHAR* argv[])
{
time_t start, finish;
double duration;
int i;unsigned __int64 a,b,c;int ttt,sss;
unsigned int *R1=NULL; unsigned int * L_r;
unsigned int *R2=NULL;
unsigned int *R_add=NULL; unsigned int *R_remain;
L_r=(unsigned int *)malloc(1*4);
R1=(unsigned int *)malloc(32 * sizeof(unsigned int));
R2=(unsigned int *)malloc(32 * sizeof(unsigned int));
R_add=(unsigned int *)malloc(64 * sizeof(unsigned int));
R_remain=(unsigned int *)malloc(32 * sizeof(unsigned int));
start=clock();
generate(R1);
Miller_test(R1,32,R_remain,L_r);
for(i=0;i<L_r[0];i++)
printf("%08x",R_remain[L_r[0]-1-i]);
if(L_r[0]==0)
{ L_r[0]=1;
R_add[0]=0;
}
else
;
finish=clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "算法执行时间：%f seconds\n", duration );
// for(i=0;i<L_r[0];i++)
//printf("%08x",R_add[L_r[0]-1-i]);
/* ttt=count(R_add,L_r[0]);
printf("\n");
printf("%d",ttt);*/
free(R1);
free(R2);
free(R_add);
free(L_r);
getch();
return 0;
}
上面是我写的大数运算的程序,当初是边写边往主函数里添加,单个的小程序是没问题的..但是合在一块就.....
谁帮我改改啊...
内存错误,我改了这边,那边又出错....所以就没标注具体那里有问题...自我感觉bug 比较多...辛苦大侠了....拜谢
[[italic] 本帖最后由 可见光 于 2007-12-6 06:26 编辑 [/italic]]
