Merge branch 'AndreasFMueller:master' into master

6 files changed, 216 insertions, 81 deletions

diff --git a/buch/papers/multiplikation/images/algo_tab.pdf b/buch/papers/multiplikation/images/algo_tab.pdf
new file mode 100644
index 0000000..7f2bb4f
--- /dev/null
+++ b/buch/papers/multiplikation/images/algo_tab.pdf
diff --git a/buch/papers/multiplikation/images/algo_tab.tex b/buch/papers/multiplikation/images/algo_tab.tex
new file mode 100644
index 0000000..50ce392
--- /dev/null
+++ b/buch/papers/multiplikation/images/algo_tab.tex
@@ -0,0 +1,122 @@
+\documentclass{article}
+\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{algorithm}
+\usepackage{algpseudocode}
+\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{multicol}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\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{table}[t]
+	\begin{tabular}{ll}
+		\begin{minipage}{0.4\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\label{multiplikation:alg:b1}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\Function{B1}{$a, b$}
+					\State \textbf{return} $a+b$
+					\EndFunction
+					\State
+					\State
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage}	
+		&
+		\begin{minipage}{0.4\textwidth}
+	\begin{algorithm}[H]\footnotesize\caption{}
+	\label{multiplikation:alg:b2}
+	\setlength{\lineskip}{7pt}
+	\begin{algorithmic}
+		\Function{B2}{$a, b$}
+		\State $ x \gets a+b $
+		\State $ y \gets a \cdot b $
+		\State \textbf{return} $x+y$
+		\EndFunction
+	\end{algorithmic}
+\end{algorithm}
+
+		\end{minipage}
+	\end{tabular}
+\end{table}
+
+\begin{table}
+	\begin{tabular}[t]{ll} 
+		\begin{minipage}{0.4\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\label{multiplikation:alg:linear}
+					\Function{L}{$\mathbf{a}, \mathbf{b}$,n}
+					\State $ sum \gets 0$
+					\For{$i = 0,1,2 \dots,n$}
+					\State $ sum \gets sum + A[i] \cdot B[i] $
+					\EndFor
+					
+					\State \textbf{return} $sum$
+					
+					\EndFunction
+					\State
+					\State
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage}	
+		&
+		\begin{minipage}{0.4\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+			\label{multiplikation:alg:q1}
+			\setlength{\lineskip}{7pt}
+			\begin{algorithmic}
+				\Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
+				\State $ sum \gets 0$
+				\For{$i = 0,1,2 \dots,n$}
+				\For{$j = 0,1,2 \dots,n$}
+				\State $ sum \gets sum + A[i] \cdot B[j] $
+				\EndFor
+				\EndFor
+				\State \textbf{return} $sum$
+				\EndFunction
+			\end{algorithmic}
+		\end{algorithm}
+		\end{minipage}
+	\end{tabular}
+\end{table}
+
+dhdfh
+\end{document}
diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf
index 3a4cfd8..faf347e 100644
--- a/buch/papers/multiplikation/images/meas_c.pdf
+++ 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
index 818a7e6..fe2bd2f 100644
--- a/buch/papers/multiplikation/images/meas_c.tex
+++ b/buch/papers/multiplikation/images/meas_c.tex
@@ -43,8 +43,8 @@
 \begin{tikzpicture}
 \begin{axis}[
 xmode=log, ymode=log,
-xmin=60, xmax=5000,
-ymin=1e-4, ymax=2e3,
+xmin=30, xmax=10000,
+ymin=1e-5, ymax=2e4,
 grid=both,
 major grid style={black!50},
 xlabel = data Input ($n$),
@@ -57,85 +57,91 @@ width=12cm, height=8cm,
 ]
 \addlegendentry{Winograd}
 \addplot[    color=purple,
+        error bars/.cd, y dir=both, y explicit,
 ] 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)
