Inversenbildung durch geometrische Reihe in NC ¹

Annahme:

Es stehen NC ¹-Schaltkreise zur Verfügung, die $\varepsilon^{i}_{}$ ( 0 $\leq$ $\varepsilon$ < 1 , 0 $\leq$ i < n ) berechnen.
Dann ist folgender Algorithmus zur Berechnung von z : = $\mathop {\rm inverse}$(y,n) in NC ¹und korrekt (sei y > 0):

 AC 0 $\qquad$   k : = |y|  
 AC 0		      

 $\varepsilon$ : = 1 - y $\cdot$ 2- k 
 NC 1		      berechne 

 $\varepsilon^{i}_{}$  für 

 i = 0,1,...,n - 1  parallel 
 NC 1		      

 z : = 2- k$\sum_{i=0}^{n-1}$$\varepsilon^{i}_{}$  

Beweis:

Zu zeigen ist 0 $\leq$ ${\frac{1}{y}}$ - $\mathop {\rm inverse}$(y,n) $\leq$ ${\frac{1}{y \cdot 2^n}}$ . Gesetzt ist k = |y| , d.h. 2^{k - 1} $\leq$ y < 2^k $\Longleftrightarrow$ 2^{- 1} $\leq$ y $\cdot$ 2^{- k} < 2⁰ $\Longleftrightarrow$ ${\frac{1}{2}}$ $\geq$ $\underbrace{1 - y \cdot 2^{-k}}_{:= \varepsilon}^{}$ > 0. Also können wir die geometrische Reihe wie folgt anwenden:

$${\textstyle\frac{1}{y}} {\frac{2^{-k}}{y \cdot 2^{-k}}} {\frac{2^{-k}}{1-(1-y\cdot 2^{-k})}} {\textstyle\frac{1}{1-\varepsilon}}$$ =

$$\sum_{i=0}^{\infty} \varepsilon^{i}_{} \sum_{i=0}^{n-1} \varepsilon^{i}_{} \varepsilon^{n}_{} \sum_{i=0}^{\infty} \varepsilon^{i}_{}$$ =

$$\sum_{i=0}^{n-1} \varepsilon^{i}_{} {\frac{\varepsilon^n}{1-\varepsilon}}$$ =

Mit $\mathop {\rm inverse}$(y,n) = 2^{- k}$\sum_{i=0}^{n-1}$$\varepsilon^{i}_{}$ erhalten wir

d : = $${\textstyle\frac{1}{y}}$$ - $$\mathop {\rm inverse}$$(y,n) = $${\frac{2^{-k}}{1-\varepsilon}}$$$$\varepsilon^{n}_{}$$ = $${\textstyle\frac{1}{y}}$$$$\varepsilon^{n}_{}$$,

denn 1 - y $\cdot$ 2^{- k} = $\varepsilon$ $\Longleftrightarrow$ 1 - $\varepsilon$ = y $\cdot$ 2^{- k} $\Longleftrightarrow$ 2^k(1 - $\varepsilon$) = y $\Longleftrightarrow$ ${\frac{2^{-k}}{1-\varepsilon}}$ = ${\frac{1}{y}}$ , und wegen $\varepsilon$ $\leq$ ${\frac{1}{2}}$ gilt ( d $\geq$ 0 klar)

0 $$\leq$$ d $$\leq$$ $${\textstyle\frac{1}{y\cdot 2^n}}$$.

Die Berechnung einer Potenz $\varepsilon^{n}_{}$ lässt sich auf die Berechnung des Produkts $\prod_{i=1}^{n}$x_i von n natürlichen Zahlen x₁,...,x_n zurückführen. Der naheliegendste Algorithmus dafür ist aber in NC ². Idee für einen NC ¹-Algorithmus:

log($$\prod_{i=1}^{n}$$x_i) = $$\sum_{i=1}^{n}$$(logx_i)

Zurückführung auf eine Summe von Logarithmen. Da wir nur Ganzzahl-Arithmetik zur Verfügung haben, benötigen wir den diskreten Logarithmus.