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 & ...

Originally posted by huycwork at 2011-06-18 15:54:04:
你这个效率太低了，乘除次数太多，而且，性能似乎受大数算法拖累。我建议你用Perl评估下大数算法的性能，就我这边看，1000万次的迭代，use bigint和no use bigint差别有几秒之多。

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

Originally posted by holmescn at 2011-06-18 17:49:22:
这个大数算法有什么关系呢?'

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

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;
}

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

Originally posted by holmescn at 2011-06-18 18:19:07:
python那个大数算法版很快的啊, 比我后来这个算法快很多的. 应该是使用了gmp和mpfr这样的库的原因.

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

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

#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;
}

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 & ...

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 & ...