+%(2,1e-07)
+%(4,5e-07)
+%(8,2.0000000000000003e-06)
+%(16,1.1999999999999999e-05)
+(32,8.329999999999999e-05)
+(64,0.0006479)
+(128,0.0052873)
+(256,0.052674599999999995)
+(512,0.5249752000000001)
+(1024,4.671161)
+(2048,136.6769777)
 (4096,1179.261048)
+(8192,10071.512655)
 };
 \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)
+%(2,1e-07)
+%(4,2.1e-06)
+%(8,1.13e-05)
+%(16,7.07e-05)
+(32,0.0005041)
+(64,0.003596)
+(128,0.0254481)
+(256,0.1781817)
+(512,1.2555)
+(1024,8.8302371)
+(2048,61.9018691)
 (4096,414.648901)
+(8192,3014.235467)
 };
 
 \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 )
+%(2,3e-07)
+%(4,1.1e-06)
+%(8,8.6e-06)
+%(16,7.819999999999999e-05)
+(32,0.0005940000000000001)
+(64,0.0044339)
+(128,0.0348443)
+(256,0.29484730000000003)
+(512,2.2228507)
+(1024,17.659234500000004)
+(2048,141.6103936)
 (4096,1147.106865)
+(8192,9606.402522)
 };
 
 \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 )
+%(2,0.0)
+%(4,3e-07)
+%(8,1.8000000000000001e-06)
+%(16,1.1999999999999999e-05)
+(32,8.93e-05)
+(64,0.0006923)
+(128,0.0056842)
+(256,0.051771500000000005)
+(512,0.5062468000000001)
+(1024,4.5048086)
+(2048,129.2894619)
 (4096,1111.312696)
+(8192,9376.173434)
 };
 \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  )
+%(2,1e-07)
+%(4,0.0)
+%(8,1e-07)
+%(16,3.9e-06)
+(32,2.1000000000000002e-05)
+(64,0.00018580000000000002)
+(128,0.0012649)
+(256,0.0096489)
+(512,0.0773765)
+(1024,0.7643868)
+(2048,7.6320993999999995)
 (4096,55.845038)
+(8192,478.429957)
 };
 \end{axis}
 \end{tikzpicture}
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
index cea2232..ab3b14b 100644
--- a/buch/papers/multiplikation/images/meas_python.pdf
+++ 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
index ee4db43..d942f46 100644
--- a/buch/papers/multiplikation/images/meas_python.tex
+++ b/buch/papers/multiplikation/images/meas_python.tex
@@ -43,8 +43,8 @@
 \begin{tikzpicture}
 \begin{axis}[
 xmode=log, ymode=log,
-xmin=30, xmax=1050,
-ymin=0.01, ymax=900,
+xmin=30, xmax=4200,
+ymin=0.01, ymax=70000,
 grid=both,
 major grid style={black!50},
 xlabel = data input ($n$),
@@ -68,7 +68,8 @@ width=12cm, height=8cm,
 (256, 8.29899    )
 (512, 68.3699    )
 (1024,537.374    )
-
+(2046,4884.61)
+(4096,43597.1)
 };
 \addlegendentry{Strassen}
 \addplot [    color=black,
@@ -79,10 +80,12 @@ width=12cm, height=8cm,
   % (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 )
+ (128,1.44718    )
+ (256,9.93866    )
+ (512,63.961     )
+(1024,461.494    )
+(2046,3860.57)
+(4096,22904.3)
 };
 
 \addlegendentry{MM div and conq}
@@ -98,6 +101,8 @@ width=12cm, height=8cm,
  (256,13.27        )
  (512,105.397      )
 (1024,847.321      )
+(2046,7375.93)
+(4096,58466)
 };
 
 \addlegendentry{MM}
@@ -113,25 +118,27 @@ width=12cm, height=8cm,
  (256,  11.0062 )
  (512,   85.4768)
 (1024,750.757 )
+(2046,6154.18)
+(4096,46813.3)
 };
-% \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    )
-% };
+%  \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    )
+% (2046,0.215739)
+% (4096,1.49159)
+%  };
+
 \end{axis}
 \end{tikzpicture}
 
 \end{document}
-
-
-