Merge remote-tracking branch 'upstream/master' into mceliece

10 files changed, 310 insertions, 26 deletions

diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf
index dfa2ba4..8a53398 100644
--- a/buch/papers/multiplikation/images/bigo.pdf
+++ b/buch/papers/multiplikation/images/bigo.pdf
diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex
index e3293e4..9ee3a68 100644
--- a/buch/papers/multiplikation/images/bigo.tex
+++ b/buch/papers/multiplikation/images/bigo.tex
@@ -39,67 +39,71 @@
 \begin{document}
 
 \begin{tikzpicture}
+
 \begin{axis}[
-    axis lines = left,
-    xlabel = $n$ (Data Input),
-    ylabel = {$t$ (time)},
-    legend pos=north east,
+    xmode=log, ymode=log,
+    xmin=1e-0, xmax=5000,
+    ymin=10e-1, ymax=1e7,
+    grid=both,
+    major grid style={black!50},
+    xlabel = data input size,
+    ylabel = {time},
+    legend pos=north west,
     very thick,
-    ymax = 500,
     yticklabels=\empty,
     xticklabels=\empty,
     scale only axis=true,
-  width=12cm, height=6cm,
+  width=12cm, height=8cm,
     ]
 \addplot [
-    domain= 1:20,
+    domain= 1:5000,
     samples=100,
     color=red,
 ]
 {1};
 \addlegendentry{$\mathcal{O}(1)$}
 \addplot [
-    domain= 1:20,
+    domain= 1:5000,
     samples=100,
     color=green,
 ]
 {x};
 \addlegendentry{$\mathcal{O}(n)$}
 \addplot [
-    domain= 1:20,
+    domain= 1:50000,
     samples=100,
     color=blue,
 ]
 {x^2};
-\addlegendentry{$\mathcal{O}(n^2)$}
+\addlegendentry{$\mathcal{O}\left(n^2\right)$}
 \addplot [
-    domain= 1:10,
+    domain= 1:500,
     samples=100,
     color=purple,
 ]
 {x^3};
-\addlegendentry{$\mathcal{O}(n^3)$}
+\addlegendentry{$\mathcal{O}\left(n^3\right)$}
 \addplot [
-    domain= 1:10,
+    domain= 1:500,
     samples=100,
     color=black,
 ]
-{exp(x)};
-\addlegendentry{$\mathcal{O}(e^n)$}
+{exp(x) - 1.7};
+\addlegendentry{$\mathcal{O}\left(e^n\right)$}
 \addplot [
-    domain= 1:20,
+    domain= 1:5000,
     samples=100,
     color=orange,
 ]
-{log2(x)};
+{log2(x)+1};
 \addlegendentry{$\mathcal{O}(\log n)$}
 
 \addplot [
-    domain= 1:20,
+    domain= 1:5000,
     samples=100,
     color=gray,
 ]
-{x*log2(x)};
+{x*log2(x)+1};
 \addlegendentry{$\mathcal{O}(n \log n)$}
 \end{axis}
 \end{tikzpicture}
