优化bigint调用

我目前正在使用"在D中编程"一书来学习D.我试图解决从1到10000000之间总结数字平方的问题.我首先提出了一个函数方法来解决地图问题并减少但是as数字越大我必须将数字转换为bigint以获得正确的输出.

  long num = 10000001;
  BigInt result;
  result = iota(1,num).map!(a => to!BigInt(a * a)).reduce!((a,b) => (a + b));
  writeln("The sum is : ", result);

使用dmd -O编译时,上面需要7秒才能完成.我描述了该程序,大部分时间都浪费在BigInt调用上.虽然数字的平方可以适合很长,但我必须将它们强制转换为bigint,以便减少函数总和并返回适当的总和.python程序只需3秒即可完成.当num = 100000000 D程序达到1分13秒时完成.有没有办法优化对bigint的调用.产品本身可能很长,但必须将它们作为bigint对象进行类型转换,以便它们能够通过减少操作来获得正确的结果.我尝试将数字的平方推入bigint数组,但速度也较慢.我试图将所有数字强制转换为Bigint

auto bigs_map_nums = iota(1,num).map!(a => to!BigInt(a)).array;
auto bigs_map = sum(bigs_map_nums.map!(a => (a * a)).array);

但它也慢了.我阅读了如何在scala中优化这个短因子函数的答案？(创建50000 BigInts).对于D中更大整数的乘法实现是否存在问题？有没有办法优化对BigInt的函数调用？

python代码:

timeit.timeit('print sum(map(lambda num : num * num, range(1,10000000)))',number=1)
333333283333335000000
3.58552622795105

该代码在具有2 GB RAM的双核64位Linux笔记本电脑上执行.python:2.7.4 dmd:DMD64 D编译器v2.066.1

没有范围凉爽: foreach(x; 0 .. num) result += x * x;

范围酷(？)ness:

import std.functional: reverseArgs;
result = iota(1, num)
    .map!(a => a * a)
    .reverseArgs!(reduce!((a, b) => a + b))(BigInt(0) /* seed */);

关键是要避免BigInt每一个元素,当然.

范围版本比非范围版本慢一点.两者都比python版本快得多.

编辑:哦!哦! 它可以变得更加愉快std.algorithm.sum:

result = iota(1, num)
    .map!(a => a * a)
    .sum(BigInt(0));

python代码不等同于D代码,实际上它的功能要少得多.

Python使用int,然后当结果大于int()类型中存储的结果时,它将int提升为long().在内部,(至少CPython)使用长数来存储大于256的整数,这至少是32位.直到溢出正常的cpu指令可用于乘法,这比bigint乘法快得多.

D的BigInt实现从一开始就将数字视为BigInt,并使用从1开始到结束的昂贵的乘法运算.还有很多工作要做.

有趣的是,当我们谈论BigInts时,乘法是多么复杂.

D实现是

https://github.com/D-Programming-Language/phobos/blob/v2.066.1/std/internal/math/biguintcore.d#L1246

Python开始做

static PyObject *
int_mul(PyObject *v, PyObject *w)
{
    long a, b;
    long longprod;                      /* a*b in native long arithmetic */
    double doubled_longprod;            /* (double)longprod */
    double doubleprod;                  /* (double)a * (double)b */

    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    /* casts in the next line avoid undefined behaviour on overflow */
    lOngprod= (long)((unsigned long)a * b);

    ... //check if we have overflowed


    {
        const double diff = doubled_longprod - doubleprod;
        const double absdiff = diff >= 0.0 ? diff : -diff;
        const double absprod = doubleprod >= 0.0 ? doubleprod :
                              -doubleprod;
        /* absdiff/absprod <= 1/32 iff
           32 * absdiff <= absprod -- 5 good bits is "close enough" */
        if (32.0 * absdiff <= absprod)
            return PyInt_FromLong(longprod);
        else
            return PyLong_Type.tp_as_number->nb_multiply(v, w);
    }
}