●FizzBuzzのプログラム書法

今話題のどうしてプログラマに・・・プログラムが書けないのか?に関して、FizzBuzz問題がネットを賑やかしてますね。

1から100までの数をプリントするプログラムを書け。ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、3と5両方の倍数の場合には「FizzBuzz」とプリントすること。

ワンライナーとかはゲームなのでそれにクレームをつけるのはヤボだというのは分かっているのですが、元ネタの趣旨から言うと、トリッキーなプログラムが書けることよりは、ごくフツーのプログラムを正確に素早く書けることが求められているわけです。

では、ごくフツーに書いたらどうなるかということですが、たとえばPerlで書いてみると、

#!perl
use strict;

for (my $i = 1; $i <= 100; $i++) {
    if ($i % 3 == 0 && $i % 5 == 0) {
        print "FizzBuzz\n";
    } elsif ($i % 3 == 0) {
        print "Fizz\n";
    } elsif ($i % 5 == 0) {
        print "Buzz\n";
    } else {
        print "$i\n";
    }
}

こんな感じでしょうか?

実は、FizzBuzz問題を見たときには、数秒間ためらいがありました。

• 「3と5両方の倍数」を15の倍数と置き換えるのは妥当か?
• 「3と5両方の倍数」を3の倍数の場合の特別なケースとするか?
• 3、5、100の「マジックナンバー」はリテラルのまま書き下してよいのか?

それと、ワンライナーたちは、「i <= 100」ではなくて「i<101」とする例がほとんどですが、こうする理由は1文字減るからでしょうね。ですが、書法としてはまずい書き方ですよね。

FizzBuzz問題を想定どおり「入社試験」として出す場合であれば、私であれば「i < 101」を減点すると思います。

私はセキュリティを生業にしていますが、その立場からもプログラム書法は大事だなぁと思っています。セキュリティホールは一種のバグであって、バグを根絶するためにはプログラムの正しい書き方に従うことが重要だと思うからです。

●n <= 100 か n < 101 か

同じようなこと書いている人いますね。 泡斎のままならない日々 - Fizz-Buzz問題 で遊ぶ

ちなみにちなみに，一番最初ので for(int i=1; i<101; i++){ ... と書いたらおれなら減点する． if(i%15 == 0 ){ ... としても同様． 理由はプログラムの仕様にそってないから．

nihaaaaaaaa

え、えええええ。そんなバカな！ボクはこれまで「i<101」こそ正しいと信じてきたのに… 1文字減るとかはどうでもよくて、「<=」「>=」ってややこしいからあまり使いたくない。 どっちが先だっけ？とか迷うし（えええ）、大体「より小さい、若しくは等値」って複雑な気がする。 この感覚は正常なのかなあ。

「正しい」も色々あるのですね。

●FizzBuzzのプログラム書法(続き)

鵜飼昌樹さんからトラックバックを頂戴しました。
[雑記] 境界表現に関する非プロのたわごと

FizzBuzz の場合はまずいと思いますが一般論としてはどうか。

int foo[100];

for(i=0; i<100; i++){
  foo[i]=hoge;
  ...
}

のときに(マジックナンバーを使うのはさておいて) i<=101 なんて書かないと思うわけです。

えーっと、i<=101 ではなくて、i<=99のことだと思いますが、それはさておき。
　私が言いたいのはまさに鵜飼さんと同じ主張です。100回ループするのであれば、99や101ではなく、100と書こうよ。N回ループするのであれば、N-1やN+1ではなく、Nと書こうよということです。決して、「<ではなく<=」を使えという主張ではありません。
　ということで、鵜飼さんと私の主張は根っこのところでは同じだと思います。

●IEEE754のとりうる整数の範囲

hnwさんの日記は一見すると平易だが、恐ろしい毒がこっそり忍ばせてある。読者は表向きの平易に書かれたウンチクを楽しみながら、裏の毒を味わうという二重の楽しみを体験することができる。

今日はPHPのround関数に関して前回と違った切り口で紹介してみます。また、コンピュータ上での整数についても少し紹介してみます。

前回の記事「PHPの奇妙なround関数」(id:hnw:20070515)を読んで、小数点が付いた数なんてPHPで触ったことないから関係ないや、なんて考えた方が居るかもしれません。そんな方のために、今回は整数を四捨五入してみます。

[hnwの日記 - round関数で整数を四捨五入してみるより引用]

そして、IEEE64bit浮動小数点数であれば仮数部が52bitありますので、-2の53乗から2の53乗（約9000兆）までの整数は全て正確に表現できます。つまり、今回登場した変数値はどれも見た目通りの整数です*1。

仮数部が52bitあると、どうして2の53乗までの整数が表現できるのか、それを理解するためには、2進浮動小数点数の内部表現についての理解が必要となる。

一般に、２進浮動小数点数は、以下のような内部表現をとる。

± 1.bbbbbbbbbbbb × 2^nnn

1.bbbの部分が仮数部である。仮数部の最上位桁が1固定になっている理由は正規化をしているためである。そして、最上位桁が1と決まってるからには、わざわざメモリ上の1ビットを割り当てる必要がないことから、現実のメモリ上の表現としては省略している。これをケチ表現(economized form)と呼ぶ。すなわち、IEEE754形式の浮動小数点数は、実際には仮数部は53bitあるわけだ。
ここで、仮数部が全て1となる数を検討してみよう。

1.111 ..... × 2^52 = 2^53 - 1

であるので、2^53 - 1までは表現できることがまず分かる。
この数に1を足すと、有効桁数としては54ビットとなるわけだが、末尾が0であるので、

1.0 × 2^53

として正しく表現できる。この数に1を足すと、有効桁数が足らないので表現できない。すなわち、2^53が正確に表現できる整数の上限となる。

このようにして、1 〜 2^53 までは表現できることがわかる。
負の数字については、符号ビットにより対応する。
ゼロについては、浮動小数点数の場合、特別扱いする必要があるのだが、IEEE754の場合は、前に述べた非正規化数の特別な場合(仮数部が全て0)として表現する。

符号なし2進52ビット固定小数点数の場合は、0 〜 2^52 - 1 の範囲の整数を表現できるわけであるが、IEEE754は仮数部のケチ表現などにより見かけの有効数字を桁増しして、2^53までの数値を正確に表現できる。巧妙な手法である。

このように複雑な内容を、hnw氏はサラリと書き流し、読者がワナに掛かるのを待っているのである。
まことに恐ろしい毒と言わざるを得ない。