Fachrat Informatik - Forum

Quoted

Original von PD
Hallo,
kann mir jemand erklären, wieso bei der Reduktion von ITADD auf BCOUNT (Anfang Kapitel 6) nach der berechnung der s_k nur noch l(n) Zahlen mit n+l(n) Bits zu addieren sind?
Insbesondere da 1<= k <=n , hat man doch zunächst n verschiedene s_k Zahlen mit jeweils l(n) Bits.

Eingabe:
n Zahlen a_i = a_{i, n - 1} ... a_{i, 0} mit je n Bits.

Es sei:
s_k = \sum_{i = 1}^n a_{i, k}

Es gilt also für 0 <= k < n:
s_k <= n.
s_k hat demnach l(n) Bits.


Es sei:
s_k = s_{k, l(n) - 1} ... s_{k, 0}

Somit:
s_k = \sum_{j = 0}^{l(n) - 1} s_{k, j} * 2^j

Wie bei LOGITADD gilt:
\sum_{i = 1}^n a_i
= \sum_{i = 1}^n \sum_{k = 0}^{n - 1} a_{i, k} * 2^k
= \sum_{k = 0}^{n - 1} \sum_{i = 1}^n a_{i, k} * 2^k
= \sum_{k = 0}^{n - 1} s_k * 2^k
= \sum_{k = 0}^{n - 1} \sum_{j = 0}^{l(n) - 1} s_{k, j} * 2^j * 2^k
= \sum_{j = 0}^{l(n) - 1} \sum_{k = 0}^{n - 1} s_{k, j} * 2^{j + k}

Man muß also l(n) Zahlen addieren, die durch Umordnung der Bits der s_k entstehen (die s_k sind mittels BCOUNT berechenbar).

Nun schätzen wir die Länge jeder dieser Zahlen ab. Es gilt:
\sum_{k = 0}^{n - 1} s_{k, j} * 2^{j + k}
<= \sum_{k = 0}^{n - 1} 2^{j + k}
= 2^j * \sum_{k = 0}^{n - 1} s_{k, j} * 2^k
< 2^j * 2^n
= 2^{j + n}
<= 2^{l(n) + n}

Demnach können wir jede dieser Zahlen mit l(n) + n Bits darstellen.