« 分光 | トップページ | ハエ »

2015年2月20日 (金)

√2 の話:その24:整数平方根:1

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

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

★考え方:アルゴリズムの「珍しさ」狙いです。
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
・・・
奇数を次々に足していくと、平方数になる。(別名「四角数」)

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

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

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

★ではVBAプログラム
VBAでは、変数の型が宣言できます。{十進BASIC出は数値には変数の型がありません。文字変数には「$」をつけますが。}
整数には下のような2種類があります。
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
----------------------------------------
真ん中の列が私の自作関数の出力。右の列はチェックのためにVBAのSqr( )の整数部を取ったもの。
望み通りの関数が出来上がりましたとさ。メデタシめでたし。

« 分光 | トップページ | ハエ »

理科おじさん」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

« 分光 | トップページ | ハエ »

2017年11月
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