"残余"を提供する平方根のアルゴリズムが必要

私は小数点を使用せずに計算をしています（実数のみをサポートしています）が、平方根を実現したいと思います。"残余"を提供する平方根のアルゴリズムが必要

数値が12のように平方根関数が押されているときは、平方根を単純化/「縮小」して2 * sqrt（3）を返します（2 * 2 ）* 3、sqrt（2 * 2）を2として抽出します。

私は非常に良いgcd（）メソッドと肯定的なパラメータに制限されているpow（）メソッドを持っているbigintegerを使用していますあなたは私がやろうとしている正確に何をやろうとしている。

私はこれを行うには、しかし、彼らは数百の桁範囲内の数字でしばらく時間がかかることがあり、いくつかの反復方法を考え出すことができます。

私は、私が暴露されていないかわいい、シンプルで、反復的でないトリックがあることを願っています。

だけ明確にする：小数の長いストリームなし

17 + 4i √3 
----------- 
    9

：私は、私はこのような結果に計画していますので、虚数を追加する意図を持っています。

2011-06-21 Bill K

平方根12の2 * sqrt（3）を意味することを願っています。 –

大多数の数字のため、この結果は一意ではないかもしれません（または、ここで明白な数学の定理が欠落していますか？ここで少し遅れています;））、要件を少し明確に指定する必要があります。明らかに数の因子を使うことができますが、それは因数分解の問題です。 – Voo

ありがとうございました@、私はどこかでそれをやろうと思っていました！ –

あなたが求めているのは、本質的に、すべての繰り返される素因数を見つけることです。数百桁の数字を扱っているので、ここでは一般的にこれを行う良い方法がないと推測します。さもなければ公開鍵暗号は突然、やや不安定な状態に陥ります。

methods of computing the square rootの番号があります。これらを使用すると、結果は整数のとの残数が1未満になるように表現できます。

2011-06-21 22:32:16

平方根を計算するすべての方法は、平方根に非常に近い数を返すことに基づいているように見えました。例えば、578は2 * sqr（17）を返さなければなりません。24 –

の近くの数字ではありません。そのため、[unique prime factorization]（http：//en.wikipedia。org/wiki/Fundamental_theorem_of_arithmetic）を参照してください。 – YXD

はい、簡単な解決策はないと思います。私はちょっと待つつもりですが、あなたはおそらく正しいでしょう、私はちょうどファクタリングとペアを探して行く必要があります。良いニュースは、同じ方法はキューブのルーツを解決するだろう:) –

あなたの番号よりも小さい完璧な正方形を見つけることができます。それはあなたに方程式の一部を与えるでしょう、あなたはあなたの番号とあなたが見つけた完璧な正方形の違いである残りの部分だけを扱う必要があります。これは数字が大きくなるにつれて低下しますが、おそらくそれほど速くはありません。

2011-06-21 22:35:43

うーん、直感的に私はこれが動作するとは思わない。最高の正方形が私の数よりも少ないかもしれないので、使用できないことを意味する私の数の要素ではないかもしれません。次の最高の広場（私が避けようとしていた反復的な解決策）に行く必要があります –

良い点ファクタに完全に間隔を置いて配置されています。あなたにはあまり得られないものを含める必要があります。いくつかの基本的な最適化以外に、できることがたくさんあるとは私は確信していません。 –

答えて