From 489104565442a3ab03dd2fad2fd700e578c01008 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Thu, 20 Oct 2022 00:17:52 -0700 Subject: [PATCH] add Toom-2.5 --- .../test_toom_cook.py | 129 +++++++++++++++++- src/bigint_presentation_code/toom_cook.py | 47 +++++++ 2 files changed, 175 insertions(+), 1 deletion(-) diff --git a/src/bigint_presentation_code/test_toom_cook.py b/src/bigint_presentation_code/test_toom_cook.py index f880a81..656c8d7 100644 --- a/src/bigint_presentation_code/test_toom_cook.py +++ b/src/bigint_presentation_code/test_toom_cook.py @@ -6,7 +6,7 @@ from bigint_presentation_code.toom_cook import ToomCookInstance class TestToomCook(unittest.TestCase): def test_toom_2(self): TOOM_2 = ToomCookInstance.make_toom_2() - print(repr(repr(TOOM_2))) + # print(repr(repr(TOOM_2))) self.assertEqual( repr(TOOM_2), "ToomCookInstance(lhs_part_count=2, rhs_part_count=2, " @@ -42,6 +42,133 @@ class TestToomCook(unittest.TestCase): "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)}))))" ) + def test_toom_2_5(self): + TOOM_2_5 = ToomCookInstance.make_toom_2_5() + # print(repr(repr(TOOM_2_5))) + self.assertEqual( + repr(TOOM_2_5), + "ToomCookInstance(lhs_part_count=3, rhs_part_count=2, " + "eval_points=(0, 1, -1, POINT_AT_INFINITY), lhs_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpAdd(lhs=" + "EvalOpAdd(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=2, rhs=0, " + "poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 2: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=1, rhs=0, " + "poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly({" + "0: Fraction(1, 1), 1: Fraction(1, 1), 2: Fraction(1, 1)})), " + "EvalOpSub(lhs=" + "EvalOpAdd(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=2, rhs=0, " + "poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 2: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=1, rhs=0, " + "poly=EvalOpPoly({1: Fraction(1, 1)})), poly=EvalOpPoly(" + "{0: Fraction(1, 1), 1: Fraction(-1, 1), 2: Fraction(1, 1)})), " + "EvalOpInput(lhs=2, rhs=0, " + "poly=EvalOpPoly({2: Fraction(1, 1)}))), rhs_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpAdd(lhs=EvalOpInput(lhs=0, rhs=0, " + "poly=EvalOpPoly({0: Fraction(1, 1)})), rhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 1: Fraction(1, 1)})), " + "EvalOpSub(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=1, rhs=0, " + "poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 1: Fraction(-1, 1)})), " + "EvalOpInput(lhs=1, rhs=0, " + "poly=EvalOpPoly({1: Fraction(1, 1)}))), " + "prod_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpSub(lhs=EvalOpExactDiv(lhs=EvalOpSub(lhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "rhs=EvalOpInput(lhs=2, rhs=0, " + "poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({1: Fraction(1, 1), 2: Fraction(-1, 1)})), " + "rhs=2, " + "poly=EvalOpPoly({1: Fraction(1, 2), 2: Fraction(-1, 2)})), rhs=" + "EvalOpInput(lhs=3, rhs=0, poly=EvalOpPoly({3: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{1: Fraction(1, 2), 2: Fraction(-1, 2), 3: Fraction(-1, 1)})), " + "EvalOpSub(lhs=EvalOpExactDiv(lhs=EvalOpAdd(lhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({1: Fraction(1, 1), 2: Fraction(1, 1)})), rhs=2, " + "poly=EvalOpPoly({1: Fraction(1, 2), 2: Fraction(1, 2)})), rhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{0: Fraction(-1, 1), 1: Fraction(1, 2), 2: Fraction(1, 2)})), " + "EvalOpInput(lhs=3, rhs=0, poly=EvalOpPoly({3: Fraction(1, 1)}))))" + ) + + def test_reversed_toom_2_5(self): + TOOM_2_5 = ToomCookInstance.make_toom_2_5().reversed() + print(repr(repr(TOOM_2_5))) + self.assertEqual( + repr(TOOM_2_5), + "ToomCookInstance(lhs_part_count=2, rhs_part_count=3, " + "eval_points=(0, 1, -1, POINT_AT_INFINITY), lhs_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpAdd(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 1: Fraction(1, 1)})), " + "EvalOpSub(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 1: Fraction(-1, 1)})), " + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})))," + " rhs_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpAdd(lhs=EvalOpAdd(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 2: Fraction(1, 1)})), rhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{0: Fraction(1, 1), 1: Fraction(1, 1), 2: Fraction(1, 1)})), " + "EvalOpSub(lhs=EvalOpAdd(lhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({0: Fraction(1, 1), 2: Fraction(1, 1)})), rhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{0: Fraction(1, 1), 1: Fraction(-1, 1), 2: Fraction(1, 1)})), " + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})))," + " prod_eval_ops=(" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "EvalOpSub(lhs=EvalOpExactDiv(lhs=EvalOpSub(lhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({1: Fraction(1, 1), 2: Fraction(-1, 1)})), " + "rhs=2, " + "poly=EvalOpPoly({1: Fraction(1, 2), 2: Fraction(-1, 2)})), rhs=" + "EvalOpInput(lhs=3, rhs=0, poly=EvalOpPoly({3: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{1: Fraction(1, 2), 2: Fraction(-1, 2), 3: Fraction(-1, 1)})), " + "EvalOpSub(lhs=EvalOpExactDiv(lhs=EvalOpAdd(lhs=" + "EvalOpInput(lhs=1, rhs=0, poly=EvalOpPoly({1: Fraction(1, 1)})), " + "rhs=" + "EvalOpInput(lhs=2, rhs=0, poly=EvalOpPoly({2: Fraction(1, 1)})), " + "poly=EvalOpPoly({1: Fraction(1, 1), 2: Fraction(1, 1)})), rhs=2, " + "poly=EvalOpPoly({1: Fraction(1, 2), 2: Fraction(1, 2)})), rhs=" + "EvalOpInput(lhs=0, rhs=0, poly=EvalOpPoly({0: Fraction(1, 1)})), " + "poly=EvalOpPoly(" + "{0: Fraction(-1, 1), 1: Fraction(1, 2), 2: Fraction(1, 2)})), " + "EvalOpInput(lhs=3, rhs=0, poly=EvalOpPoly({3: Fraction(1, 1)}))))" + ) + if __name__ == "__main__": unittest.main() diff --git a/src/bigint_presentation_code/toom_cook.py b/src/bigint_presentation_code/toom_cook.py index 76a8a99..9786624 100644 --- 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] -- 2.30.2