c - 非常に大きな数の整数平方根を桁ごとに求める効率的なアルゴリズムは何ですか?

Question

数千桁の整数の平方根を求めるプログラムを作成する必要があります。このような大きな数を格納および分割するためのデータ型がないため、Newton Raphson を使用できません。数値を格納するためにCで長い配列を使用しています。おそらく数字を反復して平方根を見つけるアルゴリズムはありますか?

編集：

GMP などの外部ライブラリを使用できません。

Answer 1

ターゲット数を入力できる場合は、そのような大きな数を少なくとも 1 つ格納する方法が必要です。Newton-Raphson の場合、数値を半分にして足すことができれば十分です。割り算を使わずに数を半分にする方法を考えてください。

ETA: 訂正: 除算は、2 倍と減算によって回避できます。

Answer 2

学校で教えられている平方根を計算する長除算法を実装できます。このメソッドを基数 10 に実装すると、結果は左から右に 1 桁ずつ計算されます。整数部分が計算されたら停止できます。