Last active
August 29, 2015 14:18
-
-
Save nightuser/dfe4626cbe99528060e1 to your computer and use it in GitHub Desktop.
Sympy bad performance with polynomials
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# -*- coding: utf-8 -*- | |
import numpy as np | |
from sympy import Poly, Symbol | |
from scipy.signal import fftconvolve | |
x = Symbol('x') | |
k = 19937 | |
# k = 12 | |
jump = 1234567 | |
# jump = 21 | |
# phi is minimal polynomial | |
phi = Poly(np.append(1, np.random.random_integers(0, 1, k - 1)), x, modulus=2) | |
# print(phi) | |
# # it's big initial polynomial, which we'd like to reduce | |
# f = Poly(x ** jump, x, modulus=2) | |
# # print(f) | |
# # g is resulted polynomial | |
# g = f.rem(phi) | |
# print(g) | |
def my_mul(f, g): | |
return fftconvolve(f, g) % 2 | |
def my_rem(f, g): | |
f = np.array(f, dtype=np.int) | |
g = np.array(g, dtype=np.int) | |
df = len(f) | |
dg = len(g) | |
shift = df - dg + 1 | |
for i in range(shift): | |
if f[i] == 1: | |
f[i:i + dg] ^= g | |
return f[shift:] | |
def my_foo(power, phi, degree): | |
# print('I\'m in %d' % power) | |
if power < degree: | |
return np.append(1, np.zeros(power, dtype=np.int)) | |
temp = my_foo(power // 2, phi, degree) | |
result = np.array(my_mul(temp, temp), dtype=np.int) | |
result = my_rem(result, phi) | |
if power % 2 == 1: | |
result = my_rem(my_mul(result, [1, 0]), phi) | |
return result | |
g1l = my_foo(jump, np.array(phi.all_coeffs()), phi.degree()) | |
print(g1l) | |
g1 = Poly.from_list(g1l, x, modulus=2) | |
# print(g1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment