√２ の話：その２４：整数平方根：１

★「整数平方根」という変な言葉を発明しました。
その昔、妙なものを考えたことがあるのです。
Ｃ言語で、整数問題を考えていたのだったと思います。
パズルコーナーか何かに応募しようと思ってね。問題は忘れましたので、例で説明します。

★与えられた整数ｎが、合成数なのか素数なのか判定したいとします。
最も単純素朴な考え方は、２から順番に整数でｎを割って行けばいい。
割り切れなかったら、素数ですね。
どこまで試せばいいんだ？
まさか、ｎ－１まで丹念に割ることはないだろう。
ｎが二つの数ａ，ｂ（ａ＜ｂ）の積だったとしましょう。
ａが√ｎより小さければ、ｂは必ず√ｎより大きくなければなりません。
ですから、√ｎまでを調べればいい。
**********
ｎを入力
ループ始まり
　　２から√ｎまでの整数で
　　　　ｎを割って余りがゼロなら：割り切れたので：素数ではない：ループを脱出
ループ
ループを途中で脱出したのではなくここまで来たらｎは素数
**********
こういう考え方でいいわけです。
このプログラムを書くとして、整数の話をしているのだから、すべて整数だけで完結させたい、というのが私の「意地」。
ところがですね、Ｃの平方根関数 sqrt は整数を与えても浮動小数点数を返してきます。
ですから、整数の話をしているのに、浮動小数点数のお世話になるので。気分ワリィ。
で、作ったのが、√ｎを超えない最大の整数を返す関数で、しかもすべて整数だけを使ってプログラムを組む、という関数。
名付けて「整数平方根（isqr）」。｛「i」は「integr」の「i」｝
現在の私、Ｃの処理系を持っていませんので、エクセルのＶＢＡで同じものを作ってお目にかけます。
効率無視、意地を通す、というプログラムですので、笑ってください。

★考え方：アルゴリズムの「珍しさ」狙いです。
1          　 =1^2
1+3       　 =4 =2^2
1+3+5    　=9 =3^2
1+3+5+7　 =16=4^2
1+3+5+7+9=25=5^2
・・・
奇数を次々に足していくと、平方数になる。（別名「四角数」）

●○◎■◆◇
○○◎■◆◇
◎◎◎■◆◇
■■■■◆◇
◆◆◆◆◆◇
◇◇◇◇◇◇

こういうことです。
式で書けば

こうですね。
「足した奇数の個数」を自乗した数が得られるわけです。
ということは、例えば、√２０の整数部だけが必要なら
1+3+5+7=16 で、奇数を４個足しましたので「４」が答えとなります。
√２０＝4.47… ですから合ってます。

四角数は有名。これを整数平方根に使おうというところに、私の「衒 (てら) い」ギラギラです。

★ではＶＢＡプログラム
VBAでは、変数の型が宣言できます。｛十進BASIC出は数値には変数の型がありません。文字変数には「$」をつけますが。｝
整数には下のような２種類があります。
Integer (整数型)　-2,147,483,648 ～ 2,147,483,647 (符号付き)
Long  (長整数型)　-9,223,372,036,854,775,808 ～ 9,223,372,036,854,775,807 (9.2...E+18) (符号付き)
折角ですから「Long  (長整数型)」を使うことにしました。
----------------------------------------
Option Explicit        '変数宣言を強制する、という宣言

Sub main()
    Dim i As Long

    For i = 0 To 40
        Cells(i + 1, 1).Value = i
        Cells(i + 1, 2).Value = isqrt(i)
        Cells(i + 1, 3).Value = Int(Sqr(i))
    Next i
End Sub

Function isqrt(n As Long) As Long
    Dim a As Long, count As Long, sum As Long
    If (n = 0) Then
        isqrt = 0
    Else
        a = 1
        count = 0
        sum = 0
        Do
            a = a + 2
            sum = sum + a
            count = count + 1
        Loop While (sum < n)
        isqrt = count
    End If
End Function
----------------------------------------
結果はこうです。
0   0   0
1   1   1
2   1   1
3   1   1
4   2   2
5   2   2
6   2   2
7   2   2
8   2   2
9   3   3
10  3   3
11  3   3
12  3   3
13  3   3
14  3   3
15  3   3
16  4   4
17  4   4
18  4   4
19  4   4
20  4   4
21  4   4
22  4   4
23  4   4
24  4   4
25  5   5
26  5   5
27  5   5
28  5   5
29  5   5
30  5   5
31  5   5
32  5   5
33  5   5
34  5   5
35  5   5
36  6   6
37  6   6
38  6   6
39  6   6
40  6   6
----------------------------------------
真ん中の列が私の自作関数の出力。右の列はチェックのためにＶＢＡのSqr( )の整数部を取ったもの。
望み通りの関数が出来上がりましたとさ。メデタシめでたし。