java - Java で最速の因数分解プロセス

Question

指定された値の平方根を 10^100 まで計算するプログラムを Java で作成しています。このためには、BigInteger を使用する必要があることはわかっていますが、扱っているプロセスはあまり効率的ではなく、多くの時間がかかります。プログラムを扱うために数を素因数分解する最速のプロセスは何ですか? より高速なアルゴリズムは何ですか?

前もって感謝します。

Answer 1

まず、入力値のほとんどは、平方根に対する正確な整数の答えを持っていないことを理解していただければ幸いです。これを BigDecimal ではなく BigInteger で実行しますか?

nまでの各値を反復処理したくないのは確かです。回答をより迅速に改善する方法が必要です。これを行う簡単な方法は、平方根の値の最初の推測 (n/2 をお勧めします) を行い、その余因子 (n / 推測) を見つけることです。等しい場合は完了です。等しくない場合は、推測を更新して、推測とその余因子の平均にします。一方は実際の平方根よりも大きくなり、もう一方は小さいので、平均すると実際の平方根に近い値になります。泡立てて、すすぎ、繰り返します。正確な平方根がない場合は、因子と補因子が互いに 1 以内になった時点で停止します。

補遺:これは疑似コードです (実際には Ruby ですが、ほとんど同じです)。

def sqrt(n)
  guess = n / 2
  cofactor = 2
  loop do
    cofactor = n / guess
    break if (guess - cofactor).abs <= 1
    guess = (guess + cofactor) / 2
  end
  return [guess, cofactor].min
end

Java への変換は非常に簡単です。