1 files changed, 42 insertions, 0 deletions
diff --git a/aberth/poly.h b/aberth/poly.h
new file mode 100644
index 0000000..82f04a2
--- /dev/null
+++ b/aberth/poly.h
@@ -0,0 +1,42 @@
+#pragma once
+
+#include "defs.h"
+
+
+using Poly = array<int, N + 1>;
+
+
+template <typename T>
+T eval(const Poly &p, int nterms, T pt) {
+	T value = p[nterms - 1];
+	for (int i = nterms - 2; i >= 0; i--) {
+		value = pt * value + (double)p[i];
+	}
+	return value;
+}
+
+template <typename T>
+T eval(const Poly &p, T pt) {
+	return eval(p, p.size(), pt);
+}
+
+inline Poly derivative(const Poly &p) {
+	Poly res;
+	for (int i = res.size() - 2; i >= 0; i--) {
+		res[i] = (i+1) * p[i+1];
+	}
+	return res;
+}
+
+inline double maxRootNorm(const Poly &poly) {
+	// Cauchy's bound: https://en.wikipedia.org/wiki/Geometrical_properties_of_polynomial_roots#Lagrange's_and_Cauchy's_bounds
+
+	double value = 0;
+	double last = (double)poly.back();
+	for (int i = 0; i < (int)poly.size() - 1; i++) {
+		value = max(value, abs(poly[i] / last));
+	}
+	return 1 + value;
+}
+
+ostream& operator<<(ostream &os, const Poly &p);