Sum（i ... j） - これにはより効率的な/エレガントなソリューションがありますか？

Question

わかりやすい式を使用せずに、それぞれ再帰と反復を使用して開始点と終了点の間のすべての数値（ 'from'と 'to'）を合計する最も効率的な方法を思いつく簡単なタスクが与えられました。 O（1）になります。

このためのアプリケーションがありませんが、私は単に好奇心と私の解決策は、それがすでにあるよりも多くの研磨/改善することができるかどうかを確認するために挑戦：

/* recursion */ 
unsigned int sum1(unsigned int from, unsigned int to) { 
    if (to - from < 2) 
     return from + (from == to ? 0 : to); 
    else 
     return from + to + sum1(from + 1, to - 1); 
} 

/* iteration */ 
unsigned int sum2(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int i, s, n = p/2; 
    if (p % 2 == 0) s = n + from; 
    else { 
     s = 0; 
     n++; 
    } 
    for (i = 0; i < n; i++) { 
     s += from++ + to--; 
    } 
    return s; 
} 

Answer 1

私は、反復バージョンの改善を試みた：

を

unsigned int sum2_improved(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int x = to + from; 
    int s = 0; 
    int i; 
    for (i = p >> 1; i > 0; i--) 
    { 
     s += x; 
    } 
    s += (p % 2 == 0) ? x >> 1 : x; 
    return s; 
} 

私はあなたのバージョンをテストした：これは私が見たものである

for (i = 0; i < 9999999; i++) sum2(1,999); 

：

$ time ./addm 
real 0m18.315s 
user 0m18.220s 
sys  0m0.015s 

同じループ数で実装しようとしましたが、ここでは改善された機能が実行方法は次のとおりです。

$ time ./addm 
real 0m14.196s 
user 0m14.070s 
sys  0m0.015s 

---

UPDATE私の実装x = to + fromで

される第一およびシーケンスの最後の数の合計が。連続した整数のシーケンスを考えて、最初と最後、2番目と最後から2番目などを合計すると、これらはすべて同じ値になります。たとえば、(1 ... 6), 1 + 6 = 2 + 5 = 3 + 4 = 7です。しかし、奇数個の要素を含むシーケンスでは、中間の番号が残っています。これを累積合計に加算する必要があります（forループの後の代入が実行していたものです）。

また、まだO(n)である私が最初に私のアプローチは、実際に一定の時間で行うことができます私の答えを掲示した後、私は実現ここで更新されたコードがあります：。。

unsigned int sum0(unsigned int from, unsigned int to) { 
    int p = to - from; 
    if (p == 0) return from; 
    int x = to + from; 
    int s = 0; 

    s += (x * (p >> 1)); 

    s += (p % 2 == 0) ? x >> 1 : x; 

    return s; 
} 

私は、以前のテストのように、ループの数が同じでこれを実行しました。ここです。私が見たもの：

$ time ./addm 

real 0m0.158s 
user 0m0.093s 
sys  0m0.047s 

これはあなたの目的のための数式の変形と考えることができるか分かりません。いずれにしても、私にとっては面白い運動でした。

Answer 2

私はコードを書くつもりはありませんが、これはあなたがタスクに取り組んでいるコアの数に直接比例するものです。

範囲をタスクに分割し、範囲の各サブセクションを合計するためにスレッドを開始すると、選択した実装をコアの数（譲渡または譲受）で割ることになります。

また、SIMD拡張を使用して、手作業でメモリにデータを書き込むことによって、加算（ベクトル加算）を容易にすることができます。それを別の極端にすると、実際にはGPUを使って部分範囲の追加を計算することができます（ただし、オーバーヘッドになるには十分な範囲が必要です）。この質問は、命令間の依存関係がなくても簡単に得ることができるので簡単です。

Answer 3

下半分と上半分の範囲を（ゼロから上限nまで）分割します。下半分の各値には、上半分にn/2の大きな値があります。 n/2個あるので、上半分の合計は下半分+（n/2）^ 2の合計です。

だろうPythonで

：あなたはiからjへsegementに合計を取得するためにsegment treeを使用することができます

def sum1(lower, upper): 
    if upper <= 0: 
     return 0 
    m, r = divmod(upper, 2) 
    return sum1(0, m) * 2 + m * m + r * upper - sum1(0, lower - 1) 

Answer 4

。この構造体にはO（log n）ルックアップ時間があります。

Answer 5

機能：

long sum(long lower, long upper) { 
    long s = 0; 
    s = ((upper * (upper + 1)) - (lower - 1) * (lower))/2; 
    return s; 
} 

パラメータで呼び出される：（1,9999999）は加算式N（N + 1）/ 2に一致し、コアデュオに以下のプロファイルで実行499999.95億返し：

real 0m0.005s 
user 0m0.002s 
sys  0m0.003s 

それはあなたの機能をチェックする価値があるかもしれない、私は彼らがこの結果を返す見ることができない - 数学的なオプションは、はるかに優れたソリューションです;）