diff --git a/buch/papers/multiplikation/images/c_meas_4096.pdf b/buch/papers/multiplikation/images/c_meas_4096.pdf
new file mode 100644
index 0000000..304015a
--- /dev/null
+++ b/buch/papers/multiplikation/images/c_meas_4096.pdf
diff --git a/buch/papers/multiplikation/images/meas_1024.pdf b/buch/papers/multiplikation/images/meas_1024.pdf
new file mode 100644
index 0000000..70c7ec1
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_1024.pdf
diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf
new file mode 100644
index 0000000..3a4cfd8
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_c.pdf
diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex
new file mode 100644
index 0000000..818a7e6
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_c.tex
@@ -0,0 +1,143 @@
+
+\documentclass[border=10pt,varwidth]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usepackage{pgfplotstable}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}
+\begin{axis}[
+xmode=log, ymode=log,
+xmin=60, xmax=5000,
+ymin=1e-4, ymax=2e3,
+grid=both,
+major grid style={black!50},
+xlabel = data Input ($n$),
+ylabel = {time ($s$)},
+legend pos=north west,
+very thick,
+scale only axis=true,
+width=12cm, height=8cm,
+       log basis x={10}
+]
+\addlegendentry{Winograd}
+\addplot[    color=purple,
+] coordinates {
+% (2,   0.000001)
+% (4,   0.000001)
+% (8,   0.000002)
+% (16,  0.000011)
+% (32,  0.000100)
+(64,  0.000654)
+(128, 0.005229)
+(256, 0.057440)
+(512, 0.517850)
+(1024,4.539413)
+(2048,130.627663)
+(4096,1179.261048)
+};
+\addlegendentry{Strassen}
+\addplot [    color=black,
+]coordinates {
+  %  (2,0.000001 )
+  %  (4,0.000003 )
+  %  (8,0.000010 )
+  % (16,0.000066 )
+  % (32,0.000470 )
+  (64,0.003368 )
+ (128,0.024232 )
+ (256,0.172000 )
+ (512,1.209262 )
+(1024,8.457472 )
+(2048,59.267256)
+(4096,414.648901)
+};
+
+\addlegendentry{MM div and conq}
+\addplot[    color=green,
+] coordinates {
+  %  (2,0.000003   )
+  %  (4,0.000002   )
+  %  (8,0.000010   )
+  % (16,0.000068   )
+  % (32,0.000594   )
+  (64,0.004264   )
+ (128,0.036289   )
+ (256,0.324645   )
+ (512,2.612010   )
+(1024,19.928951  )
+(2048,159.333884 )
+(4096,1147.106865)
+};
+
+\addlegendentry{MM}
+\addplot [    color=red,
+]coordinates {
+  %  (2,0.000001   )
+  %  (4,0.000001   )
+  %  (8,0.000001   )
+  % (16,0.000010   )
+  % (32,0.000081   )
+  (64,0.000654   )
+ (128,0.005556   )
+ (256,0.054253   )
+ (512,0.487317   )
+(1024,4.162845   )
+(2048,125.909034 )
+(4096,1111.312696)
+};
+\addlegendentry{BLAS}
+\addplot[    color=blue,
+] coordinates {
+  %  (2,0.000001 )
+  %  (4,0.000001 )
+  %  (8,0.000001 )
+  % (16,0.000003 )
+  % (32,0.000022 )
+  (64,0.000179 )
+ (128,0.001278  )
+ (256,0.010165  )
+ (512,0.074739  )
+(1024,0.704748  )
+(2048,6.845095  )
+(4096,55.845038)
+};
+\end{axis}
+\end{tikzpicture}
+
+\end{document}
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
new file mode 100644
index 0000000..cea2232
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_python.pdf
diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex
new file mode 100644
index 0000000..ee4db43
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_python.tex
@@ -0,0 +1,137 @@
+
+\documentclass[border=10pt,varwidth]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usepackage{pgfplotstable}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}
+\begin{axis}[
+xmode=log, ymode=log,
+xmin=30, xmax=1050,
+ymin=0.01, ymax=900,
+grid=both,
+major grid style={black!50},
+xlabel = data input ($n$),
+ylabel = {time ($s$)},
+legend pos=north west,
+very thick,
+scale only axis=true,
+width=12cm, height=8cm,
+       log basis x={10}
+]
+\addlegendentry{Winograd}
+\addplot[    color=purple,
+] coordinates {
+% (2,   2.7895e-05 )
+% (4,   0.000104904)
+% (8,   0.000552893)
+% (16,  0.0045557  )
+(32,  0.0187144  )
+(64,  0.153069   )
+(128, 1.19476    )
+(256, 8.29899    )
+(512, 68.3699    )
+(1024,537.374    )
+
+};
+\addlegendentry{Strassen}
+\addplot [    color=black,
+]coordinates {
+  %  (2,2.09808e-05 )
+  %  (4,0.000174284 )
+  %  (8,0.000943899 )
+  % (16,0.00475407  )
+  (32,0.0485256   )
+  (64,0.220414    )
+ (128,1.44718    2 )
+ (256,9.93866    0 )
+ (512,63.961     2 )
+(1024,461.494    2 )
+};
+
+\addlegendentry{MM div and conq}
+\addplot[    color=green,
+] coordinates {
+  %  (2,8.10623e-06 )
+  %  (4,9.01222e-05 )
+  %  (8,0.000729084 )
+  % (16,0.00497079  )
+  (32,0.02719     )
+  (64,0.26528     )
+ (128,1.77787      )
+ (256,13.27        )
+ (512,105.397      )
+(1024,847.321      )
+};
+
+\addlegendentry{MM}
+\addplot [    color=red,
+]coordinates {
+  %  (2,1.85966e-05)
+  %  (4,8.29697e-05 )
+  %  (8,0.000547171)
+  % (16,0.00305367   )
+  (32,  0.0240743 )
+  (64,  0.186895 )
+ (128,  1.56369 )
+ (256,  11.0062 )
+ (512,   85.4768)
+(1024,750.757 )
+};
+% \addlegendentry{NumPy}
+% \addplot[    color=blue,
+% ] coordinates {
+%    (2,1.83582e-05 )
+%    (4,7.86781e-06)
+%    (8,1.00136e-05)
+%   (16,5.4121e-05 )
+%   (32,4.26769e-05)
+%   (64,0.000118494)
+%  (128,0.000244141 )
+%  (256,0.000695705  )
+%  (512,0.00221705   )
+% (1024,0.0188088    )
+% };
+\end{axis}
+\end{tikzpicture}
+
+\end{document}
+
+
+
diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf
index 9899dcb..a30fdaa 100644
--- a/buch/papers/multiplikation/images/strassen.pdf
+++ b/buch/papers/multiplikation/images/strassen.pdf
diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex
index 797772b..5cf39b4 100644
--- a/buch/papers/multiplikation/images/strassen.tex
+++ b/buch/papers/multiplikation/images/strassen.tex
@@ -81,13 +81,13 @@
 	\node at (-3,-10) {$C_{12}=$} ;
 	\node at (-3,-5) {$C_{11}=$} ;
 	
-	\node at (5,-2)  {I};
-	\node at (10,-2)  {II};
-	\node at (15,-2)  {III};
-	\node at (20,-2)  {IV};
-	\node at (25,-2)  {V};
-	\node at (30,-2)  {VI};
-	\node at (35,-2)  {VII};
+	\node at (5,-2)  {P};
+	\node at (10,-2)  {Q};
+	\node at (15,-2)  {R};
+	\node at (20,-2)  {S};
+	\node at (25,-2)  {T};
+	\node at (30,-2)  {U};
+	\node at (35,-2)  {V};
 }