优化 bigint 调用

Question

我目前正在使用 'Programming in D' 这本书来学习 D。我试图解决一个从 1 到 10000000 的数字的平方求和的问题。我首先使用函数方法来解决这个问题map 和 reduce 但随着数字变大，我必须将数字转换为 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 调用上。尽管数字的平方可以放入一个 long 中，但我必须将它们转换为 bigint，以便减少函数总和和 returns 适当的总和。 python 程序只需 3 秒即可完成。当 num = 100000000 时，D 程序需要 1 分 13 秒才能完成。有没有办法优化对 bigint 的调用。产品本身可以很长，但必须将它们类型转换为 bigint 对象，以便它们从 reduce 操作中给出正确的结果。我尝试将数字的平方推入 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);

但它也更慢。我在 How to optimize this short factorial function in scala? (Creating 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

Answer 1

DMD 的后端不会发出高度优化的代码。对于快速程序，使用 GDC 或 LDC 编译。

在我的电脑上，我得到这些时间：

Python:                    3.01
dmd   -O -inline -release: 3.92
ldmd2 -O -inline -release: 2.14

Answer 2

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

范围酷（？）度：

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

当然，关键是要避免 BigInting 每个元素。

量程版本比非量程版本慢一点。两者都比 python 版本快得多。

编辑：哦！哦！使用 std.algorithm.sum:

可以使它变得更加愉快

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

Answer 3

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

如果数字大于 long 可以容纳的数字，它会执行 karatsuba 乘法。实施时间：

http://svn.python.org/projects/python/trunk/Objects/longobject.c（k_mul 函数）

等效代码将等待使用 BigInts，直到它们不是可以容纳相关数字的本机数据类型。

优化 bigint 调用

Optimizing bigint calls

python

optimization

d