\def\RGBColor#1#2{\special{color push rgb #1}#2\special{color pop}}
\def\ignore#1{}

\catcode`\@=11
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@}
\newdimen\jot \jot=3pt
\newskip\plaincentering \plaincentering=0pt plus 1000pt minus 1000pt
\def\ialign{\everycr{}\tabskip\z@skip\halign}
\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\newif\ifdt@p
\def\displ@y{\global\dt@ptrue\openup\jot\m@th
  \everycr{\noalign{\ifdt@p \global\dt@pfalse \ifdim\prevdepth>-1000\p@
      \vskip-\lineskiplimit \vskip\normallineskiplimit \fi
      \else \penalty\interdisplaylinepenalty \fi}}}
\def\@lign{\tabskip\z@skip\everycr{}} % restore inside \displ@y
\def\displaylines#1{\displ@y \tabskip\z@skip
  \halign{\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}\crcr
    #1\crcr}}
\def\eqalignno#1{\displ@y \tabskip\plaincentering
  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
    &$\@lign\displaystyle{{}##}$\hfil\tabskip\plaincentering
    &\llap{$\@lign##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\plaincentering
  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
    &$\@lign\displaystyle{{}##}$\hfil\tabskip\plaincentering
    &\kern-\displaywidth\rlap{$\@lign##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\def\plaincases#1{\left\{\,\vcenter{\normalbaselines\m@th
    \ialign{$##\hfil$&\quad##\hfil\crcr#1\crcr}}\right.}
\def\plainmatrix#1{\null\,\vcenter{\normalbaselines\m@th
    \ialign{\hfil$##$\hfil&&\quad\hfil$##$\hfil\crcr
      \mathstrut\crcr\noalign{\kern-\baselineskip}
      #1\crcr\mathstrut\crcr\noalign{\kern-\baselineskip}}}\,}
\def\plainpmatrix#1{\left(\plainmatrix{#1}\right)}
\catcode`\@=12

\def\hexnbr#1{\ifnum#1<10 \number#1\else
 \ifnum#1=10 A\else\ifnum#1=11 B\else\ifnum#1=12 C\else
 \ifnum#1=13 D\else\ifnum#1=14 E\else\ifnum#1=15 F\fi\fi\fi\fi\fi\fi\fi}
\font\tenmathx=mathx10
\font\eightmathx=mathx8
\font\sevenmathx=mathxm7
\font\fivemathx=mathxm5
\newfam\mathxfam
  \textfont\mathxfam=\tenmathx
  \scriptfont\mathxfam=\sevenmathx
  \scriptscriptfont\mathxfam=\fivemathx
\def\mathx{\fam\mathxfam\tenmathx}
\def\mathxtype{\hexnbr\mathxfam}

