2の補数

2019-07-28 / tau / コメントする

簡単なケース

正の数の表現

桁数が固定された2進数の加算を考える。たとえば4桁(4 bits)の場合に1ずつ加える。

$\begin{array}{cc} 0000 + 0001 = 0001 & (1)\\ 0001 + 0001 = 0010 & (2)\\ 0010 + 0001 = 0011 & (3)\\ 0011 + 0001 = 0100 & (4)\\ 0100 + 0001 = 0101 & (5)\\ 0101 + 0001 = 0110 & (6)\\ 0110 + 0001 = 0111 & (7) \end{array}$

負の数の表現

一方、-1は0から1を引いた値として計算される。最初の計算だけ、上位桁から1を借りてこられるとして、以下の様な計算になる。

$\begin{array}{cc} 0000 - 0001 = 1111 & (-1)\\ 1111 - 0001 = 1110 & (-2)\\ 1110 - 0001 = 1101 & (-3)\\ 1101 - 0001 = 1100 & (-4)\\ 1100 - 0001 = 1011 & (-5)\\ 1011 - 0001 = 1010 & (-6)\\ 1010 - 0001 = 1001 & (-7)\\ 1001 - 0001 = 1000 & (-8) \end{array}$

上の足し算の結果と下の引き算の結果をを見ると、以下のことがわかる。

正の数(0～7)と負の数(-8～-1)の合計15個で、4ビットの全てのパターンが網羅されている
正の数の最上位ビットは0、負の数の最上位ビットは1

引き算と補数の足し算

たとえば上の例で、正の数と負の数を加えてみる。

$\begin{array}{cl} 0101 + 1110 = 0011 & (5-2=3) \\ 0011 + 1001 = 1100 & (3-7=-4) \\ 1111 + 1100 = 1011 & (-1-4=-5) \end{array}$

2の補数を計算したときに0からその数を減じているので、当然の結果ではある。いずれにしても、負数を2の補数で表現することで、減算を加算で代えることができる。

2の補数を得る方法

2の補数を得るのに、いちいち0から引かなくても、以下の方法で可能。

整数のビットパターンを反転
1を加える

4ビットの例では以下のとおり。

$\begin{array}{cc} 0001 \rightarrow 1110 \rightarrow 1111 & (-1)\\ 0010 \rightarrow1101 \rightarrow 1110 & (-2)\\ 0011 \rightarrow1100 \rightarrow 1101 & (-3)\\ 0100 \rightarrow1011 \rightarrow 1100 & (-4)\\ 0101 \rightarrow1010 \rightarrow 1011 & (-5)\\ 0110 \rightarrow1001 \rightarrow 1010 & (-6)\\ 0111 \rightarrow1000 \rightarrow 1001 & (-7)\\ 1000 \rightarrow0111 \rightarrow 1000 & (-8)\\ \end{array}$

すなわち、固定長の整数の場合、ビット反転と加算機能があれば、減算を実現できる。

典型的なビット数の整数範囲

8ビット

byte型でよく見る値。

$\begin{array}{lllr} 0111\:1111 = &2^7 - 1 &=& 127 \\ 1000\:0000 = &-2^7 &=& -128 \end{array}$

16ビット

short型でよく見る値。

$\begin{array}{lllr} 0111\:1111\:1111\:1111 = &2^{15} - 1 &= &32767 \\ 1000\:0000\:0000\:0000 = &-2^{15} &= &-32768 \end{array}$

32ビット

一般的なint型で絶対値が約21億。

$\begin{array}{llr} 2^{31} - 1 &=& ‭2,147,483,647 \\ -2^{31} &=& -‭2,147,483,648‬ \end{array}$

64ビット

long型、絶対値が約920京（！）

$\begin{array}{llr} 2^{63} - 1 &=& ‭9,223,372,036,854,775,807 \\ -2^{63} &=& -‭9,223,372,036,854,775,808‬ \end{array}$

Python3 – 数値と文字列の相互変換

2019-07-28 / tau / コメントする

数値から文字列への変換

10進数(str関数)

str関数で引数の数値を文字列化。

整数の場合、桁数が多くてもそのまま文字列化される。

>>> str(1234)
'1234'
>>> str(12345678901234567890)
'12345678901234567890'

>>> str(1234)

'1234'

>>> str(12345678901234567890)

'12345678901234567890'

実数の場合は有効数値で丸められる。

>>> str(123.45678901234567890)
'123.45678901234568'

