next up previous
Next: Inversenbildung durch geometrische Reihe NC 1 Up: Division nach Beame, Cook Previous: Division nach Beame, Cook

Division mittels Inversenbildung in NC 1

Annahme:

Es steht ein NC 1-Schaltkreis zur Verfügung, der zu einem gegebenen y $\epsilon$ $\mbox{\bf N }$$\backslash${0} das Inverse auf n Stellen berechnet ( $ \mathop {\rm inverse} $(y,n) ), also

0 $\displaystyle\leq$ $\displaystyle{\textstyle\frac{1}{y}}$ - $\displaystyle \mathop {\rm inverse} $(y,n) $\displaystyle\leq$ $\displaystyle{\textstyle\frac{1}{y\cdot 2^n}}$

Dann berechnet folgender NC 1-Algorithmus bei Eingabe von natürlichen Zahlen x $\geq$ 0, y > 0 den Quotienten q = $\lfloor$${\frac{x}{y}}$$\rfloor$ : 


 AC 0   n : = |x|  
 NC 1		   

 z : = $
\mathop {\rm inverse}
$(y,n)  
 NC 1		   

 r : = x - y $\cdot$ $\lfloor$x $\cdot$ z$\rfloor$  (,,Rest``)
 AC 0		   if  r $\geq$ y  then 

 q : = $\lfloor$x $\cdot$ z$\rfloor$ + 1  
		 		 else 		 

 q : = $\lfloor$x $\cdot$ z$\rfloor$

Beweis:

Für den Rest R : = x - q $\cdot$ y der Division muss gelten:

0 $\displaystyle\leq$ x - q $\displaystyle\cdot$ y < y

Ist nun 0 $\leq$ r < 2y in obigem Algorithmus gegeben, so ist der Algorithmus korrekt, denn: 


1. Fall: 

 0 $\leq$ r < y  

  $\Rightarrow$ R = x - q $\cdot$ y = x - y $\cdot$ $\lfloor$x $\cdot$ z$\rfloor$ = r  
2. Fall: 		 

 y $\leq$ r < 2y  

  $\Rightarrow$ R  

  = x - q $\cdot$ y = x - y $\cdot$ ($\lfloor$x $\cdot$ z$\rfloor$ + 1) =  
		 		 		

  = x - y $\cdot$ $\lfloor$x $\cdot$ z$\rfloor$ - y = r - y $\Rightarrow$ 0 $\leq$ R < y ,

also in beiden Fällen 0 $\leq$ R < y . Wir zeigen sogar:

0 $\displaystyle\leq$ r < y + 1

Beweis hierfür:

Per Definition galt
     0 $\displaystyle\leq$ $\displaystyle{\textstyle\frac{1}{y}}$ - $\displaystyle\underbrace{ \mathop {\rm inverse} \nolimits(y,n)}_{:=z}^{}$ $\displaystyle\leq$ $\displaystyle{\textstyle\frac{1}{y\cdot 2^n}}$ $\displaystyle\Rightarrow$   
     0 $\displaystyle\leq$ $\displaystyle{\frac{x}{y}}$ - x $\displaystyle\cdot$ z $\displaystyle\leq$ $\displaystyle{\textstyle\frac{1}{y}}$ $\displaystyle\cdot$ $\displaystyle{\frac{x}{2^n}}$ < $\displaystyle{\textstyle\frac{1}{y}}$,   

da n = |x| , d.h. 2n - 1 $\leq$ x < 2n $\Rightarrow$ ${\frac{x}{2^n}}$ < 1 . Weiter

     0 $\displaystyle\leq$ x - y $\displaystyle\cdot$ x $\displaystyle\cdot$ z < 1   
     0 $\displaystyle\leq$ x - y($\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$ + x $\displaystyle\cdot$ z - $\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$) < 1   
     y(x $\displaystyle\cdot$ z - $\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$) $\displaystyle\leq$ x - y $\displaystyle\cdot$ $\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$ < 1 + y(x $\displaystyle\cdot$ z - $\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$),   

und wegen 0 $\leq$ x $\cdot$ z - $\lfloor$x $\cdot$ z$\rfloor$ < 1 (nach Definition von $\lfloor$ $\cdot$ $\rfloor$ )

0 $\displaystyle\leq$ x - y $\displaystyle\cdot$ $\displaystyle\lfloor$x $\displaystyle\cdot$ z$\displaystyle\rfloor$ < 1 + y.

Also 0 $\leq$ r < y + 1 .

next up previous
Next: Inversenbildung durch geometrische Reihe NC 1 Up: Division nach Beame, Cook Previous: Division nach Beame, Cook
Andreas Abel
12/10/1997