add Toom-2.5

[bigint-presentation-code.git] / src / bigint_presentation_code / toom_cook.py

diff --git a/src/bigint_presentation_code/toom_cook.py b/src/bigint_presentation_code/toom_cook.py
index 76a8a994b11d1123e1233b3c8e4a03857ebdc437..9786624d7dc395df7ce17d6b977351f14430f38e 100644 (file)
--- a/src/bigint_presentation_code/toom_cook.py
+++ b/src/bigint_presentation_code/toom_cook.py
@@ -365,9 +365,21 @@ class ToomCookInstance:
                     f"prod_eval_ops[{i}] is incorrect: expected polynomial: "
                     f"{prod_eval_polys[i]} found polynomial: {eval_op.poly}")
 
+    def reversed(self):
+        # type: () -> ToomCookInstance
+        """return a ToomCookInstance where lhs/rhs are reversed"""
+        return ToomCookInstance(
+            lhs_part_count=self.rhs_part_count,
+            rhs_part_count=self.lhs_part_count,
+            eval_points=self.eval_points,
+            lhs_eval_ops=self.rhs_eval_ops,
+            rhs_eval_ops=self.lhs_eval_ops,
+            prod_eval_ops=self.prod_eval_ops)
+
     @staticmethod
     def make_toom_2():
         # type: () -> ToomCookInstance
+        """make an instance of Toom-2 aka Karatsuba multiplication"""
         return ToomCookInstance(
             lhs_part_count=2,
             rhs_part_count=2,
@@ -390,6 +402,41 @@ class ToomCookInstance:
             ],
         )
 
+    @staticmethod
+    def make_toom_2_5():
+        # type: () -> ToomCookInstance
+        """makes an instance of Toom-2.5"""
+        inp_0_plus_inp_2 = EvalOpAdd(EvalOpInput(0), EvalOpInput(2))
+        inp_1_minus_inp_2 = EvalOpSub(EvalOpInput(1), EvalOpInput(2))
+        inp_1_plus_inp_2 = EvalOpAdd(EvalOpInput(1), EvalOpInput(2))
+        inp_1_minus_inp_2_all_div_2 = EvalOpExactDiv(inp_1_minus_inp_2, 2)
+        inp_1_plus_inp_2_all_div_2 = EvalOpExactDiv(inp_1_plus_inp_2, 2)
+        return ToomCookInstance(
+            lhs_part_count=3,
+            rhs_part_count=2,
+            eval_points=[0, 1, -1, POINT_AT_INFINITY],
+            lhs_eval_ops=[
+                EvalOpInput(0),
+                EvalOpAdd(inp_0_plus_inp_2, EvalOpInput(1)),
+                EvalOpSub(inp_0_plus_inp_2, EvalOpInput(1)),
+                EvalOpInput(2),
+            ],
+            rhs_eval_ops=[
+                EvalOpInput(0),
+                EvalOpAdd(EvalOpInput(0), EvalOpInput(1)),
+                EvalOpSub(EvalOpInput(0), EvalOpInput(1)),
+                EvalOpInput(1),
+            ],
+            prod_eval_ops=[
+                EvalOpInput(0),
+                EvalOpSub(inp_1_minus_inp_2_all_div_2, EvalOpInput(3)),
+                EvalOpSub(inp_1_plus_inp_2_all_div_2, EvalOpInput(0)),
+                EvalOpInput(3),
+            ],
+        )
+
+    # TODO: add make_toom_3
+
 
 def toom_cook_mul(fn, word_count, instances):
     # type: (Fn, int, Sequence[ToomCookInstance]) -> OSet[Op]