(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 6.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[      6631,        187]
NotebookOptionsPosition[      6383,        174]
NotebookOutlinePosition[      6719,        189]
CellTagsIndexPosition[      6676,        186]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{
Cell[BoxData[{
 RowBox[{
  RowBox[{"Clear", "[", 
   RowBox[{"ListKaratsuba", ",", "PolynomialKaratsuba"}], "]"}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"ListKaratsuba", "[", 
   RowBox[{"list1_", ",", "list2_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{
     RowBox[{"list1", "[", 
      RowBox[{"[", "1", "]"}], "]"}], "*", 
     RowBox[{"list2", "[", 
      RowBox[{"[", "1", "]"}], "]"}]}], "}"}], "/;", 
   RowBox[{
    RowBox[{
     RowBox[{"Min", "[", 
      RowBox[{
       RowBox[{"Length", "[", "list1", "]"}], ",", 
       RowBox[{"Length", "[", "list2", "]"}]}], "]"}], "==", "1"}], 
    "\[IndentingNewLine]"}]}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"ListKaratsuba", "[", 
    RowBox[{"list1_", ",", "list2_"}], "]"}], ":=", 
   RowBox[{
    RowBox[{"ListKaratsuba", "[", 
     RowBox[{"list1", ",", "list2"}], "]"}], "=", 
    RowBox[{"Module", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{
       "a", ",", "b", ",", "c", ",", "d", ",", "n", ",", "m", ",", "list1neu",
         ",", "list2neu", ",", "amalc", ",", "bmald", ",", "mittelterm", ",", 
        "tab"}], "}"}], ",", "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"n", "=", 
        RowBox[{"Length", "[", "list1", "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"m", "=", 
        RowBox[{"Length", "[", "list2", "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"m", "=", 
        RowBox[{"Max", "[", 
         RowBox[{"n", ",", "m"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"n", "=", "1"}], ";", "\[IndentingNewLine]", 
       RowBox[{"While", "[", 
        RowBox[{
         RowBox[{"n", "<", "m"}], ",", 
         RowBox[{"n", "=", 
          RowBox[{"2", "*", "n"}]}]}], "]"}], ";", "\[IndentingNewLine]", 
       RowBox[{"list1neu", "=", 
        RowBox[{"PadLeft", "[", 
         RowBox[{"list1", ",", "n"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"list2neu", "=", 
        RowBox[{"PadLeft", "[", 
         RowBox[{"list2", ",", "n"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"a", "=", 
        RowBox[{"Take", "[", 
         RowBox[{"list1neu", ",", 
          RowBox[{"n", "/", "2"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"b", "=", 
        RowBox[{"Take", "[", 
         RowBox[{"list1neu", ",", 
          RowBox[{
           RowBox[{"-", "n"}], "/", "2"}]}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"c", "=", 
        RowBox[{"Take", "[", 
         RowBox[{"list2neu", ",", 
          RowBox[{"n", "/", "2"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"d", "=", 
        RowBox[{"Take", "[", 
         RowBox[{"list2neu", ",", 
          RowBox[{
           RowBox[{"-", "n"}], "/", "2"}]}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"amalc", "=", 
        RowBox[{"ListKaratsuba", "[", 
         RowBox[{"a", ",", "c"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"bmald", "=", 
        RowBox[{"ListKaratsuba", "[", 
         RowBox[{"b", ",", "d"}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"mittelterm", "=", 
        RowBox[{"amalc", "+", "bmald", "+", 
         RowBox[{"ListKaratsuba", "[", 
          RowBox[{
           RowBox[{"a", "-", "b"}], ",", 
           RowBox[{"d", "-", "c"}]}], "]"}]}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"tab", "=", 
        RowBox[{"Table", "[", 
         RowBox[{"0", ",", 
          RowBox[{"{", 
           RowBox[{"n", "/", "2"}], "}"}]}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"mittelterm", "=", 
        RowBox[{"Join", "[", 
         RowBox[{"mittelterm", ",", "tab"}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"amalc", "=", 
        RowBox[{"Join", "[", 
         RowBox[{"amalc", ",", "tab", ",", "tab"}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"amalc", "=", 
        RowBox[{"PadLeft", "[", 
         RowBox[{"amalc", ",", 
          RowBox[{"2", "*", "n"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"mittelterm", "=", 
        RowBox[{"PadLeft", "[", 
         RowBox[{"mittelterm", ",", 
          RowBox[{"2", "*", "n"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"bmald", "=", 
        RowBox[{"PadLeft", "[", 
         RowBox[{"bmald", ",", 
          RowBox[{"2", "*", "n"}]}], "]"}]}], ";", "\[IndentingNewLine]", 
       RowBox[{"amalc", "+", "mittelterm", "+", "bmald"}]}]}], 
     "\[IndentingNewLine]", "]"}]}]}], 
  "\[IndentingNewLine]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"PolynomialKaratsuba", "[", 
   RowBox[{"pol1_", ",", "pol2_", ",", "x_"}], "]"}], ":=", 
  RowBox[{"Module", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"list1", ",", "list2", ",", "list3", ",", "l"}], "}"}], ",", 
    "\[IndentingNewLine]", 
    RowBox[{
     RowBox[{"list1", "=", 
      RowBox[{"Reverse", "[", 
       RowBox[{"CoefficientList", "[", 
        RowBox[{"pol1", ",", "x"}], "]"}], "]"}]}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"list2", "=", 
      RowBox[{"Reverse", "[", 
       RowBox[{"CoefficientList", "[", 
        RowBox[{"pol2", ",", "x"}], "]"}], "]"}]}], ";", 
     "\[IndentingNewLine]", 
     RowBox[{"list3", "=", 
      RowBox[{"ListKaratsuba", "[", 
       RowBox[{"list1", ",", "list2"}], "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"l", "=", 
      RowBox[{"Length", "[", "list3", "]"}]}], ";", "\[IndentingNewLine]", 
     RowBox[{"Sum", "[", 
      RowBox[{
       RowBox[{
        RowBox[{"list3", "[", 
         RowBox[{"[", 
          RowBox[{"l", "-", "k"}], "]"}], "]"}], "*", 
        RowBox[{"x", "^", "k"}]}], ",", 
       RowBox[{"{", 
        RowBox[{"k", ",", "0", ",", 
         RowBox[{"l", "-", "1"}]}], "}"}]}], "]"}]}]}], "\[IndentingNewLine]",
    "]"}]}]}], "Input"]
},
WindowSize->{640, 750},
WindowMargins->{{12, Automatic}, {Automatic, 24}},
FrontEndVersion->"6.0 for Mac OS X x86 (32-bit) (June 19, 2007)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[568, 21, 5811, 151, 794, "Input"]
}
]
*)

(* End of internal cache information *)