numpy.convolve로 다항식을 곱하면 잘못된 결과가 반환됩니다.

Question

numpy.convolve 함수를 사용하여 두 다항식을 곱하려고합니다. 나는 이것이 정말로 쉬울 것이라고 생각했지만 항상 올바른 제품을 반환하지는 않는다는 것을 알아 냈습니다.

곱셈의 구현은 매우 간단합니다 :

def __mul__(self, other): 
    new = ModPolynomial(self._mod_r, self._mod_n) 
    try: 
     new_coefs = np.convolve(self._coefs, other._coefs) 
     new_coefs %= self._mod_n    # coefficients in Z/nZ 
     new._coefs = new_coefs.tolist() 
     new._degree = self._finddegree(new._coefs) 
    except AttributeError: 
     new._coefs = [(c * other) % self._mod_n for c in self._coefs] 
     new._degree = self._finddegree(new._coefs) 
    new._mod()  #the polynomial mod x^r-1 
    return new 

잘못된 결과를 제공 예 : 내가와 정확히 같은 알고리즘을 사용하기 때문에

>>> N = 5915587277 
>>> r = 1091 
>>> pol = polynomials.ModPolynomial(r,N) 
>>> pol += 1 
>>> r_minus_1 = (pol**(r-1)).coefficients 
>>> # (x+1)^r = (x+1)^(r-1) * (x+1) = (x+1)^(r-1) * x + (x+1)^(r-1) * 1 
... shifted = [r_minus_1[-1]] + list(r_minus_1[:-1]) #(x+1)^(r-1) * x mod x^r-1 
>>> res = [(a+b)%N for a,b in zip(shifted, r_minus_1)] 
>>> tuple(res) == tuple((pol**r).coefficients) 
False 

지수는 문제가, 아마입니다 정확한 결과를주는 다른 다항식 구현. 그리고 "정확히 똑같은 알고리즘"을 사용하면 numpy.convolve을 사용하는 다항식 클래스가 __mul__ 및 _mod() [_mod()에있는 다른 클래스의 서브 클래스이므로 다른 _mod() 메서드를 호출 한 다음 해당 용어에 대한 계수를 0으로 삭제하면됩니다. 다항식 차수보다 크다].

이 실패하는의 다른 예 :

>>> pol = polynomials.ModPolynomial(r, N) #r,N same as before 
>>> pol += 1 
>>> (pol**96).coefficients 
(1, 96, 4560, 142880, 3321960, 61124064, 927048304, 88017926, 2458096246, 1029657217, 4817106694, 4856395617, 384842111, 2941717277, 5186464497, 5873440931, 526082533, 39852453, 1160839201, 1963430115, 3122515485, 3694777161, 1571327669, 5827174319, 2249616721, 501768628, 5713942687, 1107927924, 3954439741, 1346794697, 4091850467, 2576431255, 94278252, 5838836826, 3146740571, 1898930862, 4578131646, 1668290724, 2073150016, 2424971880, 1386950302, 1658296694, 5652662386, 1467437114, 2496056685, 1276577534, 4774523858, 5138784090, 4607975862, 5138784090, 4774523858, 1276577534, 2496056685, 1467437114, 5652662386, 1658296694, 1386950302, 2424971880, 2073150016, 1668290724, 4578131646, 1898930862, 3146740571, 5838836826, 94278252, 2576431255, 4091850467, 1346794697, 3954439741, 1107927924, 5713942687, 501768628, 2249616721, 5827174319, 1571327669, 3694777161, 3122515485, 1963430115, 1160839201, 39852453, 526082533, 5873440931, 5186464497, 2941717277, 384842111, 4856395617, 4817106694, 1029657217, 2458096246, 88017926, 927048304, 61124064, 3321960, 142880, 4560, 96, 1) 
#the correct result[taken from wolframalpha]: 
(1, 96, 4560, 142880, 3321960, 61124064, 927048304, 88017926, 2458096246, 1029657217, 4817106694, 4856395617, 384842111, 2941717277, 5186464497, 5873440931, 526082533, 39852453, 1160839201L, 1963430115L, 3122515485L, 3694777161L, 1571327669L, 5827174319L, 1209974072L, 5377713256L, 4674300038L, 68285275L, 2914797092L, 307152048L, 3052207818L, 1536788606L, 4970222880L, 4799194177L, 2107097922L, 859288213L, 4578131646L, 1668290724L, 1033507367L, 1385329231L, 347307653L, 618654045L, 4613019737L, 427794465L, 1456414036L, 236934885L, 3734881209L, 4099141441L, 3568333213L, 4099141441L, 3734881209L, 236934885L, 1456414036L, 427794465L, 4613019737L, 618654045L, 347307653L, 1385329231L, 1033507367L, 1668290724L, 4578131646L, 859288213L, 2107097922L, 4799194177L, 4970222880L, 1536788606L, 3052207818L, 307152048L, 2914797092L, 68285275L, 4674300038L, 5377713256L, 1209974072L, 5827174319L, 1571327669L, 3694777161L, 3122515485L, 1963430115L, 1160839201L, 39852453, 526082533, 5873440931, 5186464497, 2941717277, 384842111, 4856395617, 4817106694, 1029657217, 2458096246, 88017926, 927048304, 61124064, 3321960, 142880, 4560, 96, 1) 

