NumPyで最大公約数・最小公倍数を算出・取得
NumPyで最大公約数（greatest common divisor）・最小公倍数（least common multiple）を算出するにはnumpy.gcd(), numpy.lcm()を使う。
基本的には2つのNumPy配列ndarrayの要素ごとの最大公約数・最小公倍数の算出になるが、reduce()を利用して複数のnumpy.ndarrayやスカラー値を処理したり、1つのnumpy.ndarrayの全要素に対して最大公約数・最小公倍数を算出したりすることも可能。
以下の内容について説明する。
- 最大公約数:
numpy.gcd()- 基本的な使い方
- 形状
shapeが異なる場合
- 最小公倍数:
numpy.lcm() reduce()による集約- 複数のオブジェクトに対して処理
- 1つのNumPy配列
ndarrayの要素に対して処理
なお、numpy.gcd(), numpy.lcm()いずれもNumPy1.15.0で追加された関数。
AtCoderでも使用可能。
先にサンプルコードをいくつか載せておく。
import numpy as np
a = np.array([0, 2, 3, 6])
b = np.array([3, 4, 5, 15])
print(np.gcd(a, b))
# [3 2 1 3]
print(np.gcd.reduce([6, 9, 12, 15]))
# 3
Pythonの標準ライブラリを使って最大公約数・最小公倍数を算出することもできる。以下の記事を参照。
- 関連記事: Pythonで最大公約数と最小公倍数を算出・取得
最大公約数: numpy.gcd()
基本的な使い方
numpy.gcd()の第一引数、第二引数に対象とするnumpy.ndarrayを指定する。
要素ごとに最大公約数が算出され、numpy.ndarrayで返される。
import numpy as np
a = np.array([0, 2, 3, 6])
b = np.array([3, 4, 5, 15])
print(np.gcd(a, b))
# [3 2 1 3]
print(type(np.gcd(a, b)))
# <class 'numpy.ndarray'>
上の例のように、片方の値が0の場合は他方の値が返される。
リストでもOK。ただし、返り値はnumpy.ndarray。
l_a = [0, 2, 3, 6]
l_b = [3, 4, 5, 14]
print(np.gcd(l_a, l_b))
# [3 2 1 2]
print(type(np.gcd(l_a, l_b)))
# <class 'numpy.ndarray'>
スカラー値でもOK。この場合はnumpy.ndarrayではなく値そのものが返される。
print(np.gcd(6, 15))
# 3
print(type(np.gcd(6, 15)))
# <class 'numpy.int64'>
複数のnumpy.ndarrayやリスト、スカラー値に対して最大公約数を算出したい場合はreduce()を使う。後述。
形状shapeが異なる場合
NumPyにおいて、形状shapeが異なるnumpy.ndarray同士の演算では、可能な場合はブロードキャストによって形状が揃えられる。
- 関連記事: NumPyのブロードキャスト（形状の自動変換）
a_2d = np.array([[0, 2, 3, 6], [0, 2, 3, 6]])
print(a_2d)
# [[0 2 3 6]
# [0 2 3 6]]
print(b)
# [ 3 4 5 15]
print(a_2d + b)
# [[ 3 6 8 21]
# [ 3 6 8 21]]
numpy.gcd()においてもブロードキャストが行われる。
print(np.gcd(a_2d, b))
# [[3 2 1 3]
# [3 2 1 3]]
ブロードキャストできない場合はエラーとなる。
a_mismatch = np.array([0, 1, 2])
# print(np.gcd(a_mismatch, b))
# ValueError: operands could not be broadcast together with shapes (3,) (4,)
第一引数、第二引数のいずれかがスカラー値でもOK。各要素とスカラー値との最大公約数が返される。
print(np.gcd(a, 15))
# [15 1 3 3]
print(np.gcd(15, a))
# [15 1 3 3]
最小公倍数: numpy.lcm()
numpy.lcm()もnumpy.gcd()と同じ使い方。サンプルコードのみをいくつか示す。
基本的な使い方。
a = np.array([0, 2, 3, 6])
b = np.array([3, 4, 5, 15])
print(np.lcm(a, b))
# [ 0 4 15 30]
print(type(np.lcm(a, b)))
# <class 'numpy.ndarray'>
print(np.lcm(6, 15))
# 30
上の例のように、片方の値が0の場合は0が返される。
形状shapeが異なる場合。
a_2d = np.array([[0, 2, 3, 6], [0, 2, 3, 6]])
print(a_2d)
# [[0 2 3 6]
# [0 2 3 6]]
print(np.lcm(a_2d, b))
# [[ 0 4 15 30]
# [ 0 4 15 30]]
print(np.lcm(a, 15))
# [ 0 30 15 30]
numpy.gcd()と同じく、引数にリストを指定することも可能。例は省略。
reduce()による集約
numpy.gcd(), numpy.lcm()のような、2つのオブジェクト（numpy.ndarrayやスカラー値など）を引数とするユニバーサル関数ufuncではreduce()というメソッドが使える。
reduce()にリストなどのイテラブルを指定するとufuncが要素に対して累積的に適用され結果が集約される。
ufunc.reduce(x)は基本的には... ufunc(ufunc(ufunc(x[0], x[1]), x[2]), x[3]) ...に等しい。
これを利用すると、複数のオブジェクト（numpy.ndarrayやスカラー値など）を処理したり、1つのnumpy.ndarrayの全要素の最大公約数・最小公倍数を算出したりすることができる。
複数のオブジェクトに対して処理
numpy.gcd()を例とすると以下のようになる。複数のnumpy.ndarrayを要素とするリストを引数に指定する。例は3つだけだが、それ以上でも同じ。
a = np.array([0, 2, 3, 6])
b = np.array([3, 4, 5, 15])
c = np.array([6, 8, 9, 9])
print(np.gcd.reduce([a, b, c]))
# [3 2 1 3]
以下のような処理と同じ。
print(np.gcd(np.gcd(a, b), c))
# [3 2 1 3]
numpy.lcm()でも同様。以下、例は基本的にnumpy.gcd()だが、numpy.lcm()でも同じように処理できる。
print(np.lcm.reduce([a, b, c]))
# [ 0 8 45 90]
複数のスカラー値に対する処理も同様。
print(np.gcd.reduce([6, 9, 12, 15]))
# 3
reduce()の引数にはリストなどのイテラブルを指定する必要がある。リストではなくタプルなどでもいいが、各オブジェクトをそのままカンマ区切りで指定するとエラー。
print(np.gcd.reduce((a, b, c)))
# [3 2 1 3]
# print(np.gcd.reduce(a, b, c))
# TypeError: data type not understood
reduce()を使うと関数が繰り返し適用されると書いたが、各オブジェクトの形状が異なる場合、NumPy1.16.4時点ではエラーになった。元の関数（ここではnumpy.gcd()）を繰り返すと問題ない。
a_2d = np.array([[0, 2, 3, 6], [0, 2, 3, 6]])
print(a_2d)
# [[0 2 3 6]
# [0 2 3 6]]
# print(np.gcd.reduce([a, b, a_2d]))
# ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()
print(np.gcd(np.gcd(a, b), a_2d))
# [[3 2 1 3]
# [3 2 1 3]]
numpy.ndarrayとスカラー値が混在する場合も同じ。
# print(np.gcd.reduce([a, b, 9]))
# ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()
print(np.gcd(np.gcd(a, b), 9))
# [3 1 1 3]
ソースコードを追っていないのでバグなのかこういう仕様なのかは未確認だが要注意。
1つのNumPy配列ndarrayの要素に対して処理
複数のスカラー値に対する例と同様に、1次元のnumpy.ndarrayをreduce()の引数に指定すると、要素が順番に処理される。
numpy.gcd(), numpy.lcm()においては、全要素に対する最大公約数・最小公倍数が返される。
a_1d = np.array([4, 6, 12])
print(np.gcd.reduce(a_1d))
# 2
print(np.lcm.reduce(a_1d))
# 12
多次元配列の場合、最初の軸（axis=0）に対して順に処理される。二次元配列だと行ごと。
a_2d = np.array([[4, 6, 12], [2, 12, 16]])
print(a_2d)
# [[ 4 6 12]
# [ 2 12 16]]
print(np.gcd.reduce(a_2d))
# [2 6 4]
print(np.gcd(a_2d[0], a_2d[1]))
# [2 6 4]
全要素に対する最大公約数・最小公倍数を取得したい場合はravel()やflatten()で1次元化する。
print(a_2d.ravel())
# [ 4 6 12 2 12 16]
print(np.gcd.reduce(a_2d.ravel()))
# 2
print(np.lcm.reduce(a_2d.ravel()))
# 48