Esponenziazione veloce per quadrature successive

In questa pagina 7

Sia $D$ un dominio e $\circ : D \times D \to D$ un operatore binario associativo, $(a \circ b) \circ c = a \circ (b \circ c)$ , con elemento neutro $e$ , cioè $a \circ e = e \circ a = a$ per ogni $a \in D$ . Esempi: $D = \mathbb N$ con $\circ = +$ ( $e = 0$ ); matrici $n \times n$ con $\circ = \times$ (prodotto righe per colonne, $e = I_n$ ). L'operatore non deve essere commutativo.

Definizione (potenza). Per $x \in D$ e $n \in \mathbb N$ :

$x^n = \begin{cases} e & n = 0, \\ x \circ x^{n-1} = x^{n-1} \circ x & n > 0. \end{cases}$

Per $n \ge 1$ , $x^n = x \circ x \circ \dots \circ x$ ( $n$ fattori), senza parentesi per l'associatività.

L'uguaglianza $x \circ x^{n-1} = x^{n-1} \circ x$ vale per associatività anche per operatori non commutativi (come il prodotto di matrici). Il modello di costo assegna costo $1$ a ogni applicazione di $\circ$ e costo $0$ al resto. Si cerca un algoritmo efficiente per $x^n$ .

Algoritmo basato sulla definizione

STUPID_POWER(x, n)
  if n = 0 then return e
  p <- x
  for i <- 1 to n - 1 do
    p <- x ∘ p
  return p

La definizione è ricorsiva, ma è una ricorsione di coda, eliminabile in un ciclo. $T_{SP}(n) = n - 1 = \Theta(n)$ : lineare nell'esponente. Si vuole battere questo valore.

Proprietà di sottostruttura

Proprietà. Sia $k = \lfloor \frac n2 \rfloor$ .

Se $n = 2k$ è pari: $x^n = x^k \circ x^k$ .

Se $n = 2k + 1$ è dispari: $x^n = x^k \circ x^k \circ x$ .

Dimostrazione. Per $n = 2k$ : $x^{2k} = x^{k + k} = x^k \circ x^k$ , perché l'associatività permette di raggruppare i $2k$ fattori in due gruppi da $k$ . Per $n = 2k + 1$ : $x^{2k+1} = x^{k + k + 1} = x^k \circ x^k \circ x$ , con un fattore in più. Nessuna ipotesi su $\circ$ oltre l'associatività. $\blacksquare$

La proprietà lega $x^n$ a $x^{\lfloor n/2 \rfloor}$ : noto $y = x^{\lfloor n/2 \rfloor}$ , bastano una applicazione di $\circ$ se $n$ è pari ( $x^n = y \circ y$ ) e due se è dispari ( $x^n = y \circ y \circ x$ ). Per $n$ pari, a partire da $x^{n/2}$ la definizione richiederebbe ancora $\frac n2$ applicazioni, qui ne basta una: si quadra il valore. Gli algoritmi di questo tipo sono detti di squaring.

Algoritmo ricorsivo POWER

POWER(x, n)
  if n = 0 then return e                { BASE }
  if n = 1 then return x
  k <- floor(n / 2)                     { DIVIDE: nessun lavoro }
  y <- POWER(x, k)                      { RECURSE }
  if EVEN(n) then return y ∘ y          { CONQUER }
  else return y ∘ y ∘ x

Il caso base $n = 1$ sarebbe superfluo (si otterrebbe ricorsivamente), ma evita due applicazioni inutili di $\circ$ (con $y = e$ si farebbe $e \circ e \circ x$ ). La correttezza discende da quella della proprietà di sottostruttura.

Analisi

Il conquer costa al più $2$ (per $n$ dispari), il divide $0$ :

$T(n) \le \begin{cases} 0 & n = 0, 1, \\ T\!\left(\lfloor \frac n2 \rfloor\right) + 2 & n > 1. \end{cases}$

