Skip to content

galois v0.0.26
Compare
Choose a tag to compare
@github-actions github-actions released this 30 Mar 22:46
· 0 commits to 895053a7701ba3200b4a5708cbff05fe33d2ef07 since this release
v0.0.26
53c622e

Released March 30, 2022

Breaking Changes

  • Removed the Poly.copy() method as it was unnecessary. Polynomial objects are immutable. Use g = f wherever g = f.copy() was previously used. (#320)
  • Disabled true division f / g on polynomials since true division was not actually being performed. Use floor division f // g moving forward. (#312)
  • Refactored irreducible_polys() to return an iterator rather than list. Use list(irreducible_polys(...)) to obtain the previous output. (#325)
  • Refactored primitive_polys() to return an iterator rather than list. Use list(primitive_polys(...)) to obtain the previous output. (#325)
  • Refactored primitive_root() and primitive_roots(). (#325)
    • Added method keyword argument and removed reverse from primitive_root(). Use primitive_root(..., method="max") where primitive_root(..., reverse=True) was previously used.
    • Refactored primitive_roots() to now return an iterator rather than list. Use list(primitive_roots(...)) to obtain the previous output.
  • Refactored primitive_element() and primitive_elements(). (#325)
    • Added method keyword argument to primitive_element().
    • Removed start, stop, and reverse arguments from both functions.
  • Search functions now raise RuntimeError instead of returning None when failing to find an answer. This applies to primitive_root(), pollard_p1(), and pollard_rho(). (#312)

Changes

  • The galois.Poly class no longer returns subclasses BinaryPoly, DensePoly, and SparsePoly. Instead, only Poly classes are returned. The classes otherwise operate the same. (#320)
  • Made Galois field array creation much more efficient by avoiding redundant element verification. (#317)
    • Scalar creation is 625% faster. 
      In [2]: GF = galois.GF(3**5)

# v0.0.25
In [3]: %timeit GF(10)
21.2 µs ± 181 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [3]: %timeit GF(10)
2.88 µs ± 8.03 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
    • Nested iterable array creation is 150% faster. 
      # v0.0.25
In [4]: %timeit GF([[10, 20], [30, 40]])
53.6 µs ± 436 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [4]: %timeit GF([[10, 20], [30, 40]])
20.9 µs ± 11.2 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
    • Nested iterable (with strings) array creation is 25% faster. 
      # v0.0.25
In [5]: %timeit GF([[10, "2x^2 + 2"], ["x^3 + x", 40]])
67.9 µs ± 910 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [5]: %timeit GF([[10, "2x^2 + 2"], ["x^3 + x", 40]])
54.7 µs ± 16.3 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
  • Made array arithmetic 35% faster by avoiding unnecessary element verification of outputs. (#309) 
    In [2]: GF = galois.GF(3**5)

In [3]: x = GF.Random((10_000), seed=1)

In [4]: y = GF.Random((10_000), seed=2)

# v0.0.25
In [6]: %timeit x * y
39.4 µs ± 237 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# v0.0.26
In [6]: %timeit x * y
28.8 µs ± 172 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
  • Made polynomial arithmetic over binary fields 10,900% faster by making polynomial creation from integers much more efficient. (#320) 
    In [5]: f
Out[5]: Poly(x^10 + x^9 + x^6 + x^5 + x^3 + x, GF(2))

In [6]: g
Out[6]: Poly(x^10 + x^7 + x^4 + 1, GF(2))

# v0.0.25
In [7]: %timeit f * g
283 µs ± 6.31 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

# v0.0.26
In [7]: %timeit f * g
2.57 µs ± 54.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
  • JIT-compiled polynomial modular exponentiation. (#306)
    • Binary fields are 14,225% faster. 
      In [5]: f
Out[5]: Poly(x^10 + x^9 + x^6 + x^5 + x^3 + x, GF(2))

In [6]: g
Out[6]: Poly(x^5 + x^2, GF(2))

# v0.0.25
In [7]: %timeit pow(f, 123456789, g)
19.2 ms ± 206 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

# v0.0.26
In [7]: %timeit pow(f, 123456789, g)
134 µs ± 2.21 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
    • Other fields are 325% faster. 
      In [6]: f
Out[6]: Poly(242x^10 + 216x^9 + 32x^8 + 114x^7 + 230x^6 + 179x^5 + 5x^4 + 124x^3 + 96x^2 + 159x + 77, GF(3^5))

In [7]: g
Out[7]: Poly(183x^5 + 83x^4 + 101x^3 + 203x^2 + 68x + 2, GF(3^5))

# v0.0.25
In [8]: %timeit pow(f, 123456789, g)
17.6 ms ± 61.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# v0.0.26
In [8]: %timeit pow(f, 123456789, g)
4.19 ms ± 11.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  • Made irreducible and primitive polynomial search routines faster. (#306, #309, #317, #320)
    • Binary fields are 1,950% faster. 
      # v0.0.25
In [2]: %time f = galois.primitive_poly(2, 14)
CPU times: user 296 ms, sys: 70.9 ms, total: 367 ms
Wall time: 313 ms

# v0.0.26
In [2]: %time f = galois.primitive_poly(2, 14)
CPU times: user 14.7 ms, sys: 5.53 ms, total: 20.2 ms
Wall time: 15.3 ms
    • Other fields are 400% faster. 
      # v0.0.25
In [5]: %time f = galois.primitive_poly(7, 10)
CPU times: user 2.22 s, sys: 0 ns, total: 2.22 s
Wall time: 2.21 s

# v0.0.26
In [4]: %time f = galois.primitive_poly(7, 10)
CPU times: user 442 ms, sys: 0 ns, total: 442 ms
Wall time: 439 ms
  • Made FieldArray.Vector() 100% faster and FieldArray.vector() 25% faster by making better use of divmod() when converting between integer and vector representations. (#322)

Contributors

Commits

53c622e Version bump to 0.0.26
895053a Add release notes for v0.0.26
348c61a Update performance pages with latest speeds
429f0d8 Remove jinja2 pin since it was resolved in sphinx-immaterial upstream
810a3de Add "See Also" sections to docstrings
6ab4a49 Refactor primitive_element() and primitive_elements()
1273d16 Add private constructor Poly._PolyLike()
fc52679 Refactor primitive_roots() to return an iterator
4985853 Memoize euler_phi()
645f755 Refactor primitve_polys() to return an iterator
30d554f Refactor irreducible_polys() to return an iterator
7d9f642 Raise RuntimeError rather than return None for pollard_rho()
7b3711a Raise RuntimeError rather than return None for pollard_p1()
9a38498 Ensure dtype=object arrays always have int objects, even after assignment
1d30fb9 Better use of divmod() in int/poly conversion for GF(p^m) fields
a055e5b Speed-up Vector() and vector() using better use of divmod()
1a81be4 Adjust dense/sparse poly arithmetic threshold
864c977 Refactor Poly inheritance of BinaryPoly, DensePoly, and SparsePoly
cf84272 Remove brackets around the 0-th degree coefficient in poly strings
3ebc562 Make poly/int conversion more efficient
05ec7b4 Remove Poly.copy() method
a454532 Pin pylint before v2.13.0
b734de3 Speed-up array creation, especially 0-D arrays
74305d1 Ignore dtype check with performing an internal "cheap view"
c2e0404 Avoid jinja2 bug until fixed in sphinx-immaterial
1c99193 Fix typo in Getting Started guide
8bbb1ee Disable true division on polynomials
d86609b Fix NumPy capitalization in comments
a9e1f9b Remove function that no longer exists from reference list
5354a1f Enable arbitarily-large exponents to JIT-compiled poly pow()
b6347b6 Avoid array element range verification for internal .view(GF) conversions
9b1849d Cleanup FieldClass.display() context manager
fb20569 Modify CSS rules so sphinx-design tabs match the theme better
5869373 Fix BibTeX label
0999e4e Fix typo in Galois LFSR step docstring
a7624fc JIT compile polynomial modular exponentiation
dc5dca8 JIT compile separate polynomial div and mod functions
fa43cc1 Save 1 unnecessary calculation in poly divmod

Assets 2
Loading