Numpy gcd Funktion

Question

Funktioniert numpy eine gcd Funktion irgendwo in seiner Struktur von Modulen?

Ich bin bewusst, aber dachte, ein numpy gleichwertig möglicherweise schneller und besser arbeiten mit numpy Datentypen.

Ich konnte nichts auf Google außer diesem link aufdecken, das scheint veraltet zu sein und ich weiß nicht, wie ich auf die _gcd Funktion zugreifen würde, die es schlägt, existiert.

Naiv versuchen:

np.gcd 
np.euclid 

hat sich für mich nicht funktioniert ...

Answer 1

Sie es selbst schreiben:

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 

Hier ist der Code ist das Ergebnis und die Geschwindigkeit zu testen:

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

Es scheint, gibt es keine gcd Funktion noch in numpy. Es gibt jedoch eine gcd function in fractions module. Wenn Sie gcd auf numpy Arrays ausführen müssen, können Sie eine ufunc mit bauen:

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

Answer 3

öffentliche Ankündigung für jedermann mit Python 3.5

from math import gcd 
gcd(2, 4) 

Und wenn Sie es selbst in einem Einzeiler schreiben wollen:

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

Answer 4

Falls das gewünschte Ergebnis ist kein Element weise gcd sondern die ggT aller Zahlen im Array, Sie kann den folgenden Code verwenden.

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 

Je nach Anwendungsfall kann es schneller sein, um die Sortierschritt a = np.unique(a) wegzulassen.

Eine Alternative (vielleicht elegantere, aber langsamer) Implementierung ufuncs Verwendung ist

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]