源程序来自pe论坛。是求farey数列的。我把原来的long double修改成long long和double两个版本 long long

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define gr 1.6180339887498948482  //Golden ratio
typedef long long ll;

int main() {
   ll total=0,maxp = 2.5*pow(10,9);
   ll mt=1,nt=1,m2=1,n1=1,n2=1,h,d,m1=0;;
   printf("\n\n Perimeter:%15.1lld\n",maxp);
   d= floor(sqrt(maxp/3));    // Calculate the order of the Farey Seqence

   while ((double)m2/n2 <= gr ) {
     total= total+floor(maxp/((m2+n2)*(m2+n2)-m2*n2));
     h= floor((n1+d)/n2);  // Generate next Farey sequence m2/n2
     mt= h * m2 - m1;
     nt= h * n2 - n1;
     n1=n2;
     n2=nt;
     m1=m2;
     m2=mt;
   }

   printf(" Triangles found: %15.lld \n",total);
   return(0);
}

double

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define gr 1.6180339887498948482  //Golden ratio

int main() {
   double total=0,maxp = 2.5*pow(10,9);
   double mt=1,nt=1,m2=1,n1=1,n2=1,h,d,m1=0;;
   printf("\n\n Perimeter:%15.1le\n",maxp);
   d= floor(sqrt(maxp/3));    // Calculate the order of the Farey Seqence

   while (m2/n2 <= gr ) {
     total= total+floor(maxp/((m2+n2)*(m2+n2)-m2*n2));
     h= floor((n1+d)/n2);  // Generate next Farey sequence m2/n2
     mt= h * m2 - m1;
     nt= h * n2 - n1;
     n1=n2;
     n2=nt;
     m1=m2;
     m2=mt;
   }

   printf(" Triangles found: %15.lf \n",total);
   return(0);
}

结果 long long的21秒,double的15秒。 又看了一下,在long long版本中不需要调用取整函数floor,否则还多出来类型转换,去掉floor后就变成了5秒。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define gr 1.6180339887498948482  //Golden ratio
typedef long long ll;

int main() {
   ll total=0,maxp = 2.5*pow(10,9);
   ll mt=1,nt=1,m2=1,n1=1,n2=1,h,d,m1=0;;
   printf("\n\n Perimeter:%15.1lld\n",maxp);
   d= floor(sqrt(maxp/3));    // Calculate the order of the Farey Seqence

   while ((double)m2/n2 <= gr ) {
     total= total+(maxp/((m2+n2)*(m2+n2)-m2*n2));
     h= ((n1+d)/n2);  // Generate next Farey sequence m2/n2
     mt= h * m2 - m1;
     nt= h * n2 - n1;
     n1=n2;
     n2=nt;
     m1=m2;
     m2=mt;
   }

   printf(" Triangles found: %15.lld \n",total);
   return(0);
}

再把中间一些变量改为int,又变成了3秒。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define gr 1.6180339887498948482  //Golden ratio
typedef long long ll;

int main() {
   ll total=0,maxp = 2.5*pow(10,9);
   int mt=1,nt=1,m2=1,n1=1,n2=1,h,d,m1=0;;
   printf("\n\n Perimeter:%15.1lld\n",maxp);
   d= floor(sqrt(maxp/3));    // Calculate the order of the Farey Seqence

   while ((double)m2/n2 <= gr ) {
     total= total+(maxp/(ll(m2+n2)*ll(m2+n2)-ll(m2)*n2));
     h= ((n1+d)/n2);  // Generate next Farey sequence m2/n2
     mt= h * m2 - m1;
     nt= h * n2 - n1;
     n1=n2;
     n2=nt;
     m1=m2;
     m2=mt;
   }

   printf(" Triangles found: %15.lld \n",total);
   return(0);
}

评论

推荐 0
http://www.ituring.com.cn/article/274275
long long改为int也有类似效果

推荐 0
在x64 linux上 也有类似的结果


推荐 0
int 类型,一个字长,应该最快了……

我要评论

需要登录后才能发言
登录未成功,请修改提交。