优化c代码计算pi
Optimize c code to calculate pi
我已经编写了 C 代码来计算 https://github.com/gongchengra/hacker/blob/master/c/16_pi.c
上的 pi
无注释代码如下:
#include <stdio.h>
#define NUMBER 100000
int array_divide_number(int *array, int number, int size)
{
int i,tmp;
int modulo=0;
for(i=0;i<size;i++)
{
tmp = array[i]+modulo*10;
array[i] = tmp/number;
modulo = tmp%number;
}
return 0;
}
void print_array(int *array, int size)
{
int i,last;
for(last=size-1;last>=0;last--)
{
if(array[last] != 0)
{
break;
}
}
for(i=0;i<=last;i++)
{
printf("%d",array[i]);
}
printf("\n");
}
void copy_array(int *source, int *target, int size)
{
int i;
for(i=0;i<size;i++)
{
target[i] = source[i];
}
}
void plus_array(int *augend, int *addend, int *sum, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
sum[i] = augend[i] + addend[i];
if(sum[i]>9)
{
sum[i] = sum[i] % 10;
sum[i-1]++;
}
}
}
void minus_array(int *minuend, int *subtracter, int *answer, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
if(minuend[i] >= subtracter[i] || i == 0)
{
answer[i] = minuend[i] - subtracter[i];
}
else
{
if(minuend[i-1] == 0)
{
minuend[i-2]--;
minuend[i-1] = 10;
}
minuend[i-1]--;
answer[i] = 10 + minuend[i] - subtracter[i];
}
}
}
int main()
{
int i;
int flag=1;
int d5[NUMBER]={0};
int t5[NUMBER]={0};
int d239[NUMBER]={0};
int t239[NUMBER]={0};
int pi[NUMBER]={0};
d5[0]=16;
d239[0]=4;
array_divide_number(d5,5,NUMBER);
array_divide_number(d239,239,NUMBER);
//every iteration will increase three valid digitals
for(i=1;i<NUMBER*3/2;i+=2)
{
copy_array(d5, t5, NUMBER);
copy_array(d239, t239, NUMBER);
array_divide_number(t5,i,NUMBER);
array_divide_number(t239,i,NUMBER);
if(flag > 0)
{
plus_array(pi,t5,pi,NUMBER);
minus_array(pi,t239,pi,NUMBER);
}
else
{
minus_array(pi,t5,pi,NUMBER);
plus_array(pi,t239,pi,NUMBER);
}
flag = -1*flag;
array_divide_number(d5,5*5,NUMBER);
array_divide_number(d239,239*239,NUMBER);
}
print_array(pi, NUMBER);
return 0;
}
有效,但耗时太长:
$time ./16_pi.exe >pi3.log
./16_pi.exe > pi3.log 617.76s user 0.15s system 98% cpu 10:27.94 total
可以看到,为了计算pi
的100000位数字,需要10多分钟。
有没有办法在不改变计算pi
的算法的情况下优化代码(这里使用的算法是pi=(16/5-4/239)-1/3*(16/5^3-4/ 239^3)+1/5*(16/5^5-4/239^5)+...)
优化代码是以某种方式改变算法(即使公式相同)。
你正在做一些 bignum arithmetic. Bignum algorithms are hard and clever. You should use a bignum library like GMPlib(这可能也受益于特殊的进位传播机器指令;主要收获是聪明的 bignum 算术算法),它可能应该 运行 比你天真的 bignum 快套路。
当然,在benchmarking的时候不要忘记让编译器优化(例如gcc -O3 -Wall -mtune=native
)
FWIW,另见 Fabrice Bellard's page about Pi. And GMP has a page with code about Pi:计算 100,000 位数字只需要几分之一秒。
我已经编写了 C 代码来计算 https://github.com/gongchengra/hacker/blob/master/c/16_pi.c
上的pi
无注释代码如下:
#include <stdio.h>
#define NUMBER 100000
int array_divide_number(int *array, int number, int size)
{
int i,tmp;
int modulo=0;
for(i=0;i<size;i++)
{
tmp = array[i]+modulo*10;
array[i] = tmp/number;
modulo = tmp%number;
}
return 0;
}
void print_array(int *array, int size)
{
int i,last;
for(last=size-1;last>=0;last--)
{
if(array[last] != 0)
{
break;
}
}
for(i=0;i<=last;i++)
{
printf("%d",array[i]);
}
printf("\n");
}
void copy_array(int *source, int *target, int size)
{
int i;
for(i=0;i<size;i++)
{
target[i] = source[i];
}
}
void plus_array(int *augend, int *addend, int *sum, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
sum[i] = augend[i] + addend[i];
if(sum[i]>9)
{
sum[i] = sum[i] % 10;
sum[i-1]++;
}
}
}
void minus_array(int *minuend, int *subtracter, int *answer, int size)
{
int i;
for(i=size-1;i>=0;i--)
{
if(minuend[i] >= subtracter[i] || i == 0)
{
answer[i] = minuend[i] - subtracter[i];
}
else
{
if(minuend[i-1] == 0)
{
minuend[i-2]--;
minuend[i-1] = 10;
}
minuend[i-1]--;
answer[i] = 10 + minuend[i] - subtracter[i];
}
}
}
int main()
{
int i;
int flag=1;
int d5[NUMBER]={0};
int t5[NUMBER]={0};
int d239[NUMBER]={0};
int t239[NUMBER]={0};
int pi[NUMBER]={0};
d5[0]=16;
d239[0]=4;
array_divide_number(d5,5,NUMBER);
array_divide_number(d239,239,NUMBER);
//every iteration will increase three valid digitals
for(i=1;i<NUMBER*3/2;i+=2)
{
copy_array(d5, t5, NUMBER);
copy_array(d239, t239, NUMBER);
array_divide_number(t5,i,NUMBER);
array_divide_number(t239,i,NUMBER);
if(flag > 0)
{
plus_array(pi,t5,pi,NUMBER);
minus_array(pi,t239,pi,NUMBER);
}
else
{
minus_array(pi,t5,pi,NUMBER);
plus_array(pi,t239,pi,NUMBER);
}
flag = -1*flag;
array_divide_number(d5,5*5,NUMBER);
array_divide_number(d239,239*239,NUMBER);
}
print_array(pi, NUMBER);
return 0;
}
有效,但耗时太长:
$time ./16_pi.exe >pi3.log
./16_pi.exe > pi3.log 617.76s user 0.15s system 98% cpu 10:27.94 total
可以看到,为了计算pi
的100000位数字,需要10多分钟。
有没有办法在不改变计算pi
的算法的情况下优化代码(这里使用的算法是pi=(16/5-4/239)-1/3*(16/5^3-4/ 239^3)+1/5*(16/5^5-4/239^5)+...)
优化代码是以某种方式改变算法(即使公式相同)。
你正在做一些 bignum arithmetic. Bignum algorithms are hard and clever. You should use a bignum library like GMPlib(这可能也受益于特殊的进位传播机器指令;主要收获是聪明的 bignum 算术算法),它可能应该 运行 比你天真的 bignum 快套路。
当然,在benchmarking的时候不要忘记让编译器优化(例如gcc -O3 -Wall -mtune=native
)
FWIW,另见 Fabrice Bellard's page about Pi. And GMP has a page with code about Pi:计算 100,000 位数字只需要几分之一秒。