[Teoria] Moltiplicazione nel computer

[3m0o]

In una prova d'esame mi si chiede come esercizio
Scrivere un algoritmo \( \operatorname{FastPower}(a,n) \) che prende come input un numero \(a\) e un intero non negativo \(n \) e ritorna \(a^n \) ma la complessità computazionale dev'essere \( \Theta(\log n) \).

Ora io ho fatto così

Codice:

if n == 0
    return 1
ans = FastPower(a,  floor(n/2))
if n is even
   return ans * ans
else
  return ans* ans * a


Se diciamo che \( T(n) \) è il tempo richiesto per eseguire \( \operatorname{FastPower}(a,n) \) allora chiaramente \( T(n) = T(n/2) + \Theta(1) \) dove \( T(0) = \Theta(1) \) quindi per il teorema principale abbiamo che \( T(n) = \Theta( \log n ) \). E le soluzioni dicono esattamente questo.

Il punto è che mi è sorto un dilemma, evidentemente qui la complessità nel fare la moltiplicazione ans * ans oppure ans* ans * a è costante, ma allora perché se moltiplico due numeri interi di \(n \) cifre, ottengo una complessità di \( \Theta(n^2) \) o se fatto in modo furbo \( \Theta(n \log n) \), ma comunque non lineare. Com'è possibile questa distinzione ? Sarà una domanda banale, ma non sono un informatico e quindi magari mi sfugge qualcosa di come il computer interpreta una moltiplicazione tipo ans*ans dall'avere un risultato esatto tra due numeri interi.

[Quinzio]

Com'è possibile questa distinzione ?

A dire il vero la moltiplicazione si puo' implementare come una sequenza di shift e addizioni. Una sequenza lunga $\log n$.
Del resto l'elevamento a potenza e' una ripetizione di moltiplicazioni e una moltiplicazione e' una ripetizione di addizioni, quindi lo schema astratto di fondo e' lo stesso.
Non so onestamente perche' la complessita' della moltiplicazione venga data come $O(n^2)$.
Bisognerebbe guardarci meglio.

[apatriarca]

Qualsiasi algoritmo che dipende da un solo parametro limitato da una costante impiega un tempo costante per essere eseguito. Se il numero di cifre è insomma costante (come è il caso per operazioni su interi a 32/64 bit per esempio) allora il tempo di esecuzione sarà anch'esso costante. Il quadrato di una costante è anch'essa una costante. In pratica il tempo di esecuzione per una moltiplicazione è di pochi cicli del processore (dipende dal processore, dalla dimensione degli input...).

[3m0o]

Ho scritto \( \Theta(n \log n ) \) ma volevo scrivere \( \Theta(n^{\log_2(3)}) \).

Grazie apatriarca mi sa che ho capito dalla tua risposta cosa mi portava a confusione e a cui non avevo pensato.
Sostanzialmente sto interpretando due moltiplicazioni "diverse" come la stessa cosa in un certo senso.
Una in un certo senso è quella che avviene nel computer (nel ALU della CPU?). Quindi l'operazione moltiplicazione in un aritmetica a virgola mobile è a tempo costante per il computer e dipende dal processore, perché ad effettuare le operazioni, cioè a cambiare dei bit da 0 ad 1 nella memoria ci mette un numero costante (che dipende dal processore della macchina).
L'operazione moltiplicazione che impiega \( \Theta(n^2) \) o \( \Theta(n^{\log_2(3)}) \) è un algoritmo che deve restituire un risultato esatto in un aritmetica intera (o a virgola fissa).
Cioè se voglio un algoritmo che mi moltiplica ad esempio \(561884713 \cdot 371814703 \) voglio un risultato esatto. O un algoritmo che mi permetta di dare il risultato giusto di numeri razionali. \( 213789,3218479 \cdot 375101,3718555 \).

Quindi in un algoritmo quando fa tipo ans*ans, oppure una potenza etc, sono dei numeri a virgola flottante e quindi ci impiega un tempo costante (anche se sono interi) mentre se voglio ad esempio moltiplicare gli interi
\(A \cdot B= ( a_0 + a_1 10 + \ldots + a_n 10^n )\cdot( b_0 + b_1 10 + \ldots + b_n 10^n ) \) voglio un risultato esatto non nella memoria ma come output (che volendo in linea di principio potrebbe essere applicato anche da una persona con carta e penna e quindi non ha la limitazione di poter rappresentare solo un numero finito di numeri)
quindi possiamo utilizzare questo algoritmo per effettuare una qualunque delle infinita di possibili moltiplicazioni che ci sono tra interi.
Ad esempio l'algoritmo \( \Theta(n^{\log_2(3)}) \) è il seguente
\[ A \cdot B = ( A_1 \cdot 10^{n/2} + A_2 ) ( B_1 \cdot 10^{n/2} + B_2 ) \]
dove
\[ A_1 = a_0 + a_1 10 + \ldots + a_n 10^{n/2} \]
\[ A_2= a_{n/2 +1} + \ldots + a_n 10^{n/2} \]
\[ B_1 = b_0 + b_1 10 + \ldots + b_n 10^{n/2} \]
\[ B_2= b_{n/2 +1} + \ldots + b_n 10^{n/2} \]
e quindi fare le moltiplicazioni richiamare lo stesso algoritmo con le moltiplicazioni seguenti
\[ T_1 = A_1 B_1 \]
\[ T_2 = A_2 B_2 \]
e
\[ T_3 = (A_1 + A_2 ) (B_1 + B_2) \]
e poi restituire
\[ T_3 - (T_1 + T_2) \]
per il teorema principale ottieni che la complessità è
\[ T(n) = 3 T(n/2) + \Theta(n) = \Theta(n^{\log_2(3)} ) \]


o sto dicendo minchiate?

[apatriarca]

No, non hai capito. Provo con un esempio diverso. Supponiamo che tu debba fare una cena in cui devi preparare una pasta per un certo numero di persone. Senza avere alcuna idea di quante siano le persone, puoi solo dire che la quantità di pasta da comprare è lineare rispetto al numero di persone. Scriviamo quindi qualcosa come \(Q \propto P\) o \(Q \in \Theta(P)\) dove \(Q\) è la quantità di pasta e \(P\) è il numero di persone. Tuttavia, se sai che la quantità di persone è inferiore di una qualche costante, per esempio \(10\) allora puoi comprare una quantità di pasta che sarà sufficiente per la cena indipendentemente dal numero di persone che verranno a cena. Lo stesso vale per la moltiplicazione, se il numero di cifre è limitato, allora lo sarà anche il numero di operazioni necessarie per fare la moltiplicazione.

[3m0o]

Guarda che avevo capito quello che hai detto. Siccome i computer a 64bits ad esempio possono fare operazioni solo con 64bits allora ci impiega un tempo costante perché puoi limitare per una costante sufficientemente grande il numero di operazioni da fare. Quindi se \(n\)- ovvero il numero di cifre - è fisso come nel caso della virgola flottante (perché il computer non può fare operazioni più grande di un certo tipo) allora ci impiega un tempo costante.
Però se usi un algoritmo puoi dargli come input in linea teorica qualsiasi numero e puoi far tendere \(n\) all'infinito e in quel caso lì la complessità del tuo algoritmo non è costante ma cambia perché dipende da \(n\).

[apatriarca]

Si, l'idea è quella..

[3m0o]

Si, l'idea è quella..

Non ti leggo convinto

[apatriarca]

Sono convinto, anche se l'algoritmo che hai scritto è per numeri interi e non per numeri in virgola mobile per quanto il discorso sia alla fine lo stesso.