\def\overacute{\mathaccent"0\mathxtype79}
\def\overobtuse{\mathaccent"0\mathxtype7D}

% This file is a solution template for:
% - Giving a talk on some subject.
% - The talk is between 15min and 45min long.
% - Style is ornate.
% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 
\mode<presentation>
{
% \setbeamertemplate{background canvas}[vertical shading][bottom=red!10,
% top=blue!10]
  \usetheme{Warsaw}
  \usefonttheme[onlysmall]{structurebold}
}
% or whatever

\usepackage{amsmath,amssymb}
\usepackage[english]{babel}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.

\title[\RGBColor{1 1 1}{\ 
\kern-190pt Jean-Pierre Demailly (Grenoble I), November 26, 2011\kern30pt
On the computational complexity of mathematical functions}]
% (optional, use only with long paper titles)
{On the computational complexity\\ of mathematical functions}

%% \subtitle{Presentation Subtitle} % (optional)

\author[] % (optional, use only with lots of authors)
{Jean-Pierre Demailly}

\institute[]{Institut Fourier, Universit\'e de Grenoble I\\
\& Acad\'emie des Sciences, Paris (France)}
% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

\date[]% (optional)
{November 26, 2011\\KVPY conference at Vijyoshi Camp}

%%\subject{Talks}
% This is only inserted into the PDF information catalog. Can be left
% out. 

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

\definecolor{ColClaim}{rgb}{0,0,0.8}
\def\claim#1{{\color{ColClaim}#1}}

\definecolor{Alert}{rgb}{0.8,0,0}
\def\alert#1{{\color{Alert}#1}}

\definecolor{Justify}{rgb}{0,0.8,0}
\def\justify#1{{\color{Justify}#1}}

\def\srelbar{\vrule width0.6ex height0.65ex depth-0.55ex}
\def\merto{\mathrel{\srelbar\kern1.3pt\srelbar\kern1.3pt\srelbar
    \kern1.3pt\srelbar\kern-0.78ex\raise0.3ex\hbox{${\scriptscriptstyle>}$}}}

\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\tors}{\operatorname{torsion}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\reg}{\operatorname{reg}}
\renewcommand{\div}{\operatorname{div}}

\newcommand{\bB}{{\mathbb B}}
\newcommand{\bC}{{\mathbb C}}
\newcommand{\bD}{{\mathbb D}}
\newcommand{\bN}{{\mathbb N}}
\newcommand{\bP}{{\mathbb P}}
\newcommand{\bQ}{{\mathbb Q}}
\newcommand{\bR}{{\mathbb R}}
\newcommand{\bZ}{{\mathbb Z}}

\newcommand{\cA}{{\mathcal A}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cO}{{\mathcal O}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cX}{{\mathcal X}}

\newcommand{\dbar}{\overline\partial}
\newcommand{\ddbar}{\partial\overline\partial}
\newcommand{\ovl}{\overline}
\newcommand{\wt}{\widetilde}
\newcommand{\lra}{\longrightarrow}
\newcommand{\bu}{\claim{\bullet}}
\newcommand{\bul}{{\scriptscriptstyle\bullet}}

% mathematical operators
\renewcommand{\Re}{\mathop{\rm Re}\nolimits}
\renewcommand{\Im}{\mathop{\rm Im}\nolimits}
\newcommand{\Pic}{\mathop{\rm Pic}\nolimits}
\newcommand{\codim}{\mathop{\rm codim}\nolimits}
\newcommand{\diam}{\mathop{\rm diam}\nolimits}
\newcommand{\Id}{\mathop{\rm Id}\nolimits}
\newcommand{\Sing}{\mathop{\rm Sing}\nolimits}
\newcommand{\Supp}{\mathop{\rm Supp}\nolimits}
\newcommand{\Vol}{\mathop{\rm Vol}\nolimits}
\newcommand{\rank}{\mathop{\rm rank}\nolimits}
\newcommand{\pr}{\mathop{\rm pr}\nolimits}

\newcommand{\NS}{\mathop{\rm NS}\nolimits}
\newcommand{\GG}{{\mathop{\rm GG}\nolimits}}
\newcommand{\NE}{\mathop{\rm NE}\nolimits}
\newcommand{\ME}{\mathop{\rm ME}\nolimits}
\newcommand{\SME}{\mathop{\rm SME}\nolimits}
\newcommand{\alg}{{\rm alg}}
\newcommand{\nef}{{\rm nef}}
\newcommand{\num}{\nu}
\newcommand{\ssm}{\mathop{\Bbb r}}
\newcommand{\smallvee}{{\scriptscriptstyle\vee}}

\def\ovl{\overline}
\def\build#1^#2_#3{\mathrel{\mathop{\null#1}\limits^{#2}_{#3}}}
\def\bibitem[#1]#2#3{\medskip{\bf[#1]} #3}

\begin{document}

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
%%\AtBeginSubsection[]
%%{
%% \begin{frame}<beamer>
%%    \frametitle{Outline}
%%    \tableofcontents[currentsection,currentsubsection]
%%  \end{frame}
%%}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}

\begin{frame}
  \pgfdeclareimage[height=1cm]{ujf-logo}{ujf-logo}
  \pgfuseimage{ujf-logo}
  \pgfdeclareimage[height=1cm]{acad-logo}{acad-logo}
  \pgfuseimage{acad-logo}
  \titlepage
\end{frame}

%%\begin{frame}
%%  \frametitle{Outline}
%%  \tableofcontents
%% You might wish to add the option [pausesections]
%%\end{frame}


% Since this a solution template for a generic talk, very little can
% be said about how it should be structured. However, the talk length
% of between 15min and 45min and the theme suggest that you stick to
% the following rules:  

% - Exactly two or three sections (other than the summary).
% - At *most* three subsections per section.
% - Talk about 30s to 2min per frame. So there should be between about
%   15 and 30 frames, all told.

%% \section*{Basic concepts}
%%\def\pause{}
 
\begin{frame}
 \frametitle{Computing, a very old concern}
$\strut$\vskip1.05cm
\pgfdeclareimage[height=4.5cm]{hindu-arabic-numerals}{hindu-arabic-numerals}
\pgfuseimage{hindu-arabic-numerals}
\vskip-8.4cm
\pgfdeclareimage[height=5.3cm]{babylonian}{babylonian}
\pgfuseimage{babylonian}
$~$\kern5mm\raise2cm\vbox{
Babylonian mathematical tablet\\
allowing the computation of $\sqrt{2}$\\
(1800 -- 1600 BC)\\
$\strut$\\
Decimal numeral system\\
invented in India ($\sim 500$BC ?)~:}
\end{frame}

\begin{frame}
 \frametitle{Madhava's formula for $\pi$}

Early calculations of $\pi$ were done by Greek and Indian mathematicians
several centuries BC.\pause

These early evaluations used polygon approximations and Pythagoras
theorem. In this way, using 96 sides, Archimedes got
\alert{$3+\frac{10}{71}<\pi<3+\frac{10}{70}$}
whose average is \alert{$3.1418$} (c.~230~BC).\kern-1cm\\
Chinese mathematicians reached 7 decimal places in 480 AD.\vskip4pt
\pause
The next progress was the discovery of the first 
\alert{infinite series} formula by Madhava 
(circa 1350 -- 1450), a prominent mathematician-astronomer from Kerala
(formula rediscovered in the XVIIe century by Leibniz and Gregory)~:
\alert{$$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}
-\frac{1}{11}+\cdots+\frac{(-1)^n}{2n+1}+\cdots
$$}%
Convergence is unfortunately very slow, but Madhava was able to improve
convergence and reached in this way 11 decimal~places.\kern-1cm
\end{frame}

\begin{frame}
 \frametitle{Ramanujan's formula for $\pi$}
  \pgfdeclareimage[height=4.5cm]{ramanujan}{ramanujan}
  \pgfuseimage{ramanujan}
$~$\kern6mm\raise2cm\vbox{
Srinivasa Ramanujan (1887 -- 1920),\\
a self-taught mathematical prodigee.\\
His work dealt mainly with\\
\alert{arithmetics and function theory}}
$$\alert{\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum_{n=0}^{+\infty}\frac{(4n)!(1103+26390n)}{(n!)^4396^{4n}}}\qquad(1910).$$\pause
Each term is approximately \alert{$10^8$ times smaller} than the preceding one,
so the convergence is very fast.
\end{frame}

\begin{frame}
 \frametitle{Computational complexity theory}
$\bu$ Complexity theory is a branch of computer science and mathematics that :\\
-- tries to classify problems according to their difficulty\\
-- focuses on the \alert{number of steps (or time)} needed to solve them.
\kern-1cm
\pause
\vskip4pt
$\bu$ Let \alert{$N={}$size of the data} (e.g.\ for a decimal number, the number
$N$ of digits.)
\vskip4pt
A problem will be said to have \alert{polynomial complexity} if it requires
less than \alert{$C\,N^d$ steps} (or units of time) to be solved, where $C$ and
$d$ are constants ($d$ is the \alert{degree}). \pause 
\vskip4pt
$\bu$ Especially, it is said to have\\
-- \alert{linear complexity} when \alert{$\#\,$steps${}\le C\,N$}\pause\\
-- \alert{quadratic complexity} when \alert{$\#\,$steps${}\le C\,N^2$}\pause\\
-- \alert{quasi-linear complexity} when
\alert{$\#\,$steps${}\le C_\varepsilon\,N^{1+\varepsilon}$, $\forall\varepsilon>0$.}
\end{frame}

\begin{frame}
 \frametitle{First observations about complexity}
$\bu$ Addition has \alert{linear complexity}:\\
consider decimal numbers of the form $0.a_1a_2a_3\ldots a_N$, 
$0.b_1b_2b_3\ldots b_N$, we have
\alert{$$\sum_{1\le n\le N}a_n10^{-n}+\sum_{1\le n\le N}b_n10^{-n}
=\sum_{1\le n\le N}(a_n+b_n)10^{-n},$$}%
taking carries into account, this is done in $N$ steps at most.
\vskip4pt
\pause
$\bu$ What about multiplication ?\pause
\alert{$$\sum_{1\le k\le N}a_k10^{-k}\times\sum_{1\le\ell\le N}b_\ell10^{-\ell}
=\sum_{1\le n\le N}c_n10^{-n},\quad
c_n=\sum_{k+\ell=n}a_kb_\ell.$$}%
Calculation of each $c_n$ requires at most $N$ elementary multiplications and
$N-1$ additions and corresponding carries, thus the algorithm requires less
than $N\times 3N$ steps.\\
\vskip4pt
Thus multiplication has at most \alert{quadratic complexity}.
\end{frame}

\begin{frame}
\frametitle{The Karatsuba algorithm}
Can one do better than quadratic complexity for multiplication?\kern-1.5cm\pause
\vskip4pt
Yes !! It was discovered by Karatsuba around 1960 that multiplication has
complexity less than \alert{$C\,N^{\log_2 3}\simeq C\,N^{1.585}$}
\vskip4pt
Karatsuba's idea: for $N=2q$ even, split \alert{$x=0.a_1a_2\ldots a_N$} as
\alert{$$x=x'+10^{-q}x'',~~x'=0.a_1a_2\ldots a_q,~~x''=0.a_{q+1}a_{q+2}\ldots a_{2q}$$}%
and similarly $y=0.b_1b_2\ldots b_N=y'+10^{-q}y''$. To calculate $xy$,
one would normally need $x'y'$, $x''y''$ and $x'y''+x''y'$ which take 
4 multiplications
and 1 addition of $q$-digit numbers.\\
However, one can use only 3 multiplications by calculating
\alert{$$x'y',~~x''y'',~~x'y''+x''y'=x'y'+x''y''-(x'-x'')(y'-y'')$$}%
(at the expense of 4 additions).\pause\
One then proceeds inductively to conclude that the time $T(N)$ needed for 
$N=2^s$ satisfies
\alert{$$T(2^s)\le 3\,T(2^{s-1}) + 4\,2^{s-1}.$$}%
\end{frame}

\begin{frame}
\frametitle{Optimal complexity of multiplication}
It is an easy exercise to conclude
by induction that $T(2^s)\le 6\,3^s - 4\,2^s$ if one assumes $T(1)=1$, and so
\alert{$$T(2^s)\le 6\,3^s~~\Rightarrow~~ T(N)\le C\,N^{\log_23}.$$}%
\pause
It was in fact shown in 1971 by Schönage and Strassen that multiplication has
\alert{quasi-linear complexity}, less than
\alert{$$C\,N\,\log N\,\log\log N.$$}\pause
For this reason, the usual mathematical functions also have 
quasi-linear complexity at most~!\pause
\vskip4pt
The Schönage-Strassen algorithm is based on the use of 
\alert{discrete Fourier transforms}.
The theory comes from \alert{Joseph Fourier}, the founder 
of my university in 1810$\,$...
\end{frame}

\begin{frame}
 \frametitle{Joseph Fourier}
  \pgfdeclareimage[height=7.5cm]{jjfourier}{jjfourier}
  \pgfuseimage{jjfourier}
$~$\kern-2mm\raise4cm\vbox{
Joseph Fourier (1768 -- 1830)\\
in his suit of member of\\
Acad\'emie des Sciences,\\
of which he became\\
``Secr\'etaire Perp\'etuel''\\
(Head) in 1822.}
\end{frame}

\begin{frame}
\frametitle{Life of Joseph Fourier}
Born in 1768 in a poor family, Joseph Fourier quickly reveals himself
to be a scientific prodigee.\vskip4pt
\pause
Orphan from mother at age 8 and from father at age 10, he is sent
to a religious military school in the city of Auxerre, where he has
fortunately access to some important scientific books.\vskip4pt
\pause
He is just 16$\frac{1}{2}$ years when the director of his school asks him
to become the math teacher$\,$!\vskip4pt
\pause
At age 26, he becomes a Professor at Ecole Normale Sup\'erieure\kern-1cm\break
and \'Ecole Polytechnique. In 1798, he is chosen by Napoleon as his
main scientific advisor during the \alert{campaign of Egypt}.\vskip4pt
\pause
Back in France in 1802, he becomes the Governor of the Grenoble area
and founds the University. During this period, he discovers the
\alert{heat equation} and what is now called \alert{Fourier analysis}...\kern-1cm\vskip4pt
\pause
In 1824, he predicts the \alert{green house effect} !

\end{frame}

\begin{frame}
\frametitle{Heat equation and Fourier series}
Let \alert{$\theta(x,y,z,t)$} be the the temperature of a physical material
at a point $(x,y,z)$ and at time $t$.\vskip4pt
\pause
Fourier shows theoretically and experimentally around 1807
that $\theta(x,y,z,t)$ satisfies the propagation equation
\alert{$$
\theta'_t=D(\theta''_{xx}+\theta''_{yy}+\theta''_{zz}).
$$}
where $D$ is a constant characterizing the material.\vskip4pt
\pause
He then shows that in many cases the solutions can be expressed in
terms of trigonometric series
\alert{$$
f(x)=\sum_{n=0}^{+\infty}a_n\cos n\omega x+b_n\sin n\omega x
=\sum_{n=-\infty}^{+\infty}c_ne^{i n\omega x}$$}\pause
In fact all periodic phenomena can be described in this way. 
This is the basis of the modern theory of signal processing and
electromagnetism.
\end{frame}

\begin{frame}
\frametitle{Discrete Fourier transform}
Let $(a_n)_{0\le n<N}$ be a finite sequence of numbers and let
$u$ be a \alert{primitive $N$-th root of unity}, i.e.\ 
$$\alert{u^N=1\quad\hbox{but}\quad u^n\ne 1~~\hbox{for $0<n<N$}.}$$%
\pause
One can work with complex numbers and take \alert{$u=e^{2\pi i/N}$}.
\vskip4pt
\pause
When working with integers, it is easier to work modulo a large
prime number, e.g.\ $p=65537$ and take $N=p-1=65536$. Then
$u=3$ satisfies \alert{$u^N=1$ mod $p$} and one can check that $u=3$ is a 
primitive $N$-root of unity.
\vskip4pt
\pause
The discrete Fourier transform of $(a_n)$ is the sequence
$$
\alert{\widehat a_n = \sum_{k=0}^{N-1} a_ku^{kn}.}
$$\pause
It is convenient to consider that the index $n$ is defined \alert{mod~$N$}
(e.g.\ $a_{-n}$ means $a_{N-n}$ for $0<n<N$).\pause
\end{frame}

\begin{frame}
\frametitle{Main formulas of Fourier theory}
\claim{Fourier transform of a convolution:}\\
For $a=(a_n)$ and $b=(b_n)$ define $c=a*b$ to be the sequence
$$
\alert{c_n=\sum_{p+q=n\mod N}a_pb_q}\quad\hbox{``convolution of $a$
and $b$.''}
$$
Then~~ \alert{$\widehat c_n = \widehat a_n \widehat b_n$}.\vskip4pt
\pause
\justify{Proof}.~$\displaystyle
\sum_s c_su^{sn}=\sum_s \Big(\sum_{k+\ell=s}a_kb_\ell\Big)u^{sn}=
\sum_{k,\ell} a_ku^{kn}b_\ell u^{\ell n}=\widehat a_n \widehat b_n.$\kern-1cm
\vskip4pt
\pause
\claim{Fourier inversion formula:}
applying twice the Fourier transform, one gets
$$\alert{\widehat{\widehat a}_n = N\,a_{-n} = -a_{-n}~\mod~p}\qquad
\hbox{(recall $N=p-1$).}$$
\pause
\justify{Proof.} 
$\displaystyle
\widehat{\widehat a}_n=\sum_k\Big(\sum_\ell a_\ell u^{k\ell}\Big)u^{kn}=
\sum_\ell a_\ell\Big(\sum_ku^{k(n+\ell)}\Big)$ and
\alert{$\sum_ku^{k(n+\ell)}=0$} if $\ell\ne -n$ and 
\alert{$\sum_ku^{k(n+\ell)}=N$} if $\ell=-n$.\vskip4pt
\end{frame}

\begin{frame}
\frametitle{Fast Fourier Transform (FFT)}
\claim{Consequence:} To calculate the convolution $c=a*b$ (which is
what we need to calculate $\sum a_k10^{-k}\sum b_\ell10^{-\ell}$), one calculates
the Fourier transforms $(\widehat a_n)$, $(\widehat b_n)$, then
$\widehat c_n=\widehat a_n\widehat b_n$, which gives back $(-c_{-n})$ and thus
\alert{$(c_n)$ by Fourier inversion}.
\vskip4pt
\pause
This looks complicated, but the Fourier transform can be computed
extremely fast !!\vskip4pt
\claim{FFT algorithm:} assume that $N=2^s$ (in our example
$N=65536=2^{16}$) and define inductively $\alpha_{n,0}=a_n$ and
\alert{$$\alpha_{n,k+1}=\alpha_{n,k}+\alpha_{n+2^k}u^{2^kn},\quad
0\le k<s.$$}\pause
By considering the binary decomposition $n=\sum n_k2^k$, $0\le k<s$,\kern-1cm\\
of any integer $n=0...N-1$, one sees that \alert{$\alpha_{n,s}=\widehat a_n$}.
The calculation requires only $s$ steps, each of which requires
$N$ additions and $2N$ mutiplications (using $u^{2^{k+1}n}=(u^{2^kn})^2$),
so in total we consume only \alert{$3sN=3N\log_2 N$} operations~!
\end{frame}

\begin{frame}
\frametitle{Other mathematical functions}
OK about multiplication, but what for \alert{division} ? 
\alert{square root} ?\vskip4pt
\pause
Approximate division can be obtained solely from multiplication!\kern-1cm\\
If $x_0$ is a rough approximation of $1/a$, then the sequence
\alert{$$x_{n+1}=2x_n-ax_n^2$$}
satisfies $1-ax_{n+1}=(1-ax_n)^2$, and so inductively $1-ax_n=(1-ax_0)^{2^n}$
will converge extremely fast to $0$. In fact if $|1-ax_0|<1/10$ and 
$n\sim\log_2 N$, we get already $N$ correct digits. Hence we need
iterating only $\log_2 N$ times the sequence, and so \alert{division is 
also quasi-linear in time}.
\vskip4pt
\pause
Similarly, square roots can be approximated by using only
multiplications and divisions, thanks to the ``Babylonian
algorithm'':
\alert{$$
x_{n+1}={1\over 2}\Big(x_n+{a\over x_n}\Big),\qquad x_0>0
$$}
\ignore{which converges extremely fast to $\sqrt{a}$. In fact
$x_{n+1}-\sqrt{a}={1\over 2x_n}(x_n-\sqrt{a})^2\ge 0$, in particular
$x_n\ge\sqrt{a}$ and so $x_{n+1}-\sqrt{a}\le {1\over 2\sqrt{a}}(x_n-\sqrt{a})^2$ for $n\ge 1$, which implies again that $\approx\log_2 N$ steps suffice to get
$N$ correct digits.}
\end{frame}

\begin{frame}
\frametitle{What about $\pi$ ?}
\vskip-1mm
\pgfdeclareimage[height=4cm]{gauss}{gauss}
\pgfuseimage{gauss}
$~$\kern4mm\raise3mm\vbox{
In fact Carl-Friedrich Gauss (another\\
mathematical prodigee...) discovered\\
around 1797 the following formula for\\
the \alert{arithmetic-geometric mean}:\\
start from real numbers $a,b>0$ and\\
define inductively $a_0=a$, $b_0=b$ and\\
\alert{$\displaystyle
a_{n+1}={a_n+b_n\over 2},\qquad b_{n+1}=\sqrt{a_nb_n}.$}}
\vskip4pt\pause
Then $(a_n)$ and $(b_n)$ converge (extremely fast, only $\sim\log_2 N$ steps
to get $N$ correct digits) towards
\alert{$$
M(a,b)={2\pi\over I(a,b)}\quad\hbox{where}~
I(a,b)=\int_0^{2\pi}{dx\over\sqrt{a^2\cos^2x+b^2\sin^2x}}
$$}%
(an ``elliptic integral'').
\end{frame}

\begin{frame}
\frametitle{The Brent-Salamin formula}
Using this and another formula due to Legendre (1752 -- 1833),\kern-1cm\\
Brent and Salamin found in 1976 a remarkable formula for $\pi$. Define
$$c_n=\sqrt{a_n^2-b_n^2}$$
in the arithmetic-geometric sequence. Then
\alert{
$$\pi={4\,M(1,1/\sqrt{2})^2\over 1-\sum_{n=1}^{+\infty}2^{n+1}c_n^2}.
$$}\pause
As a consequence, the calculation of $N$ digits of $\pi$ is also a
quasi-linear problem!\vskip4pt
\pause
This formula has been used several times to break the world record, 
which seems to be 5 trillions digits since 2010 (however, there exist
so efficient quadratic complexity formulas that they are still
competitive at that level...)
\end{frame}

\begin{frame}
\frametitle{Complexity of matrix multiplication}
\claim{Question.} How many steps are necessary to compute the product
$C=AB$ of two $n\times n$ matrices, assuming that each elementary
multiplication or addition takes $1$ step?\vskip4pt
\pause
The standard matrix matrix multiplication algorithm
\alert{$$
c_{ik}=\sum_{1\le j\le n}a_{ij}b_{jk},\qquad 1\le i,k\le n
$$}%
leads to calculate $n^2$ coefficients, each of which requires 
$n$~multiplications and $(n-1)$ additions, so in total $n^2(2n-1)\sim 2n^3$
operations.\vskip4pt
\pause
However, the size of the data is $N=n^2$, and the general philosophy
that it should be quasi-linear would suggest an algorithm with
complexity less than \alert{$N^{1+\varepsilon}=n^{2+2\varepsilon}$}
for every $\varepsilon$.\vskip4pt
\pause
The fastest known algorithm, due to Coppersmith
and Winograd in 1987 has
\alert{\#steps${}\le C\,n^{2.38}$} (quite complicated!) 

\end{frame}

\end{document}