Division nach Beame, Cook und Hoover

Andreas Abel

19. November 1996, 5. März 1997

1 Division mittels Inversenbildung in NC^{1}

Annahme: Es steht ein NC^{1}-Schaltkreis zur Verfügung, der zu einem gegebenen y ϵ N\{0} das Inverse auf n Stellen berechnet (inverse(y, n)), also

0 ≤ \frac{1}{y} − inverse(y, n) ≤ \frac{1}{y · 2^{n}}

Dann berechnet folgender NC^{1}-Algorithmus bei Eingabe von natürlichen Zahlen x ≥ 0, y > 0 den Quotienten q = ⌊\frac{x}{y}⌋:

AC^{0} n := |x| NC^{1} z := inverse(y, n) NC^{1} r := x − y · ⌊x · z⌋ (,,Rest“) AC^{0} if r ≥ y then q := ⌊x · z⌋ + 1

else q := ⌊x · z⌋

Beweis: Für den Rest R := x − q · y der Division muss gelten:

0 ≤ x − q · y < y

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

1. Fall: 0 ≤ r < y ⇒ R = x − q · y = x − y · ⌊x · z⌋ = r

2. Fall: y ≤ r < 2y⇒ R = x − q · y = x − y · (⌊x · z⌋ + 1) = = x − y · ⌊x · z⌋ − y = r − y ⇒ 0 ≤ R < y,

also in beiden Fällen 0 ≤ R < y. Wir zeigen sogar:

0 ≤ r < y + 1

Beweis hierfür: Per Definition galt

0 ≤ \frac{1}{y} − \underbrace{inverse(y, n)}_{:=z} ≤ \frac{1}{y · 2^{n}} ⇒

0 ≤ \frac{x}{y} − x · z ≤ \frac{1}{y} · \frac{x}{2^{n}} < \frac{1}{y},

da n = |x|, d.h. 2^{n−1} ≤ x < 2^{n} ⇒ \frac{x}{2^{n}} < 1. Weiter

0 ≤ x − y · x · z < 1
0 ≤ x − y(⌊x · z⌋ + x · z − ⌊x · z⌋) < 1
y(x · z − ⌊x · z⌋) ≤ x − y · ⌊x · z⌋ < 1 + y(x · z − ⌊x · z⌋),

und wegen 0 ≤ x · z − ⌊x · z⌋ < 1 (nach Definition von ⌊·⌋)

0 ≤ x − y · ⌊x · z⌋ < 1 + y.

Also 0 ≤ r < y + 1.

2 Inversenbildung durch geometrische Reihe in NC^{1}

Annahme: Es stehen NC^{1}-Schaltkreise zur Verfügung, die ε^{i} (0 ≤ ε < 1, 0 ≤ i < n) berechnen. Dann ist folgender Algorithmus zur Berechnung von z := inverse(y, n) in NC^{1} und korrekt (sei y > 0):

AC^{0} k := |y| AC^{0} ε := 1 − y · 2^{−k} NC^{1} berechne ε^{i} für i = 0, 1, ..., n − 1 parallel NC^{1} z := 2^{−k} ∑_{i=0}^{n−1} ε^{i}

Beweis: Zu zeigen ist 0 ≤ \frac{1}{y} − inverse(y, n) ≤ \frac{1}{y·2^{n}}. Gesetzt ist k = |y|, d.h.

2^{k−1} ≤ y < 2^{k} ⟺ 2^{−1} ≤ y · 2^{−k} < 2^{0} ⟺ \frac{1}{2} ≥ \underbrace{1 − y · 2^{−k}}_{:=ε} > 0. Also können

wir die geometrische Reihe wie folgt anwenden:

\frac{1}{y} = \frac{2^{−k}}{y · 2^{−k}} = \frac{2^{−k}}{1 − (1 − y · 2^{−k})} = 2^{−k} \frac{1}{1 − ε} =
= 2^{−k} ∑_{i=0}^{∞} ε^{i} = 2^{−k}(∑_{i=0}^{n−1} ε^{i} + ε^{n} ∑_{i=0}^{∞} ε^{i})
= 2^{−k}(∑_{i=0}^{n−1} ε^{i} + \frac{ε^{n}}{1 − ε})

Mit inverse(y, n) = 2^{−k} ∑_{i=0}^{n−1} ε^{i} erhalten wir

d := \frac{1}{y} − inverse(y, n) = \frac{2^{−k}}{1 − ε}ε^{n} = \frac{1}{y}ε^{n},

denn 1 − y · 2^{−k} = ε ⟺ 1 − ε = y · 2^{−k} ⟺ 2^{k}(1 − ε) = y ⟺ \frac{2^{−k}}{1−ε} = \frac{1}{y}, und wegen ε ≤ \frac{1}{2} gilt (d ≥ 0 klar)

0 ≤ d ≤ \frac{1}{y · 2^{n}} .

Die Berechnung einer Potenz ε^{n} lässt sich auf die Berechnung des Produkts ∏_{i=1}^{n} x_{i} von n natürlichen Zahlen x_{1}, ..., x_{n} zurückführen. Der naheliegendste Algorithmus dafür ist aber in NC^{2}. Idee für einen NC^{1}-Algorithmus:

