Algorithm  Time  Space 
Multiplication  M(n) = n log n loglog n  n 
Division  M(n)  n 
Differential equations  M(n)  n 
Holonomic functions  n  n 
Algebraic composition  M(n) log n  n 
General composition  M(n) (n log n)^{1/2}  n log n 
Composition in finite characteristic  M(n) log n  n 
log f = log  f_{0} +  ó õ 


= g  

, 
f ° g = (f 

+ z^{p/2} f 

) ° g = f 

° g + g^{p/2} (f 

° g), 

= g_{1} z + ... + g_{q} z^{q}  

= g_{q+1} z^{q+1} + ... + g_{n} z^{n}, 
f ° g = f ° g 

+ (f' ° g 

) g 

+ 

(f'' ° g 

) (g 

)^{2} + ··· . 
f^{(i)} ° g 

= 



f^{(i1)} ° g 

= f_{i1} + i  ó õ 
æ ç ç è 

f^{(i)} ° g 

ö ÷ ÷ ø 
g' 

. 
g_{2}  2  
g_{1}  1  2  
g_{0}  0  1  2 
×  f_{0}  f_{1}  f_{2} 
g =  ó õ f' g. 
g_{2}  2  
g_{1}  1  1  
g_{0}  0  1  2 
×  f_{0}  f_{1}  f_{2} 
g_{3}  3  3  3  3 
g_{2}  2  3  2  3 
g_{1}  1  1  3  3 
g_{0}  0  1  2  3 
×  f_{0}  f_{1}  f_{2}  f_{3} 
Algorithm  Times  Space 
Karatsuba's multiplication  n^{log}_{2}^{ 3}  n log n 
Multiplication via FFT  D(n) = M(n) log n  n 
Division  D(n)  n 
Differential equations  D(n)  n 
Holonomic functions  n  n 
Algebraic composition  D(n) log n  n 
General composition  D(n) (n log n)^{1/2}  n^{3/2} log n 
Composition in finished characteristic  D(n) log n  n log n 
f(x) = 

(  1+f(x+1)+f'(x)^{2}  ) 
http://www.inria.fr/RRRT/RR3973.html
.http://www.math.upsud.fr/~vdhoeven/
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.