Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
ラベル 数値 の投稿を表示しています。 すべての投稿を表示
ラベル 数値 の投稿を表示しています。 すべての投稿を表示

2008年10月18日土曜日

Python で二進数、十進数の変換

1. 二進数から十進数へ

Python で、数値を 2 進数から十進数に変換したい。

2.1 組み込み関数 によると、

int([x[, radix]])

文字列または数値を通常の整数に変換します。…
radix 引数は変換の基数を表し、範囲 [2, 36] の整数またはゼロをとることができます。

long([x[, radix]])

文字列または数値を長整数値に変換します。…
radix 引数は int() と同じように解釈され、x が文字列の時だけ与えることができます。

int() 関数を、このような目的で使えることを知らなかった。(@_@;)

例えば、2進数を表す文字列 1010 を、十進数に変更する。

>>> print int('1010',2)
10

 

2. 十進数から二進数へ

十進数から2進数へ変換するには format 関数を使う。

PEP 3101: Advanced String Formatting によると、

In Python 3.0, the % operator is supplemented by a more powerful string formatting method, format(). Support for the str.format() method has been backported to Python 2.6.…

There’s also a format() built-in that will format a single value. It calls the type’s __format__() method with the provided specifier:…

'b' - Binary. Outputs the number in base 2.

Python 2.6 であれば、次のように書ける。例えば、十進数の 10 を、2進数に変換する。

>>> print format (10,'b')
1010

 

GMPY

Binary numbers には

を使った方法が紹介されていた。

 

3. その他

十進法 – Wikipedia によると、

十進記数法は単に十進法と呼ばれることもあるが、これを「10 進法」と書くのは好ましくない。10 が十を意味するのは十進記数法だからであり、例えば二進記数法ならば二を意味する。漢数字にはそのような曖昧さはない。英語でも同様に base 10 より decimal が好まれる。

 

参考サイト

関連記事

2008年10月14日火曜日

Haskell で、繰り返しのある数値を生成する関数を定義 – read, cycle 関数を使って

1. 繰り返しのある数値を生成したい

Haskell で、与えられた数値を、繰り返す関数を定義したい。

例えば、1234567890 を与えたら、

`1234567890123456790123…’

のように、数値を繰り返した結果を得たい。

 

2. はじめに思い付いた面倒な方法

はじめに思い付いた方法は、

  1. 0 ~ 9 のリストを指定した回数だけ複製したものを連結して、
  2. Integer 型に変換する makeNum 関数を作成すること。

makeNum 関数の中では、次のようなリストが渡されたら、

  • [0,1,2,3,4,5]

同じ長さの、 0 からはじまって 1 ずつ増加する数列を作り、

  • [0,1,2,3,4,5] → 反転させ  [5,4,3,2,1,0]

zip でくっつける。

  • [(0,5), (1,4), (2,3), (3,2), (4,1), (5,0)]

それぞれの要素を (a,b) とすると、a*10^b したものを foldl1 で足し合わせるという方法。

makeNum :: [Integer] -> Integer
makeNum xs = foldl1 (+) [a*10^b | (a,b) <- zip xs $ reverse [0..(length xs)-1]]

main = do
  print $ makeNum $ concat $ replicate 3 [0..9]

この方法は、わかりずらい… (@_@;)

 

3. Python で実装するには

Python だったら、どう定義するか考えた。

def makeNum(L):
    return long("".join(str(x) for x in L))
    
print makeNum(range(0,10) * 3)

数値のリストを渡したら、空文字で join して long() で数値へ変換。

 

4. Haskell の Read クラスを使う

上記のPython で書いたように、

文字列から数値に変換する

ことができたら、はじめに考えた方法よりも、簡単に実装できそう。

「あれ?でもそんな関数ってあったかな?」

と思い検索してみると、Re: string to Integer に、

Turning a string into an integer is easy with the Prelude function 'read':

n :: Integer
n = read "-34232"

あらら、Prelude にあったとは気がついてなかった… ^^;

Prelude にある

を読むと、文字列 <ー> 型 の変換をするため方法が解説されている。

これによると、

Show <-> Read

  • 文字列への変換のための Show クラス
  • 文字列からの変換のための Read クラス

Showクラス については、以下を参照。

 

read メソッドの型

read 関数を見ると、最後の型が、型変数 a となっており、Read クラスの制約が付いている。

 read :: Read a => String -> a

これは、

で見た形と同じ。

 read メソッドを使えば、

  print $ (read $ concatMap show $ concat $ replicate 3 [0..9] :: Integer)

 

5. cycle 関数でリストを繰り返す

`1234567890123456790123…’  を延々と繰り返される無限リストのように見立てる。そこから、一部を取り出す関数を考える。与えられた引数を延々と繰り返す infstr 関数を定義するなら、

infstr :: String -> String
infstr cs = cs ++ infstr(cs)

main = do
  print $ (read $ take 30 $ infstr "1234567890" :: Integer)

しかし、こんな基本的な関数、どこかに定義してあるのではないかと思い Prelude を探すと、

repeat があった。しかし、これは対象がリストではなない。

repeat 関数の近くに、cycle 関数があった。

cycle :: [a] -> [a]

これを使えば、

  print $ (read $ take 30 $ cycle "1234567890" :: Integer)   

と極めてシンプルに定義できる。

一体全体、最初何を書いていたのやら。(o_ _)o~†

 

cycle 関数の定義で気になったこと

ところで、cycle の実装を見ると、

cycle                   :: [a] -> [a]
cycle []  = error "Prelude.cycle: empty list"
cycle xs  = xs' where xs' = xs ++ xs'

xs’ = where … と書くのは、なにか理由があるのかな ?

Haskell の数値 – Int は型で、Num は型クラス

1. Haskell の数値の種類

PreludeNumbers には、Haskell 数値型が挙げられてる。

これを Python の「3.2 標準型の階層」における Numbers と比較すると、

Float について、Python では、

Python は単精度の浮動小数点数をサポートしません; 単精度の数を使う理由は、通常プロセッサやメモリ使用量の節約ですが、こうした節約は Python でオブジェクトを扱う際のオーバヘッドに比べれば微々たるものにすぎません。

(3.2 標準型の階層 より)

ついでに、Ruby では、

Float の実装は C 言語の double で、その精度は環境に依存します。

(Float - Rubyリファレンスマニュアル より)

http://www.ruby-lang.org/ja/man/html/_C1C8A4DFB9FEA4DFA5AFA5E9A5B9A1BFA5E2A5B8A5E5A1BCA5EBA1BFCEE3B3B0A5AFA5E9A5B9.html

組み込みクラス/モジュール/例外クラス - Rubyリファレンスマニュアル via kwout

 

2. Int と Integer の違い

Preludedata Int によると、Int は、

A fixed-precision integer type with at least the range [-2^29 .. 2^29-1].

Int に対して data Integer は、

Arbitrary-precision integers.

つまり、Int型 は表現できる範囲が決っているのに対して、Integer 型 は制限がない。

 

maxBound, minBound 関数で、表現できる範囲を調べる

Int 型は 2^29 の範囲を表現できることが保証されている。 実際に使える範囲を知るには、

「using minBound and maxBound from the Bounded class. 」

(data Int より) 。

maxBound は Bounded クラスのメソッドで、次のように定義されている。

maxBound :: a

ん? (@_@;) 何だろう、このメソッドは。「引数が一つ?」かと一瞬思いきや、

引数はなく、返ってくるのは型変数 a ?

 

型クラスとインスタンスの関係を整理する

Bounded クラスを見ると、以下のように定義されている。

class  Bounded a  where
    minBound, maxBound :: a

型クラスの宣言で使われている型変数 a は、Bounded クラスのインスタンス

例えば、Bool 型は、Bounded クラスのインスタンスとして定義されている。Bool 型の値は、True と False しかないので、最大・最小を考えやすい。以下のように定義されている。

instance Bounded Bool where
  minBound = False
  maxBound = True

この型クラスとインスタンスの表現は、慣れないと混乱する。(+_+) 基本的な事項を整理する。

上記の `instance’ は、

Bool 型が Bounded クラスのインスタンスである

ことを宣言している。

Bounded クラスでは、実装すべき関数は 2 つある。

  • minBound
  • maxBound

この関数の返す値は、Bounded クラスの定義を見ると、型変数 a とある。

class  Bounded a  where

この型変数 a は、任意の型ではなく、 Bounded クラスのインスタンス

Bool 型を、Bounded クラスのインスタンスであると、定義したのを見直す。

instance Bounded Bool where
  minBound = False
  maxBound = True

minBound は False を返し、maxBound は True を返している。

このように書ける理由は、「Bool 型 は、Bounded クラスのインスタンスである」と、最初の行で宣言している。

よって、Bool 型の値は、Bounded クラスのインスタンスだから、

「 minBound, maxBound 関数を定義し、その関数は Bounded クラスのインスタンスである型ノ値でなくてはならない」

ということを満たすことになる。つまり、 Bool 型に対して maxBound を適用すると、Bounded クラスのインスタンスである Bool 型の値 True を返すということ。

(cf. Haskell の代数的データ型と型クラス、instance 宣言の関係)

 

maxBound を適用するときは、型を指定する

ghci で maxBound を呼出すと、

Prelude> maxBound

:1:0:
    Ambiguous type variable `a' in the constraint:
      `Bounded a' arising from a use of `maxBound' at :1:0-7
    Probable fix: add a type signature that fixes these type variable(s)

「型変数 a が曖昧だから型を付けろ!」ということかな。

Haskell : maxBound によると、以下のように型を指定する必要がある。

Prelude> maxBound :: Bool
True

なぜなら、maxBound 関数は、いろいろな型のインスタンス宣言で多重定義されているから、どの型に適用したいのか示さなければならない。

 

表現できる数値の確認

maxBound, minBound を使って限界を確認してみる。

  print $ 2 ^ 29 - 1       --  536870911
  print (maxBound :: Int)  -- 2147483647
  print $ 2 ^ 31 - 1       -- 2147483647
  print $ 0x7fffffff       -- 2147483647

  print $ - 2 ^ 29         --  -536870912
  print (minBound :: Int)  -- -2147483648
  print $ - 2 ^ 31         -- -2147483648
  print $ -0x80000000      -- -2147483648

(cf. 32ビット – Wikipedia)

 

Int 型は、境界となる値に気をつける

Int 型の範囲を調べるために、境界となる値を調べる関数 hoge を定義する。

hoge :: Int -> Int
hoge x = 2 ^ 31 + x

main = do
  print $ hoge (-1) --  2147483647
  print $ hoge 0    -- -2147483648

hoge 関数は、Int で表現できる範囲を超えると負の数になってしまう。

これを修正するには、toInteger を使う。

hoge :: Int -> Integer
hoge x = 2 ^ 31 + (toInteger x)

Int と Integer は型が異なるので、

  print $ hoge (0 :: Integer)

と書くと、

Couldn't match expected type `Int' against inferred type `Integer'

「Integer 型に適用しているけれど、そこは Int 型!」と、しっかり怒られる。

 

3. Float もあるけれど、Double を使えば良い

Float, Double については、各々以下を参照。

先ほど述べたように、Python は Float に相当するものがない。Haskell も基本は Double 。

Floats (probably 32-bits) are almost always a bad idea, unless you Really Know What You Are Doing. Use Doubles. There's rarely a speed disadvantage—modern machines will use the same floating-point unit for both.

(Performance/Floating point – HaskellWiki より)

Float と Double では、パフォーマンスに滅多に差が出ないとのこと。

FloatDouble の型の定義を比較すると、同じ型クラスのインスタンスであることがわかる。

 

4. Rational は有理数

Rational は、有理数を表わす。

有理数(ゆうりすう、rational number)とは、二つの整数 a, b (ただし b は 0 でない)をもちいて a/b という分数で表せるのことをいう。b = 1 とすることにより、任意の整数は有理数として扱うことができる。

(有理数 – Wikipedia より)

Python で有理数を使うには、こちらを参照。

Haskell では、以下のように type で別名が与えられている。

type Rational = Ratio Integer

Data.Ratio によると、% によって Ratio a 型の値を作ることができる。

(%) :: Integral a => a -> a -> Ratio a

Rational を少数に変換するには、Fractional クラスの fromRational を使う。

fromRational :: Rational –> a

試してみる。

import Data.Ratio
main = do
  print $ 1 % 3                -- 1%3
  print $ 2 % 6                -- 1%3

  print $ fromRational (1 % 3) -- 0.3333333333333333

 

5. Num は型クラス

数値に関するエラーで、よく見かける Num 。

これは型ではなくて、型クラス

class (Eq a, Show a) => Num a where

この型クラスにより、型に適用できる関数が定義されている。適用できる関数により、数値の型を分類していると言える。数値の型が、どの型クラスのインスタンスで、どのような関数を適用できるのか、確認しておくと良い。

 

数値の階層関係

階層関係を示すと、

その他、RealFrac, RealFloat がある。

上記の階層関係における --- の右側のクラスは、Num の系統以外に、各々のクラスに制約として付いているクラス。

Num クラスでは、値が等しいかどうか分かればよく、順序関係を表す Ord クラスは、Real クラスで付けられている。

例えば、 「10 より大きいか検査する関数」を定義して、Num クラスの制約を付けたとする。

comp10 :: Num a => a -> Bool
comp10 x = x > 10

main = do
  print $ comp10 8

実行すると、

    Could not deduce (Ord a) from the context (Num a)
      arising from a use of `>' at numtest.hs:28:11-16

`>’  を適用することができないとエラーがでる。

少なくとも、comp10 関数の引数の制約は Real でなくてはだめということ。

 

6. まとめ

  • Haskell における数値の表現には、色々な型がある。
  • 数値の型は、型クラスの観点から分類されている。
  • 型クラスは、数値に対する可能な操作を定義することによって、数の概念を表現している。