Per i valori $n = 2^t - 1$ ogni istanza generata è dispari ( $\lfloor \frac{2^t - 1}{2} \rfloor = 2^{t-1} - 1$ ): il costo è $2$ a ogni livello, quindi il limite $2$ è raggiunto. La ricorrenza è del tipo del Master Theorem - enunciato, casi e applicazioni con $a = 1$ , $b = 2$ , $w(n) = 2$ : la soglia è $n^{\log_2 1} = n^0 = 1 = \Theta(w(n))$ , caso 2, e $T(n) = \Theta(\log n)$ . Il Master Theorem copre dunque anche soluzioni logaritmiche; la stessa ricorrenza è quella della ricerca binaria. Il risultato è un miglioramento esponenziale rispetto a STUPID_POWER.

Conto esatto. Sia $k = \lfloor \log_2 n \rfloor$ e $\nu(n)$ il numero di bit a $1$ della rappresentazione binaria di $n$ . Per $n \ge 1$ :

$T_{POWER}(n) = \lfloor \log_2 n \rfloor + \nu(n) - 1.$

Dimostrazione per induzione su $n$ (vedi Dimostrazioni, induzione e invarianti). Base: $n = 1$ dà $0 + 1 - 1 = 0$ . Se $n \ge 2$ è pari, $T(n) = T(\frac n2) + 1$ ; poiché $\lfloor \log_2 \frac n2 \rfloor = \lfloor \log_2 n \rfloor - 1$ e $\nu(\frac n2) = \nu(n)$ (si toglie uno $0$ finale), $T(n) = \bigl( \lfloor \log_2 n \rfloor - 1 \bigr) + \nu(n) - 1 + 1 = \lfloor \log_2 n \rfloor + \nu(n) - 1.$ Se $n \ge 3$ è dispari, $T(n) = T(\frac{n-1}{2}) + 2$ ; ora $\lfloor \log_2 \frac{n-1}{2} \rfloor = \lfloor \log_2 n \rfloor - 1$ e $\nu(\frac{n-1}{2}) = \nu(n) - 1$ (si toglie l'ultimo bit, che è $1$ ), quindi $T(n) = \bigl( \lfloor \log_2 n \rfloor - 1 \bigr) + \bigl( \nu(n) - 1 \bigr) - 1 + 2 = \lfloor \log_2 n \rfloor + \nu(n) - 1. \qquad \blacksquare$

In parole: $\lfloor \log_2 n \rfloor$ quadrature (una per ogni livello) più $\nu(n) - 1$ moltiplicazioni per $x$ (una per ogni bit a $1$ tranne il primo). Il minimo su $2^k \le n < 2^{k+1}$ è $k$ ( $n$ potenza di $2$ ) e il massimo $2k$ ( $n = 2^{k+1} - 1$ , tutti bit a $1$ ). Per $n = 2^t$ la formula generale (Albero della ricorrenza e formula generale per le ricorrenze) con $s = 1$ , $f(n) = \frac n2$ , $w = 1$ dà $T(n) = \sum_{\ell=0}^{\log_2 n - 1} 1 = \log_2 n$ .

Esempio ( $x^{13}$ ). $13 \to 6 \to 3 \to 1$ . POWER(x,1) $= x$ (nessuna operazione); POWER(x,3): $y = x$ , dispari, $y \circ y \circ x = x^3$ ( $2$ operazioni); POWER(x,6): $y = x^3$ , pari, $y \circ y = x^6$ ( $1$ ); POWER(x,13): $y = x^6$ , dispari, $y \circ y \circ x = x^{13}$ ( $2$ ). Totale $5 = \lfloor \log_2 13 \rfloor + \nu(13) - 1 = 3 + 3 - 1$ , contro le $12$ di STUPID_POWER.

Osservazione sul costo. Il modello a costo unitario è ragionevole per somme e prodotti di interi o reali, ma non per operatori i cui risultati sono più grandi degli operandi (unione di insiemi, prodotto di polinomi, interi con tantissime cifre): lì l'analisi va rifatta con un modello di costo adeguato.

Algoritmi iterativi

I pacchetti di aritmetica non usano la ricorsione, per non pagarne i costi (nascosti dal modello). Si ottiene facilmente una versione iterativa con lo stesso numero di moltiplicazioni asintotico. Se $n = b_kb_{k-1}\dots b_0$ in binario, con $k = \lfloor \log_2 n \rfloor$ ( $\lfloor \log_2 n \rfloor + 1$ bit), $n = \sum_{i=0}^{k} b_i 2^i$ e per l'associatività

$x^n = \underset{i=0,\ b_i = 1}{\overset{k}{\circ}} x^{2^i}.$

Si accumulano quindi le potenze $x^{2^i}$ con $b_i = 1$ , e queste si ottengono iterativamente con $x^{2^i} = x^{2^{i-1}} \circ x^{2^{i-1}}$ .

POWER2(x, n)
  if n = 0 then return e
  * n = b_k b_{k-1} ... b_0 *
  p <- e                         { accumula le potenze x^(2^i) con b_i = 1 }
  s <- x                         { a inizio iterazione i: s = x^(2^i) }
  for i <- 0 to k do
    if b_i = 1 then p <- p ∘ s
    s <- s ∘ s
  return p

Conto letterale: un quadrato $s \circ s$ per ognuna delle $k + 1$ iterazioni e un prodotto $p \circ s$ per ognuno dei $\nu(n)$ bit a $1$ : $T_{POWER2}(n) = k + 1 + \nu(n) \le 2(k + 1) = 2(\lfloor \log_2 n \rfloor + 1)$ al caso peggiore, $\Theta(\log n)$ .

I bit non servono: si possono ottenere con il test di parità e la divisione intera, con una variabile $m$ inizializzata a $n$ (lo shift destro della rappresentazione di $m$ ):

POWER3(x, n)
  p <- e;  s <- x;  m <- n
  for i <- 0 to k do
    if NOT EVEN(m) then p <- p ∘ s
    s <- s ∘ s
    m <- floor(m / 2)
  return p

POWER3 esegue le stesse applicazioni di operatore di POWER, in ordine bottom-up: è come se eseguisse solo le fasi di conquer, risparmiandosi tutta la generazione top-down dell'albero.

Esempio ( $x^{13}$ , $13 = 1101_2$ ).

$i$	$b_i$	$p$ dopo il passo	$s$ dopo il passo
0	1	$e \circ x = x$	$x^2$
1	0	$x$	$x^4$
2	1	$x \circ x^4 = x^5$	$x^8$
3	1	$x^5 \circ x^8 = x^{13}$	$x^{16}$ (inutile)

Una precisazione sul conteggio. Le dispense affermano che POWER2/POWER3 eseguono esattamente le stesse applicazioni di $\circ$ di POWER. Contando letteralmente il codice di sopra, POWER3 ne esegue $k + 1 + \nu(n) = T_{POWER}(n) + 2$ (per $n = 13$ : $7$ contro $5$ ), per due ragioni: la prima moltiplicazione $p \circ s$ con $p = e$ non produce niente di nuovo, e l'ultimo quadrato $s \circ s$ calcola una potenza che non si usa. Con le due ottimizzazioni (partire da $p \leftarrow s$ al primo bit a $1$ , non quadrare dopo l'ultimo bit) i conteggi coincidono esattamente. Il confronto $T_{POWER3} = T_{POWER} + 2$ è stato controllato con un programma per $n$ da $2$ a $5000$ .

