Commit: a6fa33805b0aa13effbb5bd9202d50fb4e5d0035 - GaloisField (hg)

A small kernel of code for playing with Galois fields of arbitrary characteristic

Commit MetaInfo

• Revision: a6fa33805b0aa13effbb5bd9202d50fb4e5d0035 (tree)
• Time: 2017-06-17 02:12:59
• Author: Eric Hopper <hopper@omni...>
• Commiter: Eric Hopper

Log Message

Add a function to do Lagrange interpolation.

Change Summary

• modified: polyops.py

Incremental Difference

diff -r 70dafd911f2d -r a6fa33805b0a polyops.py
--- a/polyops.py	Fri Jun 16 10:12:45 2017 -0700
+++ b/polyops.py	Fri Jun 16 10:12:59 2017 -0700
@@ -168,3 +168,32 @@
         result += a_coef * xpower
         xpower *= x
     return result
+
+def lagrange_interp(points):
+    from functools import reduce
+    there_is_no_one = object()
+
+    def determine_mult_ident_and_numpts(points):
+        numpts = 0
+        one = there_is_no_one
+        for x, y in points:
+            if (one is there_is_no_one) and (type(x)() != x):
+                one = x / x
+            numpts += 1
+        return (one, numpts)
+
+    (xone, numpts) = determine_mult_ident_and_numpts(points)
+    if xone is there_is_no_one:
+        if numpts > 1:
+            raise ValueError("Impossible to interpolate.")
+        else:
+            return (next(iter(points))[1],)
+    xzero = type(next(iter(points))[0])()
+    master_poly = reduce(polymul,
+                         ((xzero - x, 1) for x, y in points),
+                         (xone,))
+    xpolys = ((polydiv(master_poly, (xzero - x, xone))[0], x, y)
+              for x, y in points)
+    xpolys = (polyscalarmul(xp, y / evalpoly(xp, x))
+              for xp, x, y in xpolys)
+    return normalized(reduce(polyadd, xpolys, ()))