<\body> <\hide_expand|switch> \; \; |<\with|paragraph mode|center> <\with|font size|1.68|font shape|long> mais... Ne soyez pas trop paresseux <\with|color|blue> \\\\<\ diamondsuit\>> \; <\name> <\with|font size|1.19> <\with|font|chancery> Joris van der Hoeven <\with|color|blue> \\\\<\ diamondsuit\>> Sophia Antibes 13 décembre 2002 \; > > |||||||||||||||||||>|>>|>>>>>> \; \; <\enumerate> <\with|color|blue> L'approche zélée L'approche paresseuse L'approche détendue Résultats expérimentaux Coefficients particuliers \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; +\+f*z>>|+\+g*z>>>>>> +\+h*z=f*g+O(z)>. |<\itemize> Multiplication naïve en )>. Diviser pour régner en n 3>>. Multiplication F.F.T. en . > <|tuple> |||||||||||||||||||>|>>|>>>>>> |<\with|paragraph mode|center> \; \; ||||||||||>||>||>|>>>||>|>>>||>|>>>||>|>>>|>|>|>>>|>|>>|>>|>|>|>>>|\>compostion>|>>|>>>>>> : temps pour la multiplication > \; <|tuple> |||||||||||||||||||>|>>|>>>>>> pair, décomposer :> <\expand|equation*> >>||+\+f*z>>|>>||+\+f*\ z>>>>>>>||+\\ +g*z>>|>>|\ |+\+g*z>>>>> <\expand|eqnarray*> ||>*g<\ rsup|\>+f>*g>*z+>\ >|||>+f\ >)*(g>+g>)-f>*g<\ rsup|\>-f>*g>]*z>>>> |<\with|paragraph mode|center> ||||>>>||<\ cell|>*g>>>>|>>>|>*g>>>|>|>>|>>>|>>>>>>> \; |>>>>(f>+f>)*(g>+g>)-f>*g>-f\ >*g> > > \; <|tuple> |||||||||||||||||||>|>>|>>>>>> <\expand|equation*> log f=log f+|f> Pour pair, supposons <\expand|equation*> log g-f=O(z>), <\expand|equation*> +\+f*z ;>>|+\+g*z>>>>> Alors <\expand|equation*> =g-(log g-f)*g <\expand|equation*> \log -f=O(z>). > algorithme d'exponentiation en . <|tuple> |||||||||||||||||||>|>>|>>>>>> \; L'équation g-z=0> induit l'itération =g-g-z|f\g>> <|tuple> |||||||||||||||||||>|>>|>>>>>> \; <\with|color|blue> Entrées : <\itemize> +\+f*z> (avec \) > ; *z+\+g*z\ > (avec fixe) ; Un ordre p> (avec \>). +\+h*z>, telle que <\expand|equation*> h=f\g+O(z) \; <|tuple> |||||||||||||||||||>|2>>)>>>|>>>>>> \; <\expand|equation*> f\g=f>\g+(f>\g\ )>g Algorithme en temps M(n)*log n)>, car |<\itemize> +> multiplications de longueur . > multiplications de longueur . > multiplications de longueur ; Etc. multiplications de longueur . > \; \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; +\+f*z\ > et *z+\<\ space|-0.2spc>+g*z>\ +\+h*z> avec \g+O(z)> \; Idée : découper >+g>> <\expand|eqnarray*> >>||*z+\+g*z ;>>|>>||*z\ +\+g*z.>>>> Puis écrire : <\expand|equation*> f\g=f\g>+(f\g>)*g>+*(f\g>)*(g>)+\ <|tuple> |||||||||||||||||||>|>>|>>>>>> \g>>> Par itération direct ou inverse : \g>>||\g>)|g>> ;>>|*f\g>>\ ||+i**f\g>*g>.>>>>> \; <|tuple> |||||||||||||||||||>|>>|>>>>>> On considère des séries formelles comme des flots de coefficients. Les coefficients sont calculés un par un et à chaque étape on n'effectue que les calculs strictement nécessaires. Une série formelle est un algorithme qui ne prend rien en entrée et qui rend son premier coefficient > et la série ``reste'' )/z>. On calcule > dès que ,\,f> et ,\,g> sont connus. En particulier, > et > peuvent dépendre de ,\,(f*g)\ >. <|tuple> |||||||||||||||||||>|>>|>>>>>> \; Calcul de l'exponentielle > d'une série par f*g> On ne peut utiliser la multiplication F.F.T. ou diviser pour régner. \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; \; <\with|paragraph mode|center> > accélération> \; \; |||>>|>>|||>\ |>>|>|>|>|>>||>|>|>>|>>|\ >>|>>>>>>>>>>| |<\itemize> =f*g>. =\ *g>+*g>>. =f*g+*g>+f*g>. > >>>>|||>>|>>|||>|>>|>|>|>|>>|<\ cell|0>|>|>|>>|>>|>>|>>>>>>>>>>| |<\itemize> =f*g>. =|||||+f)*(g+g)>>>|*g\ -*g>>>>>>> =f*g+*g>+f*g>. > >>>> \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; La multiplication diviser-pour-régner est  essentiellement déten-due  : la formule pour > ne dépend que de ,\,f> et ,\,g>. =f*g> ; =(f+f)*(g+g)-f*g-f*g> ; =(f+f)*(g+g)-f*g-f*g> ; =(f+f+f+f)*(g+g+g+g)-(f+<\ space|0.2spc>f)*(g+g)-(f+f\ )*(g+g)+f*g\ +f*g+f*g+f*g> ; =(f+f)*(g+g)-f*g-f*g> ;|||||||||||>>||||>|>>||<\ cell|3>||>|>>||||>|>>|\ |||>|>>|>>|>\ >|>>|>>>>\ >>>>||0cm||0.3cm|> =(f+f)*(g+g)-f*g-f*g> ; =f*g>. > \; \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; <\with|paragraph mode|center> > Algorithme détendu en . <|tuple> |||||||||||||||||||>|>>|>>>>>> \; <\with|paragraph mode|center> \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; \; <\with|paragraph mode|center> \; <|tuple> |||||||||||||||||||>|>>|>>>>>> \; \; \; |||||||||||||| \ \ \ \ \ \ \ \ \ \ >|||||||||||||>|>|||||||||||<\ cell|5050>||>||||||||\ ||||||>|<\ row|>|||||<\ cell|18>||||||||>|>|||||||\ ||||||>||||||||||||||>||||||||||||||>>>>>>> \; \; <|tuple> |||||||||||||||||||>|>>|>>>>>> Algorithmes ``essentiellement détendues''. Changer dans l'algorithme de Brent & Kung pour 4>>. \; |<\with|paragraph mode|center> ||||||||||>||>|>| 3>>>|*log n>>>|>|>|>>>||>|\ >>>||>|>>>||>|>>>|>|>|>>>|>|>>|*log n>>>|>|>|>>>|\>compostion>|>>|>>\ >>>> : temps pour la multiplication détendue >> \; <|tuple> |||||||||||||||||||>|>>|>>>>>> )>> <\with|paragraph mode|center> <\with|font size|0.84> |||||||||||||||>|||||||\ ||>>|>|||||||||>|>|||||||||\ >|>|||||||||>|>||\ |||||||>|>|||||||||>>>|>|||||||||\ >>>> Big float coefficients \; <\with|font size|0.84> |||||||||||||||>|||||||>>|>|||||||>|>|||||||>|>|||||||>|>|||||||>|>|||||||>|>|||||||>>>> Rational coefficients \; <|tuple> |||||||||||||||||||>|>>|>>>>>> La série génératrice telle que > est le nombre d'alcools de la forme OH> vérifie <\expand|equation*> s(z)=1+z*+2*s(z)|3> <\with|font size|0.84> <\with|font size|0.71> <\with|paragraph mode|center> \ |||||||||||||||>||||||||||>>|\ >|||||\ |||||>|>|||\ |||||||>|>||||||||||>|>||||||||||>|>||||||||||>>>> Integer coefficients mod 1234577 \; |||||||||||||||>||||||||||>>|>||||||||||>|>||||||||||>|>||||||||||>|>||\ ||||||<\ cell|215.59>||>|>||||||||||>>>> Integer coefficients \; <|tuple> |||||||||||||||||||>|>>|>>>>>> L'équation différentielle aux différences *(1+f(x+1)+f(x))> admet une solution formelle unique en > : <\expand|equation*> f(x)=+>->-\ >+O> On réécrit () pour : 1+g-z*g(z)> <|tuple> |||||||||||||||||||>|>>|>>>>>> <\with|paragraph mode|center> <\with|font size|0.71> \; \; \; |||||||||||||||||||||||||>|>|||||||||>>|>|>|||||||||>||>|||||||||>||>|||||||||>|>|>|||||||||>||>||||||\ |||>||>|||||||||>|>|>|||||||||>||>|||||||||>||>|||||||||>>>> \; \; <|tuple> |||||||||||||||||||>|>>|>>>>>> Soit \[[x,y]]> telle que <\expand|eqnarray*> f|\ y>>|| f|\ x>+ f|\ x> ;>>|||.>>>> Problème : calculer *y] f>. \; \; ||0cm||0.3cm|>|> Série génératrice vérifie +z)> <|tuple> |||||||||||||||||||>|>>>|>>>>>> \; Benchmarks faussés par mauvaise arithmétique. F.F.T. généralisée pour ``anneaux denses''. <\expand|eqnarray*> ||10+1.000\10*z)>>|||\ 10+0.000\10*z+\ 1.000\10*z,>>>> puisque 10+1.000\10=1.000\10>. transformation \*z>. <|tuple> |||||||||||||||||||>|>>|>>>>>> \; |>> multiplication tronquée plus fine ou modulaire. > <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |2>> |3>> |3>> > |3>> |3>> |4>> |4>> > >