Verifica con un programma

python

def power_rec(n):                       # numero di applicazioni di o in POWER
    if n <= 1: return 0
    return power_rec(n // 2) + (1 if n % 2 == 0 else 2)

# per n = 1..5000: power_rec(n) == n.bit_length() - 1 + bin(n).count("1") - 1

Per ogni $n$ da $1$ a $5000$ vale $T_{POWER}(n) = \lfloor \log_2 n \rfloor + \nu(n) - 1$ , il massimo su $[2^k, 2^{k+1})$ è $2k$ e il minimo $k$ .

Esempio con matrici: numeri di Fibonacci

Con $\circ$ il prodotto di matrici $2 \times 2$ e $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ si ha $M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ (induzione: $M^{n+1} = M^n M$ ). Per $n = 13$ : $M \to M^2 \to M^3 \to M^6 \to M^{13}$ con POWER, e $M^{13} = \begin{pmatrix} 377 & 233 \\ 233 & 144 \end{pmatrix}$ , quindi $F_{13} = 233$ . Basta quindi $\Theta(\log n)$ prodotti di matrici $2 \times 2$ per calcolare $F_n$ (confronta con la ricorsione e la memoizzazione in Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma). Attenzione al modello di costo: $F_n$ ha $\Theta(n)$ cifre binarie, quindi le operazioni su scalari non sono più a costo unitario per $n$ grande. Lo stesso vale per matrici $n \times n$ qualsiasi: calcolare $A^m$ richiede $\Theta(\log m)$ prodotti di matrici, ciascuno da $2n^3 - n^2$ operazioni scalari con la definizione (Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi) o meno con Algoritmo di Strassen e ibridazione; per matrici con struttura (circolanti) il prodotto è più economico (Matrici circolanti e supercircolanti - algoritmi divide and conquer).

Esercizi collegati

Esercizio - domande di prima parte su moltiplicazione di matrici (simulazioni d'esame): domande di allenamento sul numero di applicazioni di $\circ$ di POWER.

Domande d'esame

Quante applicazioni dell'operatore esegue POWER(x, 31)? Risposta: $31 = 11111_2$ , $\lfloor \log_2 31 \rfloor = 4$ , $\nu = 5$ : $4 + 5 - 1 = 8$ (caso peggiore, $2 \cdot 4$ ; STUPID_POWER ne fa $30$ ). Traccia: $31 \to 15 \to 7 \to 3 \to 1$ , i quattro livelli dispari costano $2$ ciascuno.
Quale ricorrenza regola POWER e qual è la sua complessità? Traccia: $T(n) \le T(\lfloor \frac n2 \rfloor) + 2$ , $a = 1$ , $b = 2$ , $w = 2$ , soglia $n^0 = 1$ , caso 2 del Master Theorem: $\Theta(\log n)$ ; esatto $\lfloor \log_2 n \rfloor + \nu(n) - 1$ .
Quali proprietà dell'operatore servono? Traccia: solo associatività (e l'elemento neutro per $x^0$ ); non serve la commutatività, quindi vale per le matrici.

Versione ripasso

Setting: $\circ$ associativo con neutro $e$ (anche non commutativo, per esempio il prodotto di matrici con $e = I_n$ ); $x^0 = e$ , $x^n = x \circ x^{n-1} = x^{n-1} \circ x$ . Costo $=$ numero di applicazioni di $\circ$ .
STUPID_POWER: $p \leftarrow x$ , poi $n - 1$ volte $p \leftarrow x \circ p$ : $T = n - 1 = \Theta(n)$ .
Sottostruttura: con $k = \lfloor \frac n2 \rfloor$ , $x^n = x^k \circ x^k$ ( $n$ pari) e $x^n = x^k \circ x^k \circ x$ ( $n$ dispari). Dimostrazione: $x^{k+k}$ e $x^{k+k+1}$ , raggruppando per associatività. Da $y = x^k$ : $1$ applicazione (pari) o $2$ (dispari).
POWER: base $n = 0$ ( $e$ ) e $n = 1$ ( $x$ , evita due applicazioni inutili); divide $0$ ; $y \leftarrow$ POWER $(x, k)$ ; conquer $y \circ y$ oppure $y \circ y \circ x$ .
Ricorrenza: $T(n) \le T(\lfloor \frac n2 \rfloor) + 2$ , $T(0) = T(1) = 0$ . $a = 1$ , $b = 2$ , $w = 2$ , soglia $n^0 = 1$ : caso 2, $\Theta(\log n)$ (Master Theorem - enunciato, casi e applicazioni); è la ricorrenza della ricerca binaria. Il limite $2$ per livello è raggiunto da $n = 2^t - 1$ (tutte istanze dispari). Per $n = 2^t$ : $T = \log_2 n$ (formula generale con $s = 1$ , $w = 1$ ).
Esatto: $T(n) = \lfloor \log_2 n \rfloor + \nu(n) - 1$ $T (n) = ⌊ lo g_{2} n ⌋ + ν (n) - 1$ , con $\nu(n)$ $ν (n)$ numero di bit a $1$ $1$ .
- Induzione: base $n = 1$ dà $0$ .
- Pari: $T(\frac n2) + 1$ , con $\lfloor \log_2 \frac n2 \rfloor = \lfloor \log_2 n \rfloor - 1$ e $\nu(\frac n2) = \nu(n)$ .
- Dispari: $T(\frac{n-1}{2}) + 2$ , con $\nu(\frac{n-1}{2}) = \nu(n) - 1$ .
- Quindi: $\lfloor \log_2 n \rfloor$ quadrature e $\nu(n) - 1$ moltiplicazioni per $x$ . Minimo $k$ ( $n = 2^k$ ), massimo $2k$ ( $n = 2^{k+1} - 1$ ).
- Esempio $x^{13}$ : $13 \to 6 \to 3 \to 1$ , $2 + 1 + 2 = 5$ operazioni (contro $12$ ). Esempio $x^{31}$ : $4 + 5 - 1 = 8$ .
Iterativo: con $n = b_k \dots b_0$ $n = b_{k} \dots b_{0}$ in binario, $x^n = \circ_{b_i = 1}\, x^{2^i}$ $x^{n} = \circ_{b_{i} = 1} x^{2^{i}}$ e $x^{2^i} = x^{2^{i-1}} \circ x^{2^{i-1}}$ $x^{2^{i}} = x^{2^{i - 1}} \circ x^{2^{i - 1}}$ .
- POWER2: $p \leftarrow e$ , $s \leftarrow x$ ; per $i = 0..k$ : se $b_i = 1$ allora $p \leftarrow p \circ s$ ; poi $s \leftarrow s \circ s$ .
- Costo letterale $k + 1 + \nu(n) \le 2(\lfloor \log_2 n \rfloor + 1)$ , $\Theta(\log n)$ .
- POWER3: i bit si ottengono con EVEN $(m)$ e $m \leftarrow \lfloor \frac m2 \rfloor$ , con $m = n$ all'inizio.
- Esempio $13 = 1101_2$ : $p$ vale $x, x, x^5, x^{13}$ e $s$ vale $x^2, x^4, x^8, x^{16}$ .
- Il codice letterale fa $2$ applicazioni in più di POWER ( $e \circ s$ al primo bit a $1$ e l'ultimo quadrato inutile); con $p \leftarrow s$ al primo bit a $1$ e senza l'ultimo quadrato coincidono.
Fibonacci: $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ , $M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ , $F_n$ con $\Theta(\log n)$ prodotti $2 \times 2$ ( $M^{13}$ dà $F_{13} = 233$ ), purché si accetti il costo unitario sugli scalari.
Modello di costo: il costo unitario vale per somme e prodotti di interi o reali, non per operatori che ingrandiscono i risultati (unione di insiemi, prodotto di polinomi, interi lunghi, i numeri di Fibonacci grandi): serve un modello adeguato.
Errori tipici: usare il costo unitario con operandi che crescono; omettere il caso base $n = 1$ ; contare $\log_2 n$ invece dei $\lfloor \log_2 n \rfloor + 1$ bit; pensare che serva la commutatività (basta l'associatività).