log(∏_{i=1}^{n} x_{i}) = ∑_{i=1}^{n}(log x_{i})

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

3 Zahlentheoretische Grundlagen

Die multiplikativen Gruppen

Z_{p}^{∗} = \{\overline{1}, \overline{2}, ..., \overline{p−1}\} (p prim)

sind zyklisch, d.h. es existiert ein Element g ϵ Z_{p}^{∗}, genannt Primitivwurzel, mit

Z_{p}^{∗} = {g^{0}, g^{1}, ..., g^{p−2}}.

Also existiert zu jedem x ϵ Z_{p}^{∗} ein a ϵ {0, 1, ..., p−2} mit

g^{a} ≡ x mod p.

Dieses heißt Index oder diskreter Logarithmus von x zur Basis g und wird mit ind_{g}(x) bezeichnet. Mit diesen zahlentheoretischen Hilfsmitteln können wir in der Tat iterierte Multiplikation auf iterierte Addition zurückführen; denn ist P > ∏_{i=1}^{n} x_{i} prim und g eine Primitivwurzel von Z_{p}^{∗}, so gilt

∏_{i=1}^{n} x_{i} ≡ ∏_{i=1}^{n} g^{ind_{g}(x_{i})} ≡ g^{∑_{i=1}^{n} ind_{g}(x_{i})} mod P.

Es stellt sich aber heraus, dass es nur für kleine m NC^{1}-Algorithmen zur Berechnung von x mod m oder des diskreten Logarithmus in Z_{m}^{∗} gibt. Abhilfe schafft hier ein weiterer Satz der Zahlentheorie, der Chinesische Restsatz. Doch zuerst der

Algorithmus zur Berechnung von x mod m für kleine m

Eingabe: x = ∑_{i=0}^{n−1} x_{i}2^{i}, m ≤ n Ausgabe: x mod m

a_{im} := 2^{i} mod m

NC^{1} y := ∑_{i=0}^{n−1} x_{i}a_{im} (Es gilt y < n · m) NC^{1} Berechne parallel y − i · m für i = 0, ..., n−1 AC^{0} Wähle das kleinste y − i · m aus, das ≥ 0 ist, und gebe es aus.

Dabei werden die a_{im} in der Konstruktionsphase für alle i = 0, ..., m−1 und m = 2, ..., n berechnet und fest in den Schaltkreis eingebaut, alle anderen Schritte sind in NC^{1} .

4 Chinesischer Restsatz

Seien p_{1}, ..., p_{m} paarweise teilerfremde natürliche Zahlen und P := ∏_{i=1}^{m} p_{i}. Dann gibt es genau ein x ϵ Z_{P} mit

x_{1} ≡ x mod p_{1}
x_{2} ≡ x mod p_{2}
⋮
x_{m} ≡ x mod p_{m}

für x_{1} ϵ Z_{p_{1}}, ..., x_{m} ϵ Z_{p_{m}}. Sei v_{i} ϵ Z_{p_{i}} das Inverse zu \frac{P}{p_{i}} modulo p_{i} für alle i = 1, ..., m, d.h.

v_{i} · \frac{P}{p_{i}} ≡ 1 mod p_{i}.

Dann gilt

x ≡ ∑_{i=1}^{m} x_{i} · v_{i} · \frac{P}{p_{i}} mod P.

Beweis hierfür:

x ≡ x_{i} · \underbrace{v_{i} · \frac{P}{p_{i}}}_{≡1 mod p_{i}} + ∑_{j≠i} \underbrace{x_{j} · v_{j} · \frac{P}{p_{j}}}_{≡0 mod p_{i}, da p_{j}|P} mod p_{i}

Annahme: Wir haben NC^{1}-Algorithmen, die P := ∏_{i=1}^{m} p_{i} und \frac{P}{p_{i}} für i = 1, ..., m berechnen. Dann ist folgender Algorithmus, der den Chinesischen Restsatz anwendet, d.h. zu gegebenen paarweise teilerfremden

1 < p_{1} < p_{2} < ... < p_{m} ≤ m^{2}

und

x_{i} = (x mod p_{i}) (i = 1, ..m)

x berechnet, korrekt und in NC^{1}:

NC^{1} (1) Berechne P := ∏_{i=1}^{m} p_{i}. NC^{1} (2) Berechne \frac{P}{p_{i}} für i = 1, 2, ..., m parallel. NC^{1} (3) Löse die Gleichungen v_{i} · \frac{P}{p_{i}} ≡ 1 mod p_{i} für i = 1, ..., m parallel.

(Z.B. durch Ausprobieren)

NC^{1} (4) Berechne v_{i} · \frac{P}{p_{i}} für i = 1, ..., m parallel. NC^{1} (5) Berechne x_{i} · v_{i} · \frac{P}{p_{i}} für i = 1, ..., m parallel. NC^{1} (6) Berechne y := ∑_{i=1}^{m} x_{i} · v_{i} · \frac{P}{p_{i}}

Das gesuchte Ergebnis ist nun

y mod P = y − t · P, t = ⌊\frac{y}{P} ⌋ .

Im folgenden leiten wir uns die Berechnung von t her: Sei k die kleinste Zweierpotenz ≥ m, k = 2^{⌈log_{2} m⌉}.

\frac{y}{P} = ∑_{i=1}^{m} \frac{x_{i}v_{i}}{p_{i}} = \frac{1}{k} ∑_{i=1}^{m} \frac{kx_{i}v_{i}}{p_{i}} ≥ \frac{1}{k} ∑_{i=1}^{m} ⌊\frac{kx_{i}v_{i}}{p_{i}} ⌋ =: s ⇒
0 ≤ y − s · P = \frac{1}{k} ∑_{i=1}^{m} \underbrace{(\frac{kx_{i}v_{i}}{p_{i}} − ⌊\frac{kx_{i}v_{i}}{p_{i}} ⌋)}_{<1} P <

< \frac{1}{k} ∑_{i=1}^{m} P = \underbrace{\frac{m}{k}}_{≤1} P ≤ P

Also gilt sicher: 0 ≤ y − ⌊s⌋P < 2P. Damit erhalten wir t wie folgt:

1. Fall: y − ⌊s⌋P < P ⇒ t = ⌊s⌋

2. Fall: y − ⌊s⌋P ≥ P ⇒ t = ⌊s⌋ + 1 Fortsetzung des Algorithmus:

NC^{1} (7) Berechne k · v_{i} · x_{i} für i = 1, ..., m parallel. ≤ NC^{1} (8) Berechne ⌊\frac{k·v_{i}·x_{i}}{p_{i}} ⌋ für i = 1, ..., m parallel.

Da p_{i} = O(log m) und k · v_{i} · x_{i} = O(log m) genügt ein einfacher Divisionsalgorithmus mit maximal linearer Komplexität (,,any reasonable division circuit“).

NC^{1} (9) Berechne ∑_{i=1}^{m} ⌊\frac{k·v_{i}·x_{i}}{p_{i}} ⌋.

NC^{0} (10) Berechne ⌊s⌋ = ⌊\frac{∑_{i=1}^{m}⌊\frac{k·v_{i}·x_{i}}{p_{i}} ⌋}{m}⌋ (shift right).

NC^{1} (11) if y − ⌊s⌋P < P then x := y − ⌊s⌋P NC^{1} else x := y − (⌊s⌋ + 1) P

5 Berechnung des iterierten Produkts

Eingabe: n n-bit-Zahlen x_{1}, ..., x_{n} Ausgabe: Produkt ∏_{i=1}^{n} x_{i}

Konstruktionsphase:

• Ermittle m paarweise verschiedene Primzahlen 1 < p_{1} < p_{2} < ... < p_{m} ≤ n^{2} mit

P := ∏_{i=1}^{m} p_{i} ≥ 2^{n^{2}} > ∏_{i=1}^{n} x_{n}

(immer möglich für n > 5).

• Ermittle einen Generator (Primitivwurzel) g_{i} für Z_{p_{i}}^{∗} und eine Tabelle der diskreten Logarithmen

g_{i}^{0}, g_{i}^{1}, ..., g_{i}^{p_{i}−2}

für i = 1, ..., m.

• Berechne \frac{P}{p_{i}} = ∏_{j≠i} p_{j} und v_{i}, das Inverse zu \frac{P}{p_{i}} modulo p_{i}.

Alle diese Werte werden fest in den Schaltkreis integriert.

Eigentlicher Schaltkreis (Berechnungen zur Laufzeit):

NC^{1} Berechne x_{i} mod p_{j} für i = 1, ..., n, j = 1, ..., m parallel. AC^{0} Lese die diskreten Logarithmen aus

l_{ij} := ind_{g_{j}}(x_{i} mod p_{j}) NC^{1} Berechne die Summen S_{j} := ∑_{i=1}^{n} l_{ij}. AC^{0} Lese die Anti-Logarithmen aus y_{j} := g_{j}^{S_{j}}. NC^{1} Berechne y := ∏_{i=1}^{n} x_{i} durch Anwendung des

Chinesischen Restsatzes auf y_{1}, ..., y_{m}.

Damit hätten wir den NC^{1}-Schaltkreis für Ganzzahl-Division vollständig realisiert. Da die Konstanten P und v_{i} · \frac{P}{p_{i}} vorausberechnet werden müssen, ist der Schaltkreis nicht log space-uniform, nur P-uniform, d.h. kann auf einer Touringmaschine mit polynomialem Platz auf dem Arbeitsband konstruiert werden. Es wurden jedoch auch log space-uniforme Schaltkreise gefunden, nur sind diese nicht in NC^{1}, sondern haben die Tiefe O(log n log log n).

Literatur

[1] Paul W. Beame, Stephen A. Cook, H. James Hoover, Log Depth Circuits for Division and Related Problems, Siam J. Comput. Vol. 15, No. 4, November 1986

[2] R. M. Karp, V. Ramachandran, ???

[3] Peter Clote, Manuskript für zukünftiges Buch über Komplexitätstheorie

[4] Otto Forster, Algorithmische Zahlentheorie, vieweg 1996