| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 8878 人关注过本帖, 1 人收藏
标题:挑战C版所有人,1000!
只看楼主 加入收藏
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 69楼 烟雨晨曦
答主有没有按照题主的要求执行1000的阶乘100次呢?我测试了下你的代码,执行1000次需要8秒多,比我代码慢21倍,这代码和7楼代码差不多,按10进制求的,未充分利用32位系统做乘法的优势。

回复 53楼 九转星河
题主题意是追求算法速度,不追求平台通用性,没考虑大端小端问题。再说真到做的应用有推广需求,什么大端小端都不是问题,完全没必要现在在这上面钻牛角尖。
这帖是挑战帖,我不好在这里发代码献丑的。我觉得题主有点耍赖,挑战至少要找个公正的第三方嘛,或者你发个编译好的exe,让人家根据在自己电脑上测试的速度来挑战嘛,就像刘翔跑出11.2,别人就天天练,跑出11秒才挑战一样,你什么都没有,别人也就只有和你一样耍嘴皮子了。
其实我知道这里还是有真大神的,像今天70楼闪过的beyondyf大侠,就是一个算法大神,以我不长的逛论坛历史,还没发现有敢和他叫板的,他通常能一针见血地指出他人代码的幼稚之处!
我把自己做实验的代码用短消息发给你,里面应该有你需要的超大16进制数10进制显示的函数,我还准备对其优化,提升显示速度。
2018-06-05 22:23
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4474
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 71楼 xzlxzlxzl
我支持你,挑战至少要找个公正的第三方嘛,或者你发个编译好的exe,让人家根据在自己电脑上测试的速度来挑战嘛

我就是真命天子,顺我者生,逆我者死!
2018-06-05 22:33
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 71楼 xzlxzlxzl
那个代码我试过了~用共用体处理的确比较快,直接赋值就可以了嗯,我也想不到什么好说的了,就先这样吧~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-06 12:39
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:35
帖 子:1103
专家分:3530
注 册:2011-12-3
收藏
得分:0 
回复 67楼 xzlxzlxzl
没看到代码
不过简单的分析一下
听起来是用共用体从内存上拆分进位
如果是这种思路用数组会比较合适
偶数元素保存本位数据 奇数元素保存进位 诸如此类
至少数组保证连续

另外 如果用其他进制作为计算 计算结果转换到十进制(不用输出 只是转换)也应该是这个算法的组成部分的

https://zh.
2018-06-06 13:50
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
以下是引用xzlxzlxzl在2018-6-5 06:36:05的发言:

怎么就结贴了?非常想学习题主@童生的算法,肯定他算法有先进之处,否则不会发挑战帖的!
最近拜读了很多做大数阶乘的帖子,发现算法都差不多,不是使用10000进制的,就是使用100000进制的。我比较贪心,使用1000000进制,这样的代码最多只能做到4200的阶乘,刚好满足题意。通过与所有类似代码对比,我的代码都比他们的快那么一点,由于算法相同,并没有质的变化,比如“https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai”里@Knocker大神的代码在我电脑上求10000!用时840毫秒,我的790毫秒(双方都运行10次的平均耗时),仅此而已。题主是在此基础上发挑战帖的,肯定算法有质的变化!
我此前也提到的用64位做,经过实验,无论是自始至终使用64位,还是大部分时间32位计算,有进位时使用64位取进位,都不行,运行100次1000!都超过了1000ms。后来我使用了现在这个算法,这个算用了共用体数据结构,运算过程中只需要做一次按位乘法,不再需要做除法和取余数运算,经测试运算100次1000!由515ms提高到375ms,提高了140毫秒,算是有质的飞跃了。但这个算法有一个缺点:它纯粹是16进制运算,运算结果是一个超大的16进制数,为了显示结果,我专门写了个内存超大16进制数10进制显示的函数,1000的阶乘的结果16进制只有2136位,显示起来速度还可以,但显示超过万位的16进制数耗时不少。

我刚刚用vc试过,用63楼的代码相比,你那个执行100次平均是200ms,我那个执行100次平均是143ms,执行1000次你那个平均是1860ms,我那个平均是860ms,但用手机试过的确是你那个代码比较快一点,应该是CPU不同程序对执行代码的处理方式不同有关吧,嗯,刚刚改了一下63楼那个,感觉还是63楼那个比较直接,当然实际来说方法是差不多的,或者你可以试试63楼那个在你那里运行看看情况如何,嗯,算是这样了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-07 12:14
童生
Rank: 6Rank: 6
等 级:侠之大者
威 望:8
帖 子:205
专家分:455
注 册:2018-3-7
收藏
得分:0 
以下是引用九转星河在2018-6-2 21:27:14的发言:

我也弄了个简单的出来不过得出的结果却是16进制的,如果要转换成10进制那么要把那个大数看作一个整体转换才行,没有验证结果,(或者结果是错误的),当然效率也不怎么样了,就是简单弄个看看而已~

