Algoritmi aritmetici: cosa sono, tutto sull’argomento.

Algoritmo di Booth

L’algoritmo del prodotto di Booth, o semplicemente algoritmo di Booth, è un algoritmo per il calcolo del prodotto tra due numeri binari con segno, espressi nella notazione complemento a due. Fu inventato dal fisico Andrew Donald Booth nel 1951, originariamente allo scopo di velocizzare i calcoli necessari a una ricerca che Booth stava svolgendo nel settore della cristallografia, avendo a disposizione una calcolatrice lenta nelle somme ma veloce nello shift.

Algoritmi di elevamento a potenza

In informatica, per algoritmi di elevamento a potenza si intende la serie di passaggi elementari che una generica CPU deve compiere per eseguire l’operazione di elevamento a potenza.

Algoritmo di Karatsuba

L’algoritmo di Karatsuba (1960) è un algoritmo di moltiplicazione rapida (subquadratica) per moltiplicare grandi numeri interi o polinomi. È stata proposta da Anatolii Alexeevich Karatsuba in un articolo scritto insieme a Yuri Ofman nel 1962. La sua complessità è Θ, questo la rende più rapida della moltiplicazione ingenua che ha complessità Θ(n2).

Algoritmi di moltiplicazione

Per algoritmi di moltiplicazione si intende la serie di passaggi elementari che deve compiere una generica CPU per eseguire l’operazione di moltiplicazione senza ricorrere ad una banale addizione ripetuta.

Moltiplicazione Toom-Cook

Toom-Cook è stato, assieme all’algoritmo di Karatsuba, il primo algoritmo per la moltiplicazione di interi ad avere complessità meno che quadratica. Proposto nel 1963 da Andrei Toom in una forma involuta passante per il computo di due quadrati; è stato successivamente sistematizzato da Stephen Cook senza cambiarne la complessità asintotica, che è merito esclusivo del primo autore. È attualmente un algoritmo assestato ed ampiamente utilizzato per il prodotto di numeri interi grandi o polinomi.

Algoritmo per il calcolo della radice n-esima

La radice -esima,  di un numero reale  non negativo, è la soluzione reale non negativa dell’equazione

Metodi per il calcolo della radice quadrata

Questa voce è dedicata ai molti metodi che sono stati utilizzati per calcolare radici quadrate di numeri reali positivi, o per meglio dire, per calcolare le radici quadrate principali di numeri razionali.

Algoritmo di Schönhage-Strassen

L’algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da Arnold Schönhage e Volker Strassen nel 1971. La sua complessità, nella notazione O-grande, è O(n log n log log n). L’algoritmo usa ricorsivi Trasformate di Fourier veloci negli anelli con 22n + 1 elementi.


https://it.wikipedia.org/wiki/Categoria:Algoritmi_aritmetici

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: