開平法で平方根を任意桁まで求める【Python実装付き】

はじめに

コンピュータで平方根を求めるなら、二分探索やニュートン法といった高速な数値計算法を使うのが普通です。
しかし、昔から人間が「筆算」で平方根を求めるためのアルゴリズムも存在します。
それが 開平法（かいへいほう） です。

開平法とは？

小学校の算数で習う「筆算の平方根」のアルゴリズムです。
1桁ずつ順に答えを確定していくため、小数点以下も含めて任意桁まで正確に平方根を計算できます。
簡単に言うと、手計算で平方根の正確な値を求めるアルゴリズムです。

開平法のアルゴリズム（手順）

平方根を求めたい数を N とすると、以下のように計算します。そして、便宜上Q(初期値0)という変数を設けます

1. N を小数点を基準に左右に 2桁ずつ区切る
   （例：12345 → 1 23 45）

2. 二乗して「最も左のブロック」以下となる最大の整数を求める。

3. これまでに得た商を使って 新しい桁を決める。

   (Q*10 + x) * x <= 余り
   

   を満たす x を求める。なお、xは0以上9以下の整数です。

4. N を更新：

N = N - (Q*10 + x) * x

5.Q を更新：
Q = Q10 + 2x
6.すべての桁が求まるまで 2〜5 を繰り返す。

より詳しくは以下のURLを見たほうがわかりやすいかもしれません
https://manabitimes.jp/math/1318　

Python実装例

def sqrt_by_hand(n: int, digits: int) -> str:
    """
    開平法によって √n を digits 桁（小数点以下）まで正確に求める
    """
    # n を「2桁ずつ」に分けて処理する
    s = str(n)
    if len(s) % 2 == 1:
        s = "0" + s
    pairs = [int(s[i:i+2]) for i in range(0, len(s), 2)]
    pairs += [0] * digits  # 小数点以下を求めるために 00 を追加

    result = ""
    remainder = 0
    divisor = 0

    for p in pairs:
        remainder = remainder * 100 + p
        x = 0
        # divisor*10 + x を使って桁を決める
        while (divisor * 10 + (x+1)) * (x+1) <= remainder:
            x += 1
        remainder -= (divisor * 10 + x) * x
        divisor = divisor * 10 + 2 * x
        result += str(x)

    # 小数点を挿入
    int_len = len(str(n)) // 2 + (len(str(n)) % 2)
    return result[:int_len] + "." + result[int_len:]

---

実行例

print(sqrt_by_hand(2, 20))

1.41421356237309504880

小数点以下20桁まで、正確に展開されました 🎉

まとめ

初めは完全にネタとして書いていたのですが、実用性があってほしいので、ほかの数値計算法と比較してみたいと思います。