还有一个小优化的方案,就是在内循环开始之前跳过前导0直接从非0位开始判断,n!统计0的个数这个好弄吧~
要想更高效的或者只能直接用FFT之类的算法减少乘法运算量了,算是这样了~


#include<stdio.h>

#define GET_LOW( s )    \
    ((s)&0x0000ffff)
        
#define GET_HIGH( s )    \
    (((s)&0xffff0000)>>16)

unsigned fun( unsigned[],unsigned );

void print( const unsigned[],unsigned );

int main( void )
{
   unsigned a[3000];

   print(a,fun(a,1001));
        
    return 0;
}

unsigned fun( unsigned a[],unsigned len )
{
    unsigned i;
    unsigned j;
    unsigned count=3;
        
    a[1]=1;
    a[0]=0;
    a[2]=0;
 
    for (i=1;i!=len;++i)
    {
        for (j=1;j!=count;++j)
            a[j]=GET_LOW(a[j])*i+GET_HIGH(a[j-1]);
        
        if (GET_HIGH(a[count-1]))
        {
            a[count++]=0;
        }
    }
   
    return count;
           
}

void print( const unsigned a[],unsigned len)
{
    while (--len)
        printf("%04x",GET_LOW(a[len]));
        
    puts("");
}

历害!比我快了
2018-06-07 16:53
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
以下是引用童生在2018-6-7 16:53:54的发言:


历害!比我快了


哪里哪里,我没有转换成10进制,转换后还不一定呢~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-07 17:15
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 75楼 九转星河
没有看你的代码,刚刚测试了下,的确比我的快,在我电脑上做100次1000!只需要140毫秒,比我的整整快230毫秒,这已经不是一个数量级了。测试图如下:

图片附件: 游客没有浏览图片的权限,请 登录注册


通过分析你的代码,发现你是通过右移运算获得进位的,这从理论上说不过去,直接赋值肯定要比运算得到值的速度快。于是我对你的计算结果产生了怀疑,通过分析可知,你是使用int数据低2字节作为有效数据的,应该数据长度和我short int数据长度一样,从上图可以看出,你只用了414个int数据,而我用了534个数据(参见我在67楼第一幅图片),我的验证结果是正确的,显然你的414个数据无法表示1000!的结果,从估算上也无法表示,一般2个字节的数据概率上能表示4.5位十进制数,我姑且能表示5位十进制,满打满算414*5=2070,和1000!的实际位数2568相差甚远。
我决定简单检测你10至20的阶乘的正确性,我先对你的main代码和print代码做如下修改(你检查下这样修改应该没问题吧):

int main( void )
{
    int i,j,k,l,t;
    unsigned a[3000];
    t=clock();
    for(i=10;i<21;i++)
    {
        l=fun(a,i+1);
        printf("计算%d!,长度%d\n",i,l);
        print(a,l);
    }
   
    return 0;
}

void print( const unsigned a[],unsigned len)
{
    while (--len)
        printf("%p,",GET_LOW(a[len]));
   
    puts("");
}

最后通过使用微软计算器验算相应阶乘十六进制结果,发现10!、11!、12!的结果没问题,从13后结果都是错误的,验算图片见下图,你也可以自己验算下!

图片附件: 游客没有浏览图片的权限,请 登录注册


2018-06-07 18:07
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 78楼 xzlxzlxzl
之前说了可能有错,我就算到12!,13!或者已经超过int就没有验证了,嗯,看看怎么把代码弄正确,难怪说比楼主还快~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-07 21:29
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
PS: 对比过代码了,原来就是最高位没有加上进位用0表示,所以下次进位的时候就覆盖了,嗯,现在改了一下,应该是这样了,还是在170~180ms左右,还是快了那么一点点算是这样了~

程序代码:
#include<stdio.h>
#include<time.h>

#define GET_LOW( s )    \
    ((s)&0x0000ffff)
        
#define GET_HIGH( s )    \
    (((s)&0xffff0000)>>16)

unsigned fun( unsigned[],unsigned );

void print( const unsigned[],unsigned );

int main( void )
{
   unsigned a[3000];
   unsigned count;
   unsigned i;

   time_t t=clock();

   for (i=0;i!=100;++i)
       count=fun(a,1001);

   print(a,count);

   printf("用时%ldms\n",clock()-t);
        
    return 0;
}

unsigned fun( unsigned a[],unsigned len )
{
    unsigned i;
    unsigned j;
    unsigned count=3;
        
    a[1]=1;
    a[0]=0;
    a[2]=0;

 
    for (i=1;i!=len;++i)
    {
        for (j=1;j!=count;++j) 
            a[j]=GET_LOW(a[j])*i+GET_HIGH(a[j-1]);
        
        if (GET_HIGH(a[count-1]))
            a[count++]=GET_HIGH(a[j-1]);
    }
    
    return count;
}

void print( const unsigned a[],unsigned len)
{
    while (--len)
        printf("%04x",GET_LOW(a[len]));
        
    puts("");
}


[此贴子已经被作者于2018-6-7 23:13编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-07 21:55
快速回复:挑战C版所有人,1000!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.060702 second(s), 9 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved