« 2010年12月 | トップページ | 2011年2月 »

2011年1月

2011年1月29日 (土)

平方根の求め方 その2 〜 今度は Haskell で

 以前、Ruby で平方根を求めたことがありましたが、今度は Haskell でやってみました。
 今回は入力(引数)も出力(戻値)も桁数の制限を受けないように、どちらの型も String にしてみました。
 また、今回は「筆算による開平法」をシュミレートしたものも作ってみました。

 

《 筆算による開平法 》

 「筆算による開平法」の具体な方法については、こちらを参照してください。

import Data.Char {- -- 筆算による開平法 -- -} squareRoot :: String -> String squareRoot cs = root' (int' ++ frac' ++ repeat '0') 0 0 where (int, frac) = break (== '.') cs int' = if odd (length int) then ('0' : int) else int frac' = if null frac then "." else frac root' ('.' : xs) r d = '.' : root' xs r d root' (a : b : xs) r d = (intToDigit . fromIntegral) n' : root' xs r' d' where n = r * 100 + read [a, b] n' = last $ takeWhile (\x -> (d + x) * x <= n) [0 .. 9] r' = n - (d + n') * n' d' = 10 * (d + n' + n')

 このコードは、まず始めに整数部分と少数部分を整形しています。
 整数部分は偶数桁になるように、必要があれば最上位の桁に '0' を補います。
 少数部分は引数に少数点が含まれていなければ補い、さらに '0' の無限リストを付け加えています。
 その後は、root' 関数で「筆算による開平法」をシミュレートしているだけです。

 実行すると、次のようになります。

*Main> take 50 $ squareRoot "2" "1.414213562373095048801688724209698078569671875376" *Main> take 50 $ squareRoot $ show 3.0 "1.732050807568877293527446341505872366942805253810" *Main> take 50 $ squareRoot "0.000000000000000000000000123" "0.000000000000350713558335003638336349349661310276"
 squareRoot 関数をそのまま実行すると、メモりが枯渇するまで文字列を出力し続けるので、take などを使って適当に切ってください。(その場合、少数点も一桁分に数えられるのでご注意を)
 また、大きな桁の数を show を使って文字列に変換すると、浮動少数点表記になってしまい、そのまま squareRoot 関数に渡すとエラーになります。
*Main> show 0.000000000000000000000000123 "1.23e-25" *Main> take 50 $ squareRoot $ show 0.000000000000000000000000123 "1.1*** Exception: Prelude.read: no parse"

 

《 タイガー計算機による開平法 》

 「タイガー計算機による開平法」の具体的な方法については、こちらを参照してください。

import Data.Char {- -- タイガー計算機による開平法 -- -} squareRoot2 :: String -> String squareRoot2 cs = root' 0 (int' ++ frac' ++ repeat '0') 1 where (int, frac) = break (== '.') cs int' = if odd (length int) then ('0' : int) else int frac' = if null frac then "." else frac root' rest ('.' : xs) n = '.' : root' rest xs n root' rest (a : b : xs) n = intToDigit c : root' rest' xs (n' * 10 - 9) where (rest', n', c) = count (rest * 100 + read [a, b]) n -- count : -- m から 奇数 n, n + 2 .. を順に引いていった時、 -- (残った数, 次に引くはずだった奇数, 奇数を引いた回数) を返す。 count m n = head $ dropWhile (\(x, y, _) -> x >= y) $ iterate g (m, n, 0) where g (a, b, c) = (a - b, b + 2, c + 1)

 このコードの内容は root' 関数の中身が違う以外は「筆算による開平法」の squareRoot と同じです。ですから、注意事項も同じです。
 ただし、squareRoot が内部でかけ算を多用しているのに対し、こちらは内部で引き算を多用しているせいか、若干こちらのほうが速い気がします。

 

 ネットを見ていたら、私と同じように「筆算による開平法」を Haskell でコーディングしている方がいらっしゃいました。でもやっていることは同じはずなのに、処理の仕方が違うのでコードも全然違って見えます。
 こんな風にコーディングに個性が出るのが、プログラミングの面白いところだと思います。

2011年1月 3日 (月)

FizzBuzz 再び : Integer#times の落とし穴

 昨日、「fizzbuzz問題」関係のブログをいくつか見ていたら、Ruby 初心者さん(プログラミング初心者さん)がたまにハマる勘違いを見つけちゃいました。(「fizzbuzz問題」に関してはこちらを参照のこと。普通は 1 〜 100 までの範囲を表示させることが多いですね)

 問題の記事はこちらです。コードを引用してみます(読み易いようにインデントさせました)

100.times{|n| if n % 15 == 0 puts "fizzbuzz" elsif n % 3 == 0 puts "fizz " elsif n % 5 == 0 puts "buzz " else puts "#{n}" end }
 実際にこのコードを走らせると次のようになります。
>ruby test.rb ruby test.rb fizzbuzz 1 2 fizz 4 buzz fizz < 中略 > 94 buzz fizz 97 98 fizz
 皆さんは間違いに気付きましたか?

 この記事を書いた方は「1 〜 100」までの範囲を表示させるつもりで 100.times{|n| .. } と書いています。ところがこう書くと「0 〜 99」までの整数が小さいほうから順に n に代入されていきます。つまり、「100回数える」んだけど、始まりは「0」からなんですね。
 そのため 1 の前に fizzbuzz が表示され、本当は最後に表示されるべき buzz が表示されていません。

 Ruby の Integer#times に限らず、プログラミング言語には「0」から始まるものがたくさんあります。例えば Ruby や C 言語の配列のインデックスや Scheme や Haskell のリストのインデックスも「0」から始まります。
 普通、物を数える時は「1」から数え始めますよね。ところが「0」から数え始めたほうがコンピュータには都合がいいらしいんですね。

 ではこの問題では Integer#times は使えないかというと、そうではありません。ちょっと工夫すれば題意どおりの表示ができます。(以後のコードはすべてメソッドの形にしてあります)

# Integer#times 修正版 def fizzbuzz1 100.times do |m| n = m + 1 if n % 15 == 0 puts "fizzbuzz" elsif n % 3 == 0 puts "fizz " elsif n % 5 == 0 puts "buzz " else puts "#{n}" end end end

 ただ、今回のような場合には Integer#times よりも、開始点と終了点が明示できる Integer#upto を使ったほうが分かり易いと思ます。(elsif を並べるのが好きではないので case を使いました)

# Integer#upto を使う def fizzbuzz2 1.upto(100) do |n| case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end end end

 さて、話はここで終ってもいいのですが、Ruby には「多様性は善」という言葉もありますから、他の方法も考えてみました。ネットで探せばもっとたくさんの方法が見付かると思います。

# while を使う def fizzbuzz3 n = 1 while (n <= 100) case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end n += 1 end end # Range#each を使う def fizzbuzz4 (1..100).each do |n| case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end end end # Range#map を使う def fizzbuzz5 arr = (1 .. 100).map do |n| case when n % 15 == 0 "fizzbuzz" when n % 3 == 0 "fizz" when n % 5 == 0 "buzz" else n end end puts arr end # 剰余演算子を使わない 1 def fizzbuzz6 fizz = ["", "", "fizz"].cycle.take(100) buzz = ["", "", "", "", "buzz"].cycle.take(100) (1 .. 100).zip(fizz, buzz) do |a, b, c| if b == "" && c == "" puts a else puts b + c end end end # 剰余演算子を使わない 2 def fizzbuzz7 nums = (0 .. 100).to_a a = [[3, "Fizz"], [5, "Buzz"], [15, "FizzBuzz"]] a.each{|arr| 0.step(100, arr[0]){|i| nums[i] = arr[1]}} puts nums.drop(1) end

※なお、すべてのコードは Ruby 1.9 を対象に書いてあります。Ruby 1.8 では動かないものがあるかもしれません。

« 2010年12月 | トップページ | 2011年2月 »

2016年7月
          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
31            
フォト

最近のトラックバック

無料ブログはココログ