« FizzBuzz 再び : Integer#times の落とし穴 | トップページ | Project Euler : Problem 58 »

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 でコーディングしている方がいらっしゃいました。でもやっていることは同じはずなのに、処理の仕方が違うのでコードも全然違って見えます。
 こんな風にコーディングに個性が出るのが、プログラミングの面白いところだと思います。

« FizzBuzz 再び : Integer#times の落とし穴 | トップページ | Project Euler : Problem 58 »

Haskell」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

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

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/50721973

この記事へのトラックバック一覧です: 平方根の求め方 その2 〜 今度は Haskell で:

« FizzBuzz 再び : Integer#times の落とし穴 | トップページ | Project Euler : Problem 58 »

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            
フォト

最近のトラックバック

無料ブログはココログ