论坛 › 编程擂台 › Ten digit numbers

mathe 发表于 2009-1-13 08:47:18

那我算41－60吧。呵呵，我就用一台奔腾四

mathe 发表于 2009-1-13 08:48:40

批量计算还是用我的那个方法比较好。比如你要计算31-40，那么对每个数先用幂运算算出31，然后每次再乘一个。
而不是算完所有数的31次在算32次

无心人 发表于 2009-1-13 08:51:57

能节约多少时间？

无心人 发表于 2009-1-13 08:52:31

不过对每个幂， 其起始数字都不一样啊

mathe 发表于 2009-1-13 08:55:56

看一下我的程序，其实方法很简单，就是对每个整数，计算它的最后一个幂就可以了。（如果某个整数，最后一个幂是h,那么所有比这个数小的，这个幂也不需要算了）

无心人 发表于 2009-1-13 08:57:28

知道了

你们都倒着来

mathe 发表于 2009-1-13 08:57:59

原帖由 无心人 于 2009-1-13 08:51 发表 http://bbs.emath.ac.cn/images/common/back.gif
能节约多少时间？
大部分幂运算都可以仅仅用一次乘法运算代替了，这部分时间可以节省。但是数字转化为10进制统计各位数字部分就不能节省了。具体节省多少时间要看两部分计算的比例。如果幂运算占大头，那么节省的运算量会非常客观。

无心人 发表于 2009-1-13 09:11:05

乘以10位数
如果是64位机器
就简单了

可惜我的服务器内存低
不敢装64位
如果是2G或者4G我就装64位

无心人 发表于 2009-1-13 09:13:04

你连续算20个幂
每亿数字消耗的时间是？

我这里似乎一个数字的时间在31后
大大增加了
原来估计20分，现在估计60分打不住

gxqcn 发表于 2009-1-13 10:04:09

优化后的代码

改自 33# mathe 的代码：#include < stdio.h >
#include < time.h >
#include < HugeCalc.h >
#include < HugeInt.h >

#pragma comment( lib, "HugeCalc.lib" )

#define integer CHugeInt


#define MIN_EXP    9
#define MAX_EXP    10

int cc = { 0 };

void test()
{
    time_t t=time(NULL);
    integer x("10000000002"), z;
    int i, j, d;
    int mt=MAX_EXP, c=33334;
    int count;
    int digits;
    LPCTSTR p;

    while( !(!( x-=3 )) )
    {
      z.Pow( x, MIN_EXP-1 );
      for(i=MIN_EXP,d=i*10; i<=mt; i++,d+=10)
      {
            z*=x;

            digits = z.GetDigits();
            if ( digits == d )
            {
                count['\0']=1;
                for(j='0';j<='9';j++)count=i+1;

                for( p=z; 0!=--count[*p]; ++p)
                  ;

                if ( '\0' == *p )
                {
                  printf("\nNo.%u\t%s^%d=%s\n\n", ++cc, (LPCTSTR)x, i, p-d);
                  fflush(stdout);
                }
            }
            else if( digits < d )
            {
                mt=i-1;
                if(mt<MIN_EXP)
                {
                  printf("Total cost %dseconds\n", time(NULL)-t);
                  return;
                }

                break;
            }
      }

      if( 0==--c )
      {
            fprintf(stderr,"\t%s, times %ds\n", (LPCTSTR)x, time(NULL)-t);
            c = 300000;
      }
    }
}

int main(int argc, char* argv[])
{
    int i;
    test();
    for(i=MIN_EXP;i<=MAX_EXP;i++){
      printf("c[%d]=%d\n",i,cc);
    }
    return 0;
}

查看完整版本: Ten digit numbers