Perché quadratura una serie più veloce di moltiplicare due numeri casuali?

https://stackoverflow.com/questions/1377430

21-09-2019
|

Domanda

La moltiplicazione di due numeri binari prende n ^ 2 tempo, ma la quadratura di un numero può essere fatto in modo più efficiente in qualche modo. (Con n è il numero di bit) Come può essere?

O non è possibile? Questa è follia!

Soluzione

Esistono algoritmi più efficiente di O (N ^ 2) per moltiplicare due numeri (vedi Karatsuba, Pollard, Schönhage-Strassen, ecc.)
I due problemi "moltiplica due numeri N-bit arbitrari" e "quadrato un numero arbitrario N bit" hanno la stessa complessità.

Abbiamo

4*x*y = (x+y)^2 - (x-y)^2

Quindi, se squadratura interi N bit richiede tempo O (f (N)), quindi il prodotto di due numeri interi arbitraria N-bit può essere ottenuto in O (f (N)) troppo. (Cioè 2x somme N bit, 2x N-bit piazze, 1x 2N-bit di somma, e 1x 2N bit shift)

E ovviamente abbiamo

x^2 = x * x

Quindi, se moltiplicare due numeri interi N-bit prende O (f (N)), poi la quadratura di un intero N-bit può essere fatto in O (f (N)).

Qualunque algoritmo di calcolo del prodotto (risp quadrato) fornisce un algoritmo per calcolare il quadrato (risp prodotto) con lo stesso costo asintotica.

Come osservato in altre risposte, gli algoritmi utilizzati per la moltiplicazione rapida possono essere semplificate nel caso della quadratura. Il guadagno sarà sulla costante davanti al f (N), e non su f (N) stesso.

Altri suggerimenti

La quadratura un numero di cifre n può essere più veloce di moltiplicare due numeri di cifre casuali n. Googling ho trovato questo articolo . Si tratta di arbitraria aritmetica precisione, ma può essere rilevante per ciò che il vostro richiesto. In esso gli autori dicono questo:

In squadratura un grande numero intero, ossia X ^ 2 = ^ 2 molti termini tra prodotti della forma xi (xn-1, xn-2, ..., x1, x0) * xj e xj * xi sono equivalenti. Essi devono essere calcolati solo una volta e poi sinistra spostata in modo da essere raddoppiato. Un'operazione n cifre squadratura è eseguita utilizzando solo (n ^ 2 + n) / 2 moltiplicazioni singola precisione.

Come altri hanno fatto notare, squadratura può essere solo circa 1,5x o 2x più veloce di moltiplicazione regolare tra i numeri arbitrari. Da dove viene il vantaggio computazionale viene? E 'la simmetria. Calcoliamo la piazza di 1011 e cercare di individuare un modello che possiamo sfruttare. u0:u3 rappresentano i bit nel numero dal più significativo al meno significativo.

    1011 //                               u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
   1011  //                     u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3       
  0000   //           u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3                 
 1011    // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3

Se si considera l'elementi ui * ui per i=0, 1, ..., 4 per formare la diagonale e ignorarli, vedrete che gli elementi ui * uj per i ≠ j sono ripetuti due volte.

Quindi, tutto quello che dovete fare è calcolare la somma del prodotto per gli elementi sotto la diagonale e raddoppiarlo, con uno spostamento a sinistra. Si potrebbe infine aggiungere gli elementi diagonali. Ora è possibile vedere dove l'2X accelerare proviene. In pratica, la velocità-up è di circa 1.5X a causa delle operazioni di diagonale ed extra.

Credo che si può essere riferisce a exponentiation elevando al quadrato . Questa tecnica non viene utilizzata per moltiplicare, ma per elevare a potenza x ^ n, dove n può essere grande. Invece di moltiplicare x si volte N volte, si esegue una serie di squadratura e aggiungendo operazioni che possono essere mappati alla rappresentazione binaria di N. Il numero di operazioni di moltiplicazione (che sono più costosi rispetto aggiunte per grandi numeri) è ridotto da N a log (N) rispetto all'algoritmo elevamento naive.

Vuoi dire moltiplicare un numero per una potenza di 2? Questo è di solito più veloce di moltiplicare due numeri casuali dal momento che il risultato può essere calcolato po 'semplice spostamento. Tuttavia, tenere a mente che i microprocessori moderni dedicare un sacco di silicio forza bruta per questi tipi di calcoli e la maggior parte aritmetica viene eseguita con velocità accecante rispetto ai microprocessori più anziani

ce l'ho!

2 * 2

è più costoso di

2 << 1