1 2	>>> str(123.45678901234567890) '123.45678901234568'

浮動小数点で与えると、桁数が収まる範囲で固定少数表示の文字列になる。

>>> str(1e3)
'1000.0'
>>> str(1e15)
'1000000000000000.0'
>>> str(1e16)
'1e+16'

>>> str(1e3)

'1000.0'

>>> str(1e15)

'1000000000000000.0'

>>> str(1e16)

'1e+16'

2進数、8進数、16進数

組み込み関数を使う方法

bin、oct、hex関数を使った場合、プレフィックス’0b’、’0o’、’0x’がついた文字列になる。

>>> bin(31)
'0b11111'
>>> oct(4095)
'0o7777'
>>> hex(65535)
'0xffff'

>>> bin(31)

'0b11111'

>>> oct(4095)

'0o7777'

>>> hex(65535)

'0xffff'

format関数を使う方法

format関数の第2引数に基数に対応した文字を指定する。

>>> format(255, 'b')
'11111111'
>>> format(255, 'o')
'377'
>>> format(255, 'x')
'ff'
>>> format(255, 'X')
'FF'

>>> format(255, 'b')

'11111111'

>>> format(255, 'o')

'377'

>>> format(255, 'x')

'ff'

>>> format(255, 'X')

'FF'

第2引数で、桁数を指定して空いた上位桁を0で埋めることができる。

>>> format(15, '08b')
'00001111'
>>> format(15, '04o')
'0017'
>>> format(15, '02x')
'0f'

>>> format(15, '08b')

'00001111'

>>> format(15, '04o')

'0017'

>>> format(15, '02x')

'0f'

書式文字列を使う方法

書式文字列と％演算子を使っても、数値を文字列化できるが、2進数には対応していない。

>>> '%#o' % 255, '%o' % 255
('0o377', '377')
>>> '%#x' % 255, '%x' % 255
('0xff', 'ff')
>>> '%#X' % 255, '%X' % 255
('0XFF', 'FF')

>>> '%#o' % 255, '%o' % 255

('0o377', '377')

>>> '%#x' % 255, '%x' % 255

('0xff', 'ff')

>>> '%#X' % 255, '%X' % 255

('0XFF', 'FF')

文字列から数値への変換

10進数

整数(int関数)

int関数は整数の文字列を数値化するが、実数形式の文字列を与えるとエラーになる。

>>> int('1234')
1234
>>> int('1.')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '1.'

>>> int('1234')

1234

>>> int('1.')

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: invalid literal for int() with base 10: '1.'

実数(float関数)

float関数は実数の文字列を数値化する。固定小数点/浮動小数点のどちらの表現でもかまわない。

>>> float('1234')
1234.0
>>> float('1.234')
1.234
>>> float('1e15')
1000000000000000.0
>>> float('1e16')
1e+16

>>> float('1234')

1234.0

>>> float('1.234')

1.234

>>> float('1e15')

1000000000000000.0

>>> float('1e16')

1e+16

2進数、8進数、16進数

int関数の第2引数で基数を指定する。

>>> int('1111', 2)
15
>>> int('7777', 8)
4095
>>> int('FFFF', 16)
65535

>>> int('1111', 2)

>>> int('7777', 8)

4095

>>> int('FFFF', 16)

65535

第2引数には2～36まで指定可能で、0～9とA～Zまで使った36進法まで変換可能。

>>> int('1000', 1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: int() base must be >= 2 and <= 36
>>> int('1000', 3)
27
>>> int('GGGG', 17)
83520
>>> int('ZZZZ', 36)
1679615

>>> int('1000', 1)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: int() base must be >= 2 and <= 36

>>> int('1000', 3)

>>> int('GGGG', 17)

83520

>>> int('ZZZZ', 36)

1679615

‘0b’、’0o’、’0x’のプレフィックスを付けた文字列を変換するときは、第2引数を0にする。この場合、10進数も変換可能。

>>> int('0x1111', 0)
4369
>>> int('0x7777', 0)
30583
>>> int('0xFFFF', 0)
65535
>>> int('9999', 0)
9999

>>> int('0x1111', 0)

4369

>>> int('0x7777', 0)

30583

>>> int('0xFFFF', 0)

65535

>>> int('9999', 0)

9999

Python3 – 数値

2019-07-27 / tau / コメントする

int型

整数型はintで表される。

>>> print(type(1), 1)
<class 'int'> 1

1 2	>>> print(type(1), 1) <class 'int'> 1

桁数が多くなってもint型として扱われる。

>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000)
<class 'int'> 1000000000000000000000000000000

1 2	>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000) <class 'int'> 1000000000000000000000000000000

int型のチェック

>>> print(type(1)==int)
True

1 2	>>> print(type(1)==int) True

float型

数値リテラルに小数点を付けるとfloat型として扱われる。float型はCやFORTRANの倍精度の精度。

>>> print(type(1.), 1.)
<class 'float'> 1.0

1 2	>>> print(type(1.), 1.) <class 'float'> 1.0

‘/’による除算の結果は常にfloat型になる。

>>> print(type(6/3), 6/3)
<class 'float'> 2.0

1 2	>>> print(type(6/3), 6/3) <class 'float'> 2.0

‘//’による除算では商が整数化される(整数除算と剰余を参照)。

>>> print(type(8//3), 8//3)
<class 'int'> 2

1 2	>>> print(type(8//3), 8//3) <class 'int'> 2

Python3 – 書式設定～format

2019-07-27 / tau / コメントする

format関数

一つの数値・文字列の書式を設定する場合、format組み込み関数が使える。引数はリテラルでも変数でもよい。

print("Hexadecimal of 255 is " + format(255, '0x'))
print("1/7 is approximately " + format(1/7, 'e'))


# Hexadecimal of 255 is ff
# 1/7 is approximately 1.428571e-01

print("Hexadecimal of 255 is " + format(255, '0x'))

print("1/7 is approximately " + format(1/7, 'e'))

# Hexadecimal of 255 is ff

# 1/7 is approximately 1.428571e-01

formatメソッド

文字列に対するformatメソッドでも数値・文字列の書式を設定できる（書式設定の書き方は後述）。引数はリテラルでも変数でもよい。

print("Hexadecimal of 255 is {:0x}".format(255))
print("Hexadecimal of 255 is {:e}".format(1/7))

# Hexadecimal of 255 is ff
# Hexadecimal of 255 is 1.428571e-01

print("Hexadecimal of 255 is {:0x}".format(255))

print("Hexadecimal of 255 is {:e}".format(1/7))

# Hexadecimal of 255 is ff

# Hexadecimal of 255 is 1.428571e-01

formatメソッドは複数の数値・文字列を扱える。

print("My name is {} and my age is {}".format("Jane", 38))

# My name is Jane and my age is 38

print("My name is {} and my age is {}".format("Jane", 38))

# My name is Jane and my age is 38

位置引数として整数を指定し、繰り返して利用することが可能。

print("The suits of handed cards were {0}, {1}, {2}, {1}, {3}" \
    .format("Spade", "Club", "Diamond", "Heart".))

# The suits of handed cards were Spade, Club, Diamond, Club, Heart.

print("The suits of handed cards were {0}, {1}, {2}, {1}, {3}" \

.format("Spade", "Club", "Diamond", "Heart".))

# The suits of handed cards were Spade, Club, Diamond, Club, Heart.

キーワード引数として文字列を指定可能。

print("{name} is {age} years old.".format(name="Kark", age=25))

# Kark is 25 years old.

print("{name} is {age} years old.".format(name="Kark", age=25))

# Kark is 25 years old.

リストを引数にするときは整数の位置引数とリスト内の引数で指定する。複数のリストを指定するときは位置引数を0、1…と対応させていく。

result1 = ["Head", "Tail"]
result2 = ["Head", "Head"]
print("First result was {0[0]} and {0[1]}.\nSecond was {1[0]} and {1[1]}.".\
    format(result1, result2))

# First result was Head and Tail.
# Second was Head and Head.

result1 = ["Head", "Tail"]

result2 = ["Head", "Head"]

print("First result was {0[0]} and {0[1]}.\nSecond was {1[0]} and {1[1]}.".\

format(result1, result2))

# First result was Head and Tail.

# Second was Head and Head.

辞書を引数にするときは整数の位置引数とキーで指定する。キーはクォートで囲まない。

person1 = {'name': "John", 'age': 20}
person2 = {'name': "Kate", 'age': 32}
print("{0[name]} is {0[age]} years old) and {1[name]} is {1[age]} years old.".\
    format(person1, person2))

# John is 20 years old) and Kate is 32 years old.

person1 = {'name': "John", 'age': 20}

person2 = {'name': "Kate", 'age': 32}

print("{0[name]} is {0[age]} years old) and {1[name]} is {1[age]} years old.".\

format(person1, person2))

# John is 20 years old) and Kate is 32 years old.

書式設定する場合は、[位置引数]:[書式設定文字列]の形式にする。位置引数を指定しない場合でも':'は必要。

print("1/4 is {0:f} and 1/5 is {1:e}".format(1/4, 1/5))
print("1/4 is {:f} and 1/5 is {:e}".format(1/4, 1/5))

# 1/4 is 0.250000 and 1/5 is 2.000000e-01
# 1/4 is 0.250000 and 1/5 is 2.000000e-01

print("1/4 is {0:f} and 1/5 is {1:e}".format(1/4, 1/5))

print("1/4 is {:f} and 1/5 is {:e}".format(1/4, 1/5))

# 1/4 is 0.250000 and 1/5 is 2.000000e-01

書式設定文字列

formatメソッド

位置引数を省略して書式設定文字列を各場合{:[書式設定文字列]}のように':'を省略することができない。

文字列

{:[</^/>][width]}で左寄せ／中央ぞろえ／右寄せと、全体の幅widthを指定。

str = "Python"

print("left  :{:<10}".format(str))
print("center:{:^10}".format(str))
print("right :{:>10}".format(str))

# left  :Python
# center:  Python
# right :    Python

str = "Python"

print("left :{:<10}".format(str))

print("center:{:^10}".format(str))

print("right :{:>10}".format(str))

# left :Python

# center: Python

# right : Python

{:[char][</^/>][width]}で空白部分をcharの文字でパディング

print("left  :{:*<10}".format(str))
print("center:{:*^10}".format(str))
print("right :{:*>10}".format(str))

# left  :Python****
# center:**Python**
# right :****Python

print("left :{:*<10}".format(str))

print("center:{:*^10}".format(str))

print("right :{:*>10}".format(str))

# left :Python****

# center:**Python**

# right :****Python

整数

整数の書式は幅の値に'd'を続けて書く。

print("{:*<10d}".format(123))
print("{:*^10d}".format(123))
print("{:*>10d}".format(123))

# 123*******
# ***123****
# *******123

print("{:*<10d}".format(123))

print("{:*^10d}".format(123))

print("{:*>10d}".format(123))

# 123*******

# ***123****

# *******123

整数を2進数、8進数、16進数で表現できる。

print("{:d}".format(255))
print("{:b}".format(255))
print("{:o}".format(255))
print("{:x}".format(255))
print("{:X}".format(255))

# 255
# 11111111
# 377
# ff
# FF

print("{:d}".format(255))

print("{:b}".format(255))

print("{:o}".format(255))

print("{:x}".format(255))

print("{:X}".format(255))

# 255

# 11111111

# 377

# ff

# FF

基数を指定するとき、'#'を前置すると0b、0o、0xが前に付加される。以下の例では、同時に幅も指定している。2進数表現の場合は0bを付加すると設定幅を超えるので、そのまま表示されている。

print("{:#8b}".format(255))
print("{:#8o}".format(255))
print("{:#8x}".format(255))
print("{:#8X}".format(255))

# 0b11111111
#    0o377
#     0xff
#     0XFF

print("{:#8b}".format(255))

print("{:#8o}".format(255))

print("{:#8x}".format(255))

print("{:#8X}".format(255))

# 0b11111111

# 0o377

# 0xff

# 0XFF

浮動小数点

浮動小数点形式の実数の書式は、小数部の桁数だけ指定するときは".3f"のように、幅を設定するときは"10.3f"のように指定する。

print("{:*<10.3f}".format(12.3454))
print("{:*^10.3f}".format(12.3455))
print("{:*>10.3f}".format(12.3456))

# 12.345****
# **12.345**
# ****12.346

print("{:*<10.3f}".format(12.3454))

print("{:*^10.3f}".format(12.3455))

print("{:*>10.3f}".format(12.3456))

# 12.345****

# **12.345**

# ****12.346

固定小数点

固定小数点形式の実数の書式は、小数部の桁数だけ指定するときは".5e"のように、幅を指定するときは"15.5e"のように指定する。

# 固定小数点型
print("{:*<15.3e}".format(1.2344e-10))
print("{:*^15.3e}".format(1.2345e-10))
print("{:*>15.3e}".format(1.2346e-10))

# 1.234e-10******
# ***1.234e-10***
# ******1.235e-10

# 固定小数点型

print("{:*<15.3e}".format(1.2344e-10))

print("{:*^15.3e}".format(1.2345e-10))

print("{:*>15.3e}".format(1.2346e-10))

# 1.234e-10******

# ***1.234e-10***

# ******1.235e-10

符号の表示方法

正の数値に対して'+'を表示させるときは、数値書式の前に'+'をつけ、正の時にスペースを表示させるときには' 'をつける。

print("{:*>10d}".format(123))
print("{:*>10d}".format(-123))
print("{:*>+10d}".format(123))
print("{:*>+10d}".format(-123))
print("{:*> 10d}".format(123))
print("{:*> 10d}".format(-123))

# *******123
# ******-123
# ******+123
# ******-123
# ****** 123
# ******-123

print("{:*>10d}".format(123))

print("{:*>10d}".format(-123))

print("{:*>+10d}".format(123))

print("{:*>+10d}".format(-123))

print("{:*> 10d}".format(123))

print("{:*> 10d}".format(-123))

# *******123

# ******-123

# ******+123

# ******-123

# ****** 123

# ******-123

指定した幅の先頭に符号等を表示し、右寄せの数値との間をパディングする方法。

print("{:*=10.3f}".format(12.345))
print("{:*=10.3f}".format(-12.345))
print("{:*=+10.3f}".format(12.345))
print("{:*= 10.3f}".format(12.345))

# ****12.345
# -***12.345
# +***12.345
#  ***12.345

print("{:*=10.3f}".format(12.345))

print("{:*=10.3f}".format(-12.345))

print("{:*=+10.3f}".format(12.345))

print("{:*= 10.3f}".format(12.345))

# ****12.345

# -***12.345

# +***12.345

# ***12.345

format関数

基数表示

数値の基数を指定して、10進数、2進数、8進数、16進数を表示。16進数は英文字の大文字/小文字を選択可能。

print(format(255, 'd')) #255
print(format(255, 'b')) #11111111
print(format(255, 'o')) #377
print(format(255, 'x')) #ff
print(format(255, 'X')) #FF

print(format(255, 'd')) #255

print(format(255, 'b')) #11111111

print(format(255, 'o')) #377

print(format(255, 'x')) #ff

print(format(255, 'X')) #FF

位置揃え

文字列や数値を固定幅の中で左寄せ、センタリング、右寄せ（センタリングで左右幅が異なるときは、左に1桁寄せられる）。

print(format("Python", '<10s')) #Python
print(format("Python", '^10s')) #  Python
print(format("Python", '>10s')) #    Python

print(format(123, '<6d'))   #123
print(format(123, '^6d'))   # 123
print(format(123, '>6d'))   #   123

print(format("Python", '<10s')) #Python

print(format("Python", '^10s')) # Python

print(format("Python", '>10s')) # Python

print(format(123, '<6d')) #123

print(format(123, '^6d')) # 123

print(format(123, '>6d')) # 123

パディング

数値を固定幅で表示した場合のデフォルトは右寄せ。'[任意の文字]=’で空白をパディング。特にゼロで埋める場合は’=’を省略できる。

print(format(123, '6d'))    #   123
print(format(123, '*=6d'))  #***123
print(format(123, '0=6d'))  #000123
print(format(123, '06d'))   #000123

print(format(123, '6d')) # 123

print(format(123, '*=6d')) #***123

print(format(123, '0=6d')) #000123

print(format(123, '06d')) #000123

2、8、16の基数に対して固定幅で0でパディングする例。

print(format(15, '08b'))    #00001111
print(format(15, '04o'))    #0017
print(format(143, '04x'))   #008f
print(format(143, '04X'))   #008F

print(format(15, '08b')) #00001111

print(format(15, '04o')) #0017

print(format(143, '04x')) #008f

print(format(143, '04X')) #008F

+符号

‘+’を指定すると、正の値の時に+記号がつく。

print(format(456, '+6d'))   #  +456
print(format(-456, '+6d'))  #  -456
print(format(-456, '+06d')) #-00456
# '0+6d'はエラー

print(format(456, '+6d')) # +456

print(format(-456, '+6d')) # -456

print(format(-456, '+06d')) #-00456

# '0+6d'はエラー

カンマ区切り

3桁ごとのカンマ区切り指定。

print(format(123456789, ','))   #123,456,789
print(format(123456789, '15,')) #    123,456,789

1 2	print(format(123456789, ',')) #123,456,789 print(format(123456789, '15,')) # 123,456,789

固定小数点実数

固定小数点の小数部の桁数を’.[桁数]f’で指定する。

print(format(123.456789, '.3f'))  #123.457
print(format(123.456789, '.10f')) #123.4567890000

1 2	print(format(123.456789, '.3f')) #123.457 print(format(123.456789, '.10f')) #123.4567890000

浮動小数点実数

浮動小数点の小数部の桁数を’.[桁数]e’で指定する。

print(format(123.456, '.0e'))   #1.e+02
print(format(123.456, '.1e'))   #1.2e+02
print(format(123.456, '.2e'))   #1.23e+02
print(format(123.456, '.3e'))   #1.235e+02

print(format(123.456, '.0e')) #1.e+02

print(format(123.456, '.1e')) #1.2e+02

print(format(123.456, '.2e')) #1.23e+02

print(format(123.456, '.3e')) #1.235e+02

実数全体の桁数

小数部の桁数ではなく全体の桁数を’.[桁数]g’で指定する。全体の桁数が整数部の桁数以上のときは、固定小数点で表示される。

print(format(123.456, '.0g'))   #1e+02
print(format(123.456, '.1g'))   #1e+02
print(format(123.456, '.2g'))   #1.2e+02
print(format(123.456, '.3g'))   #123
print(format(123.456, '.4g'))   #123.5
print(format(123.456, '.5g'))   #123.46

print(format(123.456, '.0g')) #1e+02

print(format(123.456, '.1g')) #1e+02

print(format(123.456, '.2g')) #1.2e+02

print(format(123.456, '.3g')) #123

print(format(123.456, '.4g')) #123.5

print(format(123.456, '.5g')) #123.46

Python3 – 整数除算と剰余（//, %）

2019-07-22 / tau / 1件のコメント

//演算子

//演算子は、切り捨て除算と言われることが多いが、正確には小数部の切り捨てではなく、除算値を超えない最大の整数となる。これは実数の除算結果にfloorを適用した値と同じで、除算結果が負の時に注意を要する。

import math

print(8/3)
print(8//3)
print(math.floor(8/3))

# 2.6666666666666665
# 2
# 2

print(-7/3)
print(-7//3)
print(math.floor(-7/3))

# -2.3333333333333335
# -3
# -3

import math

print(8/3)

print(8//3)

print(math.floor(8/3))

# 2.6666666666666665

# 2

print(-7/3)

print(-7//3)

print(math.floor(-7/3))

# -2.3333333333333335

# -3

なお、被除数・除数の何れがマイナスかは問わず、計算結果がマイナスかどうかだけによる。

%演算子

%演算子は、引数の剰余(mod)を与える。除数の正負によって挙動が異なる点に注意。

print(13%3)     # 1
print(-13%3)    # 2
print(13%(-3))  # -2
print(-13%(-3)) # -1

print(13%3) # 1

print(-13%3) # 2

print(13%(-3)) # -2

print(-13%(-3)) # -1

除数が正のとき剰余は正となり、除数が負のときは剰余は負となる。

$\begin{array}{lcl} 13 \% 3 = 1 & \Rightarrow & 13 = 3 \times 4 + 1 \\ -13 \% 3 = 2 & \Rightarrow & -13 = 3 \times (-5) + 2 \\ 13 \% (-3) = -2 & \Rightarrow & 13 = -3 \times (-5) - 2 \\ -13 \% (-3) = -1 & \Rightarrow & -13 = -3 \times 4 -1 \end{array}$

Python3 – 組み込み関数

2019-07-21 / tau / コメントする

range関数

zip関数

map関数

Python3 – range関数

2019-07-21 / tau / コメントする

概要

Python3のrange関数は引数で指定した範囲の整数列をrangeオブジェクトで返す。rangeオブジェクトを表示するには、list関数でリスト化する必要がある。

>>> range(0, 5)
range(0, 5)
>>> list(range(0, 5))
[0, 1, 2, 3, 4]

>>> range(0, 5)

range(0, 5)

>>> list(range(0, 5))

[0, 1, 2, 3, 4]

書式

range(end): 0から始まり、1ずつ増加してendに達しない範囲の数列
range(start, end): startから始まり、1ずつ増加してendに達しない範囲の数列
range(start, end, step): startから始まり、stepずつ増加してendに達しない範囲の数列

引数は整数である必要があり、そうでなければエラーとなる。

共通なのは、開始値からステップ値ずつ変化させ、終了値に達する直前までの数列を返す、というもので、ステップ値が正の場合にはstart ≤ 値 < endを、ステップ値が負の場合にはstart ≥ 値 > endを要素とする数列となる。

実行例

引数を1つだけ指定した場合は、0から引数未満の整数列となる。

>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

1 2	>>> list(range(10)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

引数を2つ指定すると、第1引数以上、第2引数未満の整数列となる。

>>> list(range(3, 10))
[3, 4, 5, 6, 7, 8, 9]

1 2	>>> list(range(3, 10)) [3, 4, 5, 6, 7, 8, 9]

引数を3つ指定すると、第1引数から第3引数ずつ増加して第2引数を超える手前までの整数列となる。

>>> list(range(0, 10, 3))
[0, 3, 6, 9]

1 2	>>> list(range(0, 10, 3)) [0, 3, 6, 9]

第3引数を負の数とすると、降順の数列になる。このとき、第2引数の終了値以下になる前までの数列となっていることに注意。

>>> list(range(10, 0, -1))
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> list(range(10, 0, -4))
[10, 6, 2]

>>> list(range(10, 0, -1))

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

>>> list(range(10, 0, -4))

[10, 6, 2]

なお、2つだけ引数を指定して、第1引数＞第2引数としても、降順の数列は得られず、空となる。

>>> list(range(10, 0))
[]

1 2	>>> list(range(10, 0)) []

ユークリッドの互除法

2019-07-15 / tau / コメントする

概要

ユークリッドの互除法(Euclidean Algorithm)は、2つの自然数の最大公約数を求める手順。

2つの自然数 $a, b \; (a \ge b)$ の最大公約数(GCD: greatest common divisor)は、 $b$ と剰余 $r = a \mod b$ の最大公約数に等しいという性質を利用。数を順次割り込んでいき、剰余がゼロとなったときの除数が最大公約数となる。

(1) $}\begin{align*}a \mod b &= r_1 \quad (a \ge b) \\b \mod r &= r_2 \\&\vdots \\r_{n-1} \mod r_n &= 0 \\&\Downarrow \\\gcd(a, b) &= r_n\end{align*}$

証明

以下の余りあり除算を考える。

(2) $\begin{gather*}a \mod b = r \Rightarrow a = bd + r\end{gather*}$

$a, b$ の公約数を $m$ とすると、上式は以下のように変形され、 $m$ は $b$ と $r$ の公約数でもあることがわかる。

(3) $\begin{gather*}a = mp , \quad b = mq \\r = mp - mqd = m(p - qd)\end{gather*}$

一方、 $b, r$ の公約数を $n$ とすると、 $n$ は $a$ と $b$ の公約数であることがわかる。

(4) $\begin{gather*}b = ns , \quad r = nt \\a = nsd + nt = n(sd + t)\end{gather*}$

これより、 $a, b$ の公約数の集合と $b, r$ の公約数の集合は等しく、最大公約数も等しくなる。

(5) $\begin{equation*}a = bd+r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}$

計算例

143と91の最大公約数を求める。

(6) $\begin{align*}&143 \mod 91 = 52 \\&91 \mod 52 = 39 \\&52 \mod 39 = 13 \\&39 \mod 13 = 0 \\&\therefore \gcd(143, 91) = 13\end{align*}$

再帰関数による実装

PythonとCLispの再帰関数による実装例は以下の通り。ただし、第1引数>第2引数を前提としており、エラー処理はしていない。

Python

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

print( gcd(12, 8) )

def gcd(a, b):

if a % b == 0:

return b

else:

return gcd(b, a % b)

print( gcd(12, 8) )

CLisp

(defun mygcd (a b)
	(if (= (mod a b) 0) b (mygcd b (mod a b)))
)

(print (mygcd 18 12))

(defun mygcd (a b)

(if (= (mod a b) 0) b (mygcd b (mod a b)))

)

(print (mygcd 18 12))

最大公約数・最小公倍数

2019-07-13 / tau / コメントする

約数

約数の定義

整数 $N$ の約数(divisor, factor)とは、Nを割り切る整数(余りが生じない除数)。

整数 $m$ が $N$ の約数であるとき、 $m|N$ と表し、ある整数 $a$ に対して $N=ma$ が成り立つことでもある。一般には自然数あるいは0以上の整数で考える。

通常は $m \ne 0$ の条件を課すが、0も含める場合は、 $N=0$ の時に限り0が約数になる。

例えば12の約数は、以下の6個。

(1) $\begin{align*}&12 \div 1 = 12 \\&12 \div 2 = 6 \\&12 \div 3 = 4 \\&12 \div 4 = 3 \\&12 \div 6 =2 \\&12 \div 12 = 1\end{align*}$

効率的な約数の求め方

$m|N$ であるとき、 $\frac Nm|N$ である。これより $m = \frac Nm$ として、 $\sqrt N$ 以下の約数 $m_i$ を求め、あとは $N/m_i$ を計算すれば、手間が半分で済む。

$N$ が平方数の場合は $\sqrt N$ も約数となり、約数の総数は奇数個、平方数でない場合は偶数異なる。

0、1の約数

0の約数は $0 = ma$ となる整数 $m$ であり、0以上の全ての整数である。

1の約数は $1 = ma$ となる整数 $m$ であり、1のみ。

1は全ての整数の約数。

素数の約数

素数の定義が「1と自身以外に約数を持たない数」なので、約数は2個。

公約数

2つの数の公約数は、それらの最大公約数の約数。

0、1との公約数

$a$ と1の公約数は1のみ。

$a$ と0の公約数は、 $a$ の約数全て(0の約数は0以上の全ての整数)。

公約数と剰余

$a \mod b = r$ のとき、 $a, b$ の公約数は $b, r$ の公約数でもある。

最大公約数

2つの数の最大公約数(greatest common divisor)を、 $\gcd(a, b)$ のように表す。

最大公約数を求める手順として、にユークリッドの互除法がある。

0、1との最大公約数

(2) $\begin{gather*}\gcd(a, 0) = a \\\gcd(a, 1) = 1\end{gather*}$

最大公約数と剰余

被除数と除数の最大公約数は、除数と剰余の最大公約数でもある。

(3) $\begin{equation*}a \mod b = r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}$

倍数

倍数(multiple)とは、ある数 $a$ (整数に限らない)を整数倍した数である。

(4) $\begin{gather*}\cdots \; -3a,\; -2a,\; -a,\; 0,\; a,\; 2a,\; 3a,\; \cdots\end{gather*}$

0の倍数は0のみ
0はすべての数の倍数
すべての数は自分自身の倍数
すべての整数は1と-1の倍数

最小公倍数

最小公倍数(least common multiple)とは、2つの整数の公倍数のうち、正で最小のもの。

たとえば36と56の最小公倍数は504。

最大公約数と最小公倍数の積

2つの数 $a, b$ の積は、それらの最大公約数と最小公倍数の積に等しい。

(5) $\begin{equation*}ab = \gcd(a, b) \cdot \operatorname{lcm}(a, b)\end{equation*}$

Python3 – mathモジュール

2019-07-13 / tau / コメントする

使い方

数学関数を使うためのモジュールで、importし、各定数・関数について、math.[定数名・関数名]として使う。

>>> import math
>>> math.sqrt(2)
1.4142135623730951

>>> import math

>>> math.sqrt(2)

1.4142135623730951

関数群

主なもの

定数

pi, e: 円周率、自然対数の底
inf: 浮動小数点の正の無限大。負の無限大は-math.inf。
nan: 浮動小数点の非数NaN。

数論関数

ceil(x): xの天井(x以上の最小の整数)。
floor(x): xの床(x以下の最大の整数)。
fabs(x): xの絶対値。
fmod(x, y): $x \mod y$ を返す。浮動小数点の場合はx % yよりこちらを使う。
gcd(x, y): xとyの最大公約数。gcd(0.0, 0.0)は0を返す。
isfinite(x): xが無限でもNaNでもない時にTrueを返す。
ifinf(x): xが正の無限大か負の無限大の時にTrueを返す。
isnan(x): xがNaNの時にTrueを返す。

指数・対数関数

sqrt(n): nの平方根
pow(x, y): xのy乗( $x^y$ )。pow(1.0, x)、pow(x, 0.0)は常に1.0を返す。
exp(x): $e^x$ 。
expm1(n): $e^x - 1$ 。桁落ちに対して最大精度で計算。
log2(x), log10(x), log(x [,b]): それぞれ2、10、bを底とする対数関数。3番目の関数でbを省略した場合は自然対数 $\ln x$
log1p(x): $1+\log x$

を返す。ゼロに近いxに対して正確になるよう計算される。

三角関数

sin(x), cos(x), tan(x): 三角関数。
asin(x), acos(x), atan(x): 逆三角関数
atan2(y, x): [latex]\tan^{^1}を返すが、4つの象限に対する符号から、[latex]-\pi \sim \pi[/lates]の値を返す。
degrees(r), radians(d): ラジアンから度、度からラジアンへの変換。