Numpy funkcja gcd

Question

Czy numpy ma funkcję gcd gdzieś w swojej strukturze modułów?

Jestem świadomy fractions.gcd, ale uważam, że odpowiednik numpy może być potencjalnie szybszy i lepiej pracować z numpy typami danych.

Nie mogę znaleźć niczego w Google innym niż ten link, który wydaje się nieaktualny i nie wiem, w jaki sposób uzyskać dostęp do funkcji _gcd, która sugeruje, że istnieje.

Naiwnie starając:

np.gcd 
np.euclid 

nie pracował dla mnie ...

Answer 1

można napisać samemu:

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 

Oto kod, aby sprawdzić wynik i szybkość:

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

Wydaje się, że ma jeszcze gcd funkcja w numpy. Istnieje jednak gcd function in fractions module. Jeśli trzeba wykonać gcd na numpy tablic, można zbudować ufunc używając go:

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

Answer 3

zapowiedź usługi publiczne dla wszystkich osób korzystających z Pythona 3.5

from math import gcd 
gcd(2, 4) 

A jeśli chcesz go napisać siebie w jednej wkładki:

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

Answer 4

W przypadku pożądany rezultat nie jest NWD elementem mądry ale raczej GCD wszystkich liczb w tablicy, ty może użyć poniższego kodu.

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 

W zależności od przypadku zastosowania, może być szybciej pominąć etap sortowania a = np.unique(a).

Alternatywnym (może bardziej elegancki, ale wolniej) realizacja za pomocą ufuncs jest

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]