7

私は最近、大きな整数の階乗アルゴリズムを検討することにしました。この「分割統治」アルゴリズムは、単純な反復アプローチや素数分解アプローチよりも高速です。

def multiply_range(n, m):
    print n, m
    if n == m:
        return n
    if m < n:
        return 1
    else:
        return multiply_range(n, (n+m)/2) * multiply_range((n+m)/2+1, m)

def factorial(n):
    return multiply_range(1, n)

アルゴリズムが機能する理由を理解しています。それは、乗算を再帰的に小さな部分に分割するだけです。私が理解していないのは、なぜこの方法が速いのかということです。

4

2 に答える 2

7

@NPEの答えに反して、あなたの方法は非常に大きな数に対してのみより速くなります。私にとっては、分割統治法が入力〜10^4でより速くなるのを見始めました。10 ^ 6以上では、従来のループが無残に失敗する比較はありません。

私はハードウェア乗算器の専門家ではないので、誰かがこれを拡張できることを願っていますが、私の理解では、乗算は小学校で教えられているのと同じように桁ごとに行われます。

従来の階乗ループは少数から始まり、結果は増え続けます。結局、あなたは比較的小さな数で巨大な数を多重化しています、これは数字の不一致のために高価な計算です。

元。比較

reduce(operator.mul, range(1,10**5))
reduce(operator.mul, range(10**5,1,-1))

2つ目は、結果が速く成長するため遅くなり、計算コストが高くなります。

あなたの方法は、階乗を同じサイズの部分に分割するため、これらのいずれよりも大きな数の場合は桁違いに高速です。サブ結果の桁数は同じで、乗算が速くなります。

于 2012-12-01T16:01:44.743 に答える
3

簡単な答えは、あなたが間違っているということです。それほど速くはありません：

In [34]: %timeit factorial(100)
10000 loops, best of 3: 57.6 us per loop

In [35]: %timeit reduce(operator.mul, range(1, 101))
100000 loops, best of 3: 19.9 us per loop

言い換えれば、それは単純なワンライナーよりも約3倍遅いです。

値が小さい場合n、差はさらに劇的になります。

于 2012-12-01T07:11:02.410 に答える