私のアルゴリズムは、iは整数<code>x</code>と<code>i</code>の1つの< <code>i</code> < <code>x</code>次の値を<code>i = floor(x/i) + (x mod i)</code>によって計算されるように、出発整数<code>i</code>ためにそのアルゴリズムを有する

Question

遅すぎます。これは既に見たiに達するまで続きます。

JavaScriptで

（この質問はあるものの、言語に依存しない）：

function f(x, i) { 
    var map = {}; 
    while(!map[i]) { 
     map[i] = true; 
     i = Math.floor(x/i) + (x % i); // ~~(x/i) is a faster way of flooring 
    } 
    return i; 
} 

私たちは最終的に我々はすでに見てきたiに達するであろうことを証明することができますが、私は思ったんだけど：

1. 次のiをより効率的に計算する方法はありますか？
2. （さらに重要なこと）ループn回を実行することなく、n番目のiを計算する方法はありますか？

---

だけ明確にする - 私はそのチェックのためのJSハッシュマップを使用するよりも速い方法があります知っている、そしてその床材は、他の言語で整数除算に置き換えることができます。私はこれらの最適化を両方行いましたが、コードを理解しやすくするためにそれらを残しました。混乱を招いて申し訳ありません。

ありがとうございます！

Answer 1

私はメインタイムエター - マップと思います。ハッシュ関数を使用しています（おそらく単純ではないでしょう）。 iの範囲が妥当な値で制限されている場合は、ビット/ブール配列（またはJavaScriptアナログ）を使用する方が良いでしょう。

2番目の2つの桁。 Javascriptでは浮動小数点数と整数が区別されますか？ （これは整数の除算の基本的な特性/モジュロ定義の）乗算および減算して剰余を求める、1つの整数除算を行うことが可能である：

p = x \\ i 
i = p + (x - p * i) 
or 
i = x - (x \\ i) * (i - 1) 

注：ほとんどのプロセッサで整数除算が同じで両方の商、残渣を算出します時間

mov eax, 17   //dividend 
mov ecx, 3   //divisor 
xor edx, edx   //zero 
div ecx    //edx:eax pair divide by ecx 
//now eax contains quotient 5, edx contains residue (modulus) 2 

あなたがCでASMを使用するか、またはデルファイDivModのようないくつかの機能を持つことができるならば、あなたはいくつかのより高速な計算を行うことができます。