python - numpy gcd 関数

Question

モジュールの構造のどこかに機能がありますかnumpy?gcd

私は知っていますが、同等のものがおそらくより速く、データ型でよりうまく機能するfractions.gcdと考えました。numpynumpy

古いと思われるこのリンク以外に、グーグルで何かを発見することができず、_gcdそれが示唆する機能にアクセスする方法がわかりません。

素朴にしようとしている：

np.gcd
np.euclid

私のために働いていません...

Answer 1

自分で書くことができます：

def numpy_gcd(a, b):
    a, b = np.broadcast_arrays(a, b)
    a = a.copy()
    b = b.copy()
    pos = np.nonzero(b)[0]
    while len(pos) > 0:
        b2 = b[pos]
        a[pos], b[pos] = b2, a[pos] % b2
        pos = pos[b[pos]!=0]
    return a

結果と速度をテストするコードは次のとおりです。

In [181]:
n = 2000
a = np.random.randint(100, 1000, n)
b = np.random.randint(1, 100, n)
al = a.tolist()
bl = b.tolist()
cl = zip(al, bl)
from fractions import gcd
g1 = numpy_gcd(a, b)
g2 = [gcd(x, y) for x, y in cl]
print np.all(g1 == g2)

True

In [182]:
%timeit numpy_gcd(a, b)

1000 loops, best of 3: 721 us per loop

In [183]:
%timeit [gcd(x, y) for x, y in cl]

1000 loops, best of 3: 1.64 ms per loop

Answer 2

にはgcdまだ機能がないようnumpyです。ただし、fractions モジュールには gcd 関数があります。gcd配列で実行する必要がある場合は、それを使用してnumpy構築できます。ufunc

gcd = numpy.frompyfunc(fractions.gcd, 2, 1)

Answer 3

目的の結果が要素単位の gcd ではなく、配列内のすべての数値の gcd である場合は、次のコードを使用できます。

import numpy as np
from math import gcd as mathgcd

def numpy_set_gcd(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")

    gcd = a[0]
    for i in a[1:]:
        gcd = mathgcd(i, gcd)
        if gcd == 1:
            return 1 

    return gcd

ユース ケースによっては、並べ替え手順を省略した方が高速な場合がありますa = np.unique(a)。

ufuncs を使用した代替の (おそらくより洗練されているが遅い) 実装は次のとおりです。

import numpy as np
from math import gcd as mathgcd
npmathgcd = np.frompyfunc(mathgcd, 2, 1)

def numpy_set_gcd2(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")
    npmathgcd.at(a[1:], np.arange(a.size-1), a[:-1])
    return a[-1]