Performance testing

import numpy as np

import galois

GFp_small = galois.GF_factory(31, 1)
GFp_large = galois.GF_factory(2267, 1)

def construct_arrays(GF, N):
    order = GF.order

    a = np.random.randint(0, order, N, dtype=int)
    b = np.random.randint(0, order, N, dtype=int)

    ga = GF(a)
    gb = GF(b)

    return a, b, ga, gb, order

def pure_python_add(a, b, modulus):
    c = np.zeros(a.size, dtype=a.dtype)
    for i in range(a.size):
        c[i] = (a[i] + b[i]) % modulus
    return c

def pure_python_exp(a, b, order):
    c = np.ones(a.size, dtype=a.dtype)
    for i in range(a.size):
        for _ in range(0, b):
            c[i] = (c[i] * a[i]) % order
    return c

def numpy_exp(a, b, order):
    c = np.ones(a.size, dtype=a.dtype)
    for _ in range(0, b):
        c = (c * a) % order
    return c

GF(p) speed tests

GF(31) addition, N=10e3

N = int(10e3)
a, b, ga, gb, order = construct_arrays(GFp_small, N)

print(f"Pure python addition in GF({order})")
%timeit pure_python_add(a, b, order)

print(f"\nNative numpy addition in GF({order})")
%timeit (a + b) % order

print(f"\n`galois` implementation of addition in GF({order})")
%timeit ga + gb

Pure python addition in GF(31)
7.03 ms ± 170 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Native numpy addition in GF(31)
117 µs ± 475 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

`galois` implementation of addition in GF(31)
85.2 µs ± 2.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

GF(31) addition, N=10e6

N = int(10e6)
a, b, ga, gb, order = construct_arrays(GFp_small, N)

print(f"Pure python addition in GF({order})")
%timeit pure_python_add(a, b, order)

print(f"\nNative numpy addition in GF({order})")
%timeit (a + b) % order

print(f"\n`galois` implementation of addition in GF({order})")
%timeit ga + gb

Pure python addition in GF(31)
8.56 s ± 598 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Native numpy addition in GF(31)
162 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

`galois` implementation of addition in GF(31)
121 ms ± 1.84 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

GF(31) exponentiation, N=10e3

N = int(10e3)
a, b, ga, gb, order = construct_arrays(GFp_small, N)

exponent = 21

print(f"Pure python exponentiation in GF({order})")
%timeit pure_python_exp(a, exponent, order)

print(f"\nNative numpy exponentiation in GF({order})")
%timeit numpy_exp(a, exponent, order)

print(f"\n`galois` implementation of exponentiation in GF({order})")
%timeit ga ** exponent

Pure python exponentiation in GF(31)
151 ms ± 4.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Native numpy exponentiation in GF(31)
2.51 ms ± 62.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

`galois` implementation of exponentiation in GF(31)
1.03 ms ± 18.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

GF(31) exponentiation, N=10e6

N = int(10e6)
a, b, ga, gb, order = construct_arrays(GFp_small, N)

exponent = 21

# print(f"Pure python exponentiation in GF({order})")
# %timeit pure_python_exp(a, exponent, order)

print(f"\nNative numpy exponentiation in GF({order})")
%timeit numpy_exp(a, exponent, order)

print(f"\n`galois` implementation of exponentiation in GF({order})")
%timeit ga ** exponent

Native numpy exponentiation in GF(31)
2.96 s ± 239 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

`galois` implementation of exponentiation in GF(31)
1.08 s ± 43.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)