24小时热门版块排行榜    

查看: 2029  |  回复: 30

huycwork

金虫 (著名写手)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
微尘、梦想(金币+2): 鼓励交流! 2011-06-19 17:18:47
引用回帖:
Originally posted by holmescn at 2011-06-18 10:23:25:
OK, 完成 Python版的质数分解法, 不过不是很快,大概要3秒左右吧
[code]
# coding: utf-8

factorsOfA = []

for a in xrange(2, 101):
    u = 2
    n = 0
    x = a
    factors = []
    while u & ...

你这个效率太低了,乘除次数太多,而且,性能似乎受大数算法拖累。我建议你用Perl评估下大数算法的性能,就我这边看,1000万次的迭代,use bigint和no use bigint差别有几秒之多。

另外,建议你看看这个算法:http://zh.wikipedia.org/wiki/%E5 ... C%E7%AD%9B%E6%B3%95
漩涡的中心有一块空地,空空的。
11楼2011-06-18 15:54:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)

★ ★
微尘、梦想(金币+2): 鼓励交流! 2011-06-19 17:19:09
引用回帖:
Originally posted by huycwork at 2011-06-18 15:54:04:
你这个效率太低了,乘除次数太多,而且,性能似乎受大数算法拖累。我建议你用Perl评估下大数算法的性能,就我这边看,1000万次的迭代,use bigint和no use bigint差别有几秒之多。

另外,建议你看看这个算法 ...

这个大数算法有什么关系呢?'

当然,我可以先筛出小于100的质数. 然后再把2到100这些数做分解. 不过,我觉得这个算法的瓶颈不在这里. 那个分解过程用不了1秒. 主要是下面怎么做指数乘法, 并用什么方法做比较. 这个地方我用了太多的转换, 所以慢了.

[ Last edited by holmescn on 2011-6-18 at 18:07 ]
12楼2011-06-18 17:49:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
微尘、梦想(金币+2): 鼓励交流! 2011-06-19 17:19:27
引用回帖:
Originally posted by holmescn at 2011-06-18 17:49:22:
这个大数算法有什么关系呢?'

当然,我可以先筛出小于100的质数. 然后再把2到100这些数做分解. 不过,我觉得这个算法的瓶颈不在这里. 那个分解过程用不了1秒. 主要是下面怎么做指数乘法, 并用什么方法做比较 ...

电路板实现的乘除算的是定点数,计算时间接近常数,但目前实现大数算法时多半都用用循环实现的,像加法的大数算法,二进制的补码实现看起来像这样:
CODE:
int add(int bs1, int bs2){
        int t, ac = bs2;
        t = bs1 & ac;
        bs1 ^= ac;
        while(t){
                t <<= 1;
                ac = t;
                t = bs1 & ac;
                bs1 ^= ac;
        }
        return bs1;
}

乘法更复杂,仿照竖式运算复杂度会达到n*n,跟电路板的效率根本没法拼,不能随便祭出大数算法的呃~

[ Last edited by huycwork on 2011-6-18 at 18:18 ]
漩涡的中心有一块空地,空空的。
13楼2011-06-18 18:14:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)

刚测了一下, 整个算法平均用时1.5秒, 分解只用了千分之1.5秒. 所以, 不是主要矛盾,不用优化.
14楼2011-06-18 18:15:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)

引用回帖:
Originally posted by huycwork at 2011-06-18 18:14:07:
电路板实现的乘除算的是定点数,计算时间接近常数,但目前实现大数算法时多半都用用循环实现的,像加法的大数算法,二进制的补码实现看起来像这样:
[code]
int add(int bs1, int bs2){
        int t, ac = bs ...

python那个大数算法版很快的啊, 比我后来这个算法快很多的. 应该是使用了gmp和mpfr这样的库的原因.

大数乘法有算法的, 不用做竖式那样的乘. arXiv上应该有文献.
15楼2011-06-18 18:19:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)


小木虫(金币+0.5):给个红包,谢谢回帖
引用回帖:
Originally posted by holmescn at 2011-06-18 18:19:07:
python那个大数算法版很快的啊, 比我后来这个算法快很多的. 应该是使用了gmp和mpfr这样的库的原因.

大数乘法有算法的, 不用做竖式那样的乘. arXiv上应该有文献.

仿竖式的话其实就是多项式算法嘛,即使优化过也在n~n*n之间,不管怎么看也很浪费了,相比于GPU而言。
如果这么确定,后面除了join之外也没看出来什么耗时的操作了,还有一个麻烦可能是数组的合并操作,append那里。
漩涡的中心有一块空地,空空的。
16楼2011-06-18 18:36:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)

引用回帖:
Originally posted by huycwork at 2011-06-18 18:36:01:
仿竖式的话其实就是多项式算法嘛,即使优化过也在n~n*n之间,不管怎么看也很浪费了,相比于GPU而言。
如果这么确定,后面除了join之外也没看出来什么耗时的操作了,还有一个麻烦可能是数组的合并操作,append ...

这里转换成字符串和用字符串做比较可能是有点低效, 特别是那个 not in, 可能是问题的关键, 不过没有做profile, 这个算法在不做大数运算的情况下,还算一般吧。 改成C的可能就快了。一些分配内存的动作也耗时
17楼2011-06-18 22:09:29
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)

★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
微尘、梦想(金币+4): 鼓励交流! 2011-06-19 17:20:02
嗯,里面的magic number都是可以手工算出来的(不是我瞒天过海哦),计算过程和意义省略了...让大家猜猜看吧

原理类似因子分解,嗯
CODE:
#include

int tag[101];

int main(){
    int dup[7] = {0, 0, 49, 98, 156, 204, 266};
    int i, j, t;
    int count = 99*99;

    for(i=2; i<=10; i++){
        if(tag[i]) continue;
        for(t=0, j=i; j<=100; j*=i){
            tag[j] = 1;
            t++;
        }
        count -= dup[t];
    }

    printf("%d\n", count);

    return 0;
}

[ Last edited by sudo on 2011-6-19 at 09:01 ]
18楼2011-06-18 23:00:09
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qinghuoly

木虫 (正式写手)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
微尘、梦想(金币+2): 鼓励交流,欢迎常来程序语言版! 2011-06-19 17:20:36
引用回帖:
Originally posted by holmescn at 2011-06-18 10:23:25:
OK, 完成 Python版的质数分解法, 不过不是很快,大概要3秒左右吧
[code]
# coding: utf-8

factorsOfA = []

for a in xrange(2, 101):
    u = 2
    n = 0
    x = a
    factors = []
    while u & ...

J语言啊,APL语言的替代版。

代码简洁精炼,够cool。话说欧拉工程上好多题目都有相应的J语言解法。
天地为帐,日月为灯,风雷为号角,云虹为旗令,山川为阵图,草木为兵卒。运阴阳五行为谋,策古今兴替为略。
19楼2011-06-19 00:18:03
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qinghuoly

木虫 (正式写手)


小木虫(金币+0.5):给个红包,谢谢回帖
引用回帖:
Originally posted by holmescn at 2011-06-18 10:23:25:
OK, 完成 Python版的质数分解法, 不过不是很快,大概要3秒左右吧
[code]
# coding: utf-8

factorsOfA = []

for a in xrange(2, 101):
    u = 2
    n = 0
    x = a
    factors = []
    while u & ...

J语言啊,APL语言的替代版。

代码简洁精炼,够cool。话说欧拉工程上好多题目都有相应的J语言解法。
天地为帐,日月为灯,风雷为号角,云虹为旗令,山川为阵图,草木为兵卒。运阴阳五行为谋,策古今兴替为略。
20楼2011-06-19 00:26:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
普通表情 高级回复 (可上传附件)
信息提示
请填处理意见