만 appeard "큰 숫자"에 잘못된 결과를, 또한 지수가 "큰"해야는 [I은 지수 <와 예를 찾을 수 없습니다 96].

나는 왜 이런 일이 발생 하는지를 알지 못합니다. 나는 numpy.convolve을 사용하고 있는데, 다른 질문에서 제안 되었기 때문에 나는 접근 방식의 속도를 수치적인 접근 방식과 비교하려고하고있다. 어쩌면 내가 잘못된 방법으로 numpy.convolve을 사용하고 있습니까?

나중에 더 정확한 디버깅을 시도하고 정확히 어디에서 문제가 발생하는지 이해하려고합니다.

Answer 1

NumPy는 fixed-size numeric data types의 배열에서 빠른 작업을 구현하는 라이브러리입니다. 임의 정밀도 산술을 구현하지 않습니다. 따라서 여기에서 볼 수있는 것은 정수 오버 플로우입니다. NumPy는 계수를 64 비트 정수로 나타내며이 값이 충분히 크면 numpy.convolve으로 오버플로합니다. 당신이 임의 정밀도 정수 산술 필요한 경우

>>> import numpy 
>>> a = numpy.convolve([1,1], [1,1]) 
>>> type(a[0]) 
<type 'numpy.int64'> 

, 당신은 파이썬의 임의 정밀도의 정수를 사용할 수 있도록 자신의 회선을 구현해야합니다. 예를 들어,

def convolve(a, b): 
    """ 
    Generate the discrete, linear convolution of two one-dimensional sequences. 
    """ 
    return [sum(a[j] * b[i - j] for j in range(i + 1) 
       if j < len(a) and i - j < len(b)) 
      for i in range(len(a) + len(b) - 1)] 

>>> a = [1,1] 
>>> for i in range(95): a = convolve(a, [1,1]) 
... 
>>> from math import factorial as f 
>>> all(a[i] == f(96)/f(i)/f(96 - i) for i in range(97)) 
True 

Answer 2

속도는 (귀하의 경우와 같이) 가 dtype=object으로 회선을 반복 수행하는 문제의 경우, 당신은 numpy.convolve보다는 karatsuba 모듈을 사용하는 것이 좋습니다. 상위 오브젝트 (예 : dtype=object)를 사용하기위한 것이지만, 컨볼 루션을 사전 계산하기 위해 계획에 의존합니다. 단일 컨볼 루션에는 쓸모가 없지만 많은 유사한 것들이 필요하다면 매우 효율적입니다.