长的速度 [英] Long Num speed
问题描述
有一段时间我一直在玩用一个小C程序来计算
计算大数的阶乘。目前每1000次乘法每秒需要1 b / b
秒，即25000P1000需要大约
秒。对于50000P1000，预期会更长，因为答案中会有更多数字
。现在，在Num Analyses论坛/小组上有一个
的帖子，那个人在一秒钟内编写了计算1000000的java代码！
。这比我预期的要强约10000倍。我的代码可以做到这一点。所以两种可能性是：
1）我正在做一些非常错误的事情
2）其他人在说谎
At我倾向于相信其数字1的那一刻。
我在下面提出我的代码，我想听听你的意见
为什么它是慢，我怎么能改进它的速度。
我知道有公共BIGNUM库已经为这样的计算优化了b
但我不想使用它们，因为我想要在较低的水平上解决这个问题。我最感兴趣的是
，以了解如何让这段代码更快地运行或者有什么选择
algorythms我应该考虑。阶乘计算只是一个测试
程序。
===================开始粘贴==========================
#include< stdio.h>
#include< stdlib.h>
#include< math.h>
#define al 1024 * 20
#define base 1000
typedef long int IntegerArrayType;
struct AEI {
IntegerArrayType data [al];
long int digits;
};
void pack（IntegerArrayType i，struct AEI * N1）;
void Amult（struct AEI * A，struct AEI * B，struct AEI * C）;
void AEIprintf（struct AEI * N1）;
void AEIfprintf（FILE * fp，struct AEI * N1）;
int main（无效）
{
struct AEI * N1，* MO， * Ans;
long i = 0，j = 0，ii，NUM，iii;
FILE * ff;
N1 = malloc（sizeof（struct AEI））;
MO = malloc（sizeof（struct AEI））;
Ans = malloc（sizeof（struct AEI））;
while（i< al）{
N1-> data [i] = 0;
MO-> data [i] = 0;
Ans - > data [i] = 0;
i ++;
}
printf（"输入整数到Factorialize： "）;
scanf（"％ld"& NUM）;
pack（1，N1）;
pack（1，Ans）;
ff = fopen（" Results.txt"，" w"）;
printf（" you entered：％ ld"，NUM）;
i = 1;
while（i< NUM）{
iii = 0;
而（iii< NUM& iii< 1000）{
ii = 1;
while（ii< al）
{
MO-> data [ii] = 0;
ii ++;
}
pack（（i + iii），MO）;
Amult（N1，MO，N1）;
iii ++;
}
i + = iii;
Amult（Ans，N1，Ans）;
printf（" \ nProgress is： ％d"，i）;
pack（1，N1）;
}
if（ff！= NULL）{
fprintf（ff，" \ n％d \ n"，i-1）;
AEIfprintf（ff，Ans）;
}
fclose（ff）;
printf（" \ nProgress：100 \％"）;
返回0;
}
void AEIprintf（struct AEI * N1）{
float fieldLength;
double temp;
char format1 [8];
long j，FL0 ;
j = N1-> digits-1;
FL0 =（长）log10（（浮动）基数）;
fieldLength =（ float）log10（（float）base）;
temp = modf（fieldLength，& fieldLength）;
format1 [0] =''％'';
format1 [1] =''0'';
format1 [2] = fieldLength + 48;
format1 [3] =''d '';
format1 [4] = 0x00;
printf（"％* d"，FL0，N1-> data [j]） ;
j--;
while（j> = 0）
{
printf（format1，N1-> data [j]）;
j--;
}
返回;
}
void AEIfprintf（FILE * fp，struct AEI * N1）{
long j = N1-> digits-1;
double fieldLength，temp;
char format0 [8]，format1 [8] ;
fieldLength =（int）log10（base）;
temp = modf（fieldLength，& fieldLength）;
format0 [0] =''％'';
format0 [1] = fieldLength + 48;
format0 [2] =''d'' ;
format0 [3] = 0x00;
format1 [0] =''％'';
format1 [1] ='' 0'';
format1 [2] = fieldLength + 48;
format1 [3] =''d'';
format1 [ 4] = 0x00;
fprintf（fp，format0，N1-> data [j]）;
j--;
while（j> = 0）{
fprintf（fp，format1，N1-> data [j]）;
j- - ;
}
返回;
}
void pack（IntegerArrayType i，struct AEI * N1）
{
长t = 1，i1，j = 0;
而（t == 1） {
i1 = i％base;
N1-> data [j] = i1;
i =（i - i1）/ base;
j ++;
if（i == 0）
t = 0;
}
N1-> digits = j;
返回;
}
void Amult（struct AEI * A，struct AEI * B，struct AEI * C）{
/ * C = A * B; * /
long i，ii，d，result，carry = 0，digits = 0;
struct AEI * Ans;
Ans = malloc（sizeof（struct AEI））;
i = 0;
d =（A->数字+ B-> digits-1）;
while（i< d）{
Ans-> data [i] = carry;
carry = 0;
ii = 0;
而（ii< = i）{
if（B-> data [ii]！= 0）{
Ans-> data [i] + = A-> data [i-ii] * B-> data [ii];
carry + = Ans-> data [i] / base ;
Ans-> data [i] = Ans-> data [i]％base;
}
ii ++;
}
随身携带+ = Ans-> data [i] / base;
Ans-> data [i] = Ans->数据[i]％base;
i ++;
}
if（carry！= 0）{
d ++;
Ans-> data [i] = carry;
}
C->位数= d;
i = 0;
while（i< d）{
C-> data [i] = Ans-> data [i];
i ++;
}
返回;
}
====================结束粘贴===================== =======
我试图用空格而不是制表符缩进代码，但如果有些
部分最终没有正确缩进，我希望没有人会反对
我。
谢谢你
For a while now i have been "playing" with a little C program to
compute the factorial of large numbers. Currently it takes aboy 1
second per 1000 multiplications, that is 25000P1000 will take about a
second. It will be longer for 50000P1000 as expected, since more digits
will be in the answer. Now, on the Num Analyses forum/Group there is a
post reaporting that that person wrot java code that computed 1000000!
in about a second. That is about 10000 times faste than I would expect
my code to do it. So the two possiblilities are:
1) I am doing something terribly wrong
2) The othr person is lying
At the moment i am inclined to believe that its number 1.
I am posing my code below, I would like to hear your opinions about
why it is slow and how i can improove its speed.
I know that there are public BIGNUM libraries which are already
optimized for such calculations, but I dont want to use them, bcause i
want to approach this problem on a lower level. I am mostly interested
to find out how to get this code perform faster or what alternative
algorythms i should consider. The factorial calculation is just a test
program.
===================start paste==========================
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define al 1024*20
#define base 1000
typedef long int IntegerArrayType;
struct AEI{
IntegerArrayType data[al];
long int digits;
};
void pack(IntegerArrayType i, struct AEI *N1);
void Amult(struct AEI * A, struct AEI * B, struct AEI * C);
void AEIprintf(struct AEI * N1);
void AEIfprintf(FILE * fp, struct AEI * N1);
int main(void)
{
struct AEI *N1, *MO, *Ans;
long i = 0, j = 0, ii, NUM, iii;
FILE *ff;
N1=malloc(sizeof(struct AEI));
MO=malloc(sizeof(struct AEI));
Ans=malloc(sizeof(struct AEI));
while (i < al){
N1->data[i] = 0;
MO->data[i] = 0;
Ans->data[i]=0;
i++;
}
printf("Enter integer to Factorialize: ");
scanf("%ld", &NUM);
pack(1, N1);
pack(1, Ans);
ff = fopen("Results.txt", "w");
printf("you entered: %ld", NUM);
i=1;
while(i < NUM ){
iii=0;
while(iii<NUM && iii<1000){
ii = 1;
while (ii < al)
{
MO->data[ii] = 0;
ii++;
}
pack((i+iii), MO);
Amult(N1, MO, N1);
iii++;
}
i+=iii;
Amult(Ans, N1, Ans);
printf("\nProgress is: %d",i);
pack(1, N1);
}
if(ff!=NULL){
fprintf(ff,"\n%d\n",i-1);
AEIfprintf(ff, Ans);
}
fclose(ff);
printf("\nProgress: 100\%");
return 0;
}
void AEIprintf(struct AEI *N1){
float fieldLength;
double temp;
char format1[8];
long j, FL0;
j = N1->digits-1;
FL0=(long)log10((float)base);
fieldLength = (float)log10((float)base);
temp = modf(fieldLength, &fieldLength);
format1[0] = ''%'';
format1[1] = ''0'';
format1[2] = fieldLength + 48;
format1[3] = ''d'';
format1[4] = 0x00;
printf("%*d", FL0, N1->data[j]);
j--;
while (j >= 0)
{
printf(format1, N1->data[j]);
j--;
}
return;
}
void AEIfprintf(FILE * fp, struct AEI *N1){
long j = N1->digits-1;
double fieldLength, temp;
char format0[8], format1[8];
fieldLength = (int)log10(base);
temp = modf(fieldLength, &fieldLength);
format0[0] = ''%'';
format0[1] = fieldLength + 48;
format0[2] = ''d'';
format0[3] = 0x00;
format1[0] = ''%'';
format1[1] = ''0'';
format1[2] = fieldLength + 48;
format1[3] = ''d'';
format1[4] = 0x00;
fprintf(fp,format0, N1->data[j]);
j--;
while (j >= 0){
fprintf(fp, format1, N1->data[j]);
j--;
}
return;
}
void pack(IntegerArrayType i, struct AEI * N1)
{
long t = 1, i1, j = 0;
while (t == 1){
i1 = i % base;
N1->data[j] = i1;
i = (i - i1) / base;
j++;
if (i == 0)
t = 0;
}
N1->digits=j;
return;
}
void Amult(struct AEI * A, struct AEI * B, struct AEI * C){
/*C = A * B; */
long i, ii,d, result, carry=0, digits=0;
struct AEI *Ans;
Ans=malloc(sizeof(struct AEI));
i=0;
d= (A->digits+B->digits-1);
while(i<d){
Ans->data[i]=carry;
carry=0;
ii=0;
while(ii<=i){
if(B->data[ii]!=0){
Ans->data[i]+=A->data[i-ii]*B->data[ii];
carry+=Ans->data[i]/base;
Ans->data[i]=Ans->data[i]%base;
}
ii++;
}
carry+=Ans->data[i]/base;
Ans->data[i]=Ans->data[i]%base;
i++;
}
if(carry!=0){
d++;
Ans->data[i]=carry;
}
C->digits=d;
i=0;
while(i<d){
C->data[i]=Ans->data[i];
i++;
}
return;
}
====================end paste============================
I tried to indent the code with spaces instead of tabs, but if some
parts end up not properly indented, I hope no one will hold it against
me.
Thanks ahead
推荐答案
fermineutron写道：
fermineutron wrote:
有一段时间我现在一直在玩用一个小C程序来计算
计算大数的阶乘。目前每1000次乘法每秒需要1 b / b
秒，即25000P1000需要大约
秒。对于50000P1000，预期会更长，因为答案中会有更多数字
。现在，在Num Analyses论坛/小组上有一个
的帖子，那个人在一秒钟内编写了计算1000000的java代码！
。这比我预期的要强约10000倍。我的代码可以做到这一点。所以两种可能性是：
1）我正在做一些非常错误的事情
2）其他人在说谎
At我倾向于相信其数字1的那一刻。
我在下面提出我的代码，我想听听你的意见
为什么它是慢，我怎么能改进它的速度。
For a while now i have been "playing" with a little C program to
compute the factorial of large numbers. Currently it takes aboy 1
second per 1000 multiplications, that is 25000P1000 will take about a
second. It will be longer for 50000P1000 as expected, since more digits
will be in the answer. Now, on the Num Analyses forum/Group there is a
post reaporting that that person wrot java code that computed 1000000!
in about a second. That is about 10000 times faste than I would expect
my code to do it. So the two possiblilities are:
1) I am doing something terribly wrong
2) The othr person is lying
At the moment i am inclined to believe that its number 1.
I am posing my code below, I would like to hear your opinions about
why it is slow and how i can improove its speed.
在有人评论代码之前，你有没有对它进行分析？
如果没有， 为什么不？如果你有，瓶颈在哪里？
-
Ian Collins。
Before anyone reviews the code, have you profiled it?
If not, why not? If you have, where were the bottlenecks?
--
Ian Collins.
fermineutron ：
fermineutron:
现在，在Num Analyzes论坛/小组上有一个
的帖子，那个人用来编写计算1000000的java代码！大约一秒钟的
。这比我预期的要强约10000倍。我的代码可以做到这一点。所以两种可能性是：
1）我做的事情非常糟糕
2）其他人在说谎
Now, on the Num Analyses forum/Group there is a
post reaporting that that person wrot java code that computed 1000000!
in about a second. That is about 10000 times faste than I would expect
my code to do it. So the two possiblilities are:
1) I am doing something terribly wrong
2) The othr person is lying
举证责任在于Java老兄。
概率表明他在说谎，因为只有很小比例的b / b
精通程序员把时间浪费在mickey-mouse hold-my-hand
语言上，比如Java。此外，Java很慢。
无论是那个还是算法'愚蠢的东西：
char const * Func（void）
{
return" 2349507239573258471257975093275092375093275923875 09" ;;
}
如果你问Java老兄可以看到他的代码。如果他拒绝，假设他是一个骗子，然后把他的房子打蛋。
-
Frederick Gotham
The burden of proof is on the Java dude.
Probability suggests that he''s lying, because only a very small proportion of
proficient programmers waste their time on mickey-mouse hold-my-hand
languages such as Java. Also, Java is slow.
Either that or the algorithm''s something stupid like:
char const *Func(void)
{
return "2349507239573258471257975093275092375093275923875 09";
}
Ask the Java dude if you can see his code. If he refuses, assume that he''s a
liar, then egg his house.
--
Frederick Gotham
Ian Collins写道：
Ian Collins wrote:
在任何人评论之前代码，您有没有对它进行分析？
如果没有，为什么不呢？如果你有，瓶颈在哪里？
Before anyone reviews the code, have you profiled it?
If not, why not? If you have, where were the bottlenecks?
我对它进行了分析，但是没有明显的瓶颈，我不希望b $ b预计会出现在设计中。
这里是探查器输出
http://igorpetrusky.awardspace.com/Temp/RunStats.html
我在想，也许还有其他的algorythm更好
比我的长期对象更好？
因子计算只是乘法函数的驱动因素。
I profilled it, but there were no obvious bottlenecks which i would not
anticipate to be there by design.
here is the profiler output
http://igorpetrusky.awardspace.com/Temp/RunStats.html
I was thinking that maybe there is some other algorythm that is better
than mine for the long int arithemetic?
Factorial calculation is just a driver for the multiplication function.
这篇关于长的速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