(L'avvertimento essendo funziona solo per un caso.)

Si supponga di voler ampliare la (a+b)×(c+d) moltiplicazione. Si divide in quattro singoli moltiplicazioni:. a×c + a×d + b×c + b×d

Ma se si desidera espandere fuori (a+b)², quindi ha bisogno soltanto tre moltiplicazioni (e un raddoppio):. a² + 2ab + b²

(Si noti inoltre che due delle moltiplicazioni sono essi stessi piazze.)

Speriamo che questo inizia solo per dare uno spaccato alcune delle incrementi nella velocità che sono possibili durante l'esecuzione di un quadrato su una moltiplicazione normale.

Prima di tutto grande domanda! Vorrei che ci fossero altre domande di questo tipo.

Così si scopre che il metodo mi è venuta è O (n log n) per la moltiplicazione generale solo la complessità aritmetica. È possibile rappresentare qualsiasi numero X come

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0

dove

x_i, y_i \in {0,1}

poi

XY = sum _ {k=0} ^ m+n r_k 2^k

dove

r_k = sum _ {i=0} ^ k x_i y_{k-i}

che è solo un'applicazione dritto in avanti di FFT per trovare i valori di r_k per ogni k in (n + m) log (n + m) tempo.

Poi, per ogni r_k è necessario determinare quanto grande sia il trabocco è e aggiungerlo di conseguenza. Per quadrare un numero questo significa O (n log n) aritmetica operazioni.

È possibile aggiungere i valori r_k più efficiente utilizzando l'Algoritmo di Schönhage-Strassen per ottenere un O (n log n log log n) bit legato.

La risposta esatta alla tua domanda è già postato da Eric Bainville.

Tuttavia, è possono ottenere una migliore limite di O (n ^ 2) per la squadratura un numero semplicemente perché non esistono limiti molto meglio per moltiplicare gli interi!

Se si assume lunghezza fissa alla dimensione della parola della macchina e che il numero da quadrato è nella memoria, un'operazione di squadratura richiede solo un carico di memoria, quindi potrebbe essere più veloce.

Per numeri interi di lunghezza arbitraria, moltiplicazione è tipicamente O (n²) ma ci sono algoritmi che riducono questo per grandi interi.

Se si assume l'approccio semplice O (n²) per moltiplicare a di b , quindi per ogni bit in a si deve spostare b e aggiungerlo a un accumulatore se questo bit è uno. Per ogni bit in a è necessario turni 3N e integrazioni.

Si noti che

( x - y )² = x² - 2 xy + y²

Quindi

x² = ( x - y )² + 2 xy - y²

Se ogni y è la più grande potenza di due non maggiore di x, questo dà una riduzione di un quadrato inferiore, due turni e due aggiunte. Come N si riduce ad ogni iterazione, è possibile ottenere un guadagno di efficienza (la simmetria significa che visita ogni punto in un triangolo invece di un rettangolo), ma è ancora O (n²).

Ci può essere un altro simmetria meglio sfruttare.

a ^ 2 (A + b) * (a + b) + b ^ 2 es. ^ 2 = 66 (66 + 6) (66-6) + 6 ^ 2 = 72 * 60 + 36 = 4356

per un ^ n basta usare la regola di potenza

66 ^ 4 = 4356 ^ 2

Vorrei risolvere il problema N po moltiplicazione per un numero

i bit sia A (n-1) (n-2) ........ A (1) A (0).

B i bit essere B (n-1) B (n-2) ........ B (1) B (0).

per il quadrato del numero A bit moltiplicazione univoca generata sarà per A (0) -> A (0) .... A (n-1) A (1) -> A (1) .... A (n-1), e così via così le operazioni totali saranno

OP = n + n-1 + n-2 ....... + 1 Pertanto OP = n ^ 2 + n / 2; quindi la notazione asintotica sarà O (n ^ 2)

e per la moltiplicazione di A e B n ^ 2 moltiplicazioni uniche verrà generato quindi la notazione asintotica sarà O (n ^ 2)

La radice quadrata di 2 ⁿ è di 2 ^{n / 2} o 2 ^{n >> 1}, quindi se il vostro numero è una potenza di due tutto è assolutamente semplice, una volta si conosce la potenza. Per moltiplicare è ancora più semplice: 2 ⁴ * 2 ⁸ è di 2 ^{4 + 8}. Non c'è alcun senso in questo affermazioni che hai fatto.

Se si dispone di un numero binario A, si può (sempre, la prova lasciato al lettore desideroso) essere espressa come (2 ^ n + B), questo può essere squadrato come 2 ^ 2n + 2 ^ (n + 1) B + B ^ 2. Possiamo quindi ripetere l'espansione, fino ad un punto tale che B è uguale a zero. Non ho guardato troppo duro, ma intuitivamente, ci si sente come se si dovrebbe essere in grado di fare una funzione di squadratura prendere meno passaggi algoritmici di una moltiplicazione general-purpose.

Credo che tu sia completamente sbagliato nelle istruzioni

La moltiplicazione di due numeri binari prende n ^ 2 tempo

La moltiplicazione di due numeri a 32 bit prendono esattamente un ciclo di clock. Su un processore a 64 bit, presumo che moltiplicare due numeri a 64 bit prendono esattamente 1 ciclo di clock. Non sarebbe nemmeno una sorpresa a mia che un processore a 32 bit può moltiplicare due numeri a 64 bit in un ciclo di clock 1.

yet squaring a number can be done more efficiently somehow.

quadratura un numero è solo moltiplicando il numero con se stesso, in modo che è solo una semplice moltiplicazione. Non v'è alcuna operazione "piazza" nella CPU.

Forse si è confuso "quadratura" con "moltiplicando per una potenza di 2". Moltiplicando per 2 può essere implemeted spostando tutti i bit di una posizione verso "sinistra". Moltiplicando per 4 sta spostando tutti i bit due posizioni verso "sinistra". Da 8, 3 posizioni. Ma questo trucco si applica solo a una potenza di due.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow