Le potenze nello studio degli algoritmi

[Peternek]

Ciao a tutti! Vi chiedo di aiutarmi con un dubbio: studiando una materia molto simile a "dati e algoritmi" (quella materia astratta dove si usano solo pseudocodici) mi sono accorto che nella soluzione di un esercizio invece di trascurare il calcolo della potenza ad esempio con un fissato, dice che sarebbe necessario un tempo per calcolarla.
In java o altri linguaggi io farei senza chiedermi quanto ci impiega la macchina, sperando che il tempo sia bassissimo. In realtà non so quanto ci impiegano, sarebbe diciamo il classico tempo necessario n queste situazioni, o quello che si usa per convenzione negli algoritmi?

[EdmondDantes]

Non ho capito bene, ma cerco di dedurre.
Se scrivi un algoritimo con complessità n^k, con k molto elevato, il tempo di esecuzione è dell'ordine dei secoli. Tutt'altro che trascurabile.
Bisognerebbe scrivere un algoritimo con complessità log(n) o al più n*log(n) in modo da ridurre il tempo di esecuzione all'ordine delle decine di secondi.

[Peternek]

Si chiedo scusa non sono riuscito a spiegarmi bene usando la : volevo dire che se dovessi fare un operazione aritmetica dentro al codice ad esempio int s = 4^k . Questa riga di codice di solito ci mette ad essere eseguita dalla macchina?
Per quindi non intendevo la complessità dell'algoritmo ma un qualsiasi parametro

[Exodus]

ad esempio int s = 4^k . Questa riga di codice di solito ci mette \log k ad essere eseguita dalla macchina?

Quello che tu chiami macchina penso che sia il sistema processore , memoria etc...
Se tu scrivi quella potenza in un linguaggio ad alto livello, la prima cosa da valutare sarà il compilatore, ovvero come ottimizza tale espressione.
La seconda cosa il tipo di processore sulla quale verrà eseguito tale codice, i processori non sono tutti uguali.
Ad esempio il Pentium 3 della Intel ci metteva un ciclo di clock per una moltiplicazione, contro i 18 cicli di clock del Pentium 4
Se i dati si trovano già nella cache, o nella memoria centrale (RAM).
Insomma il logaritmo non c'entra nulla

[GuidoB]

Con i numeri interi a 32 o 64 bit non ha molto senso fare queste considerazioni di efficienza sull'operazione di elevamento a potenza (tra l'altro, in C/C++ non esiste l'operatore di elevamento a potenza tra interi).

Se dovessi farlo in C, mi scriverei una funzioncina che ottiene la potenza con ripetute moltiplicazioni, che quindi avrà una complessità O(k) (proporzionale a k).
Ma k non potrà essere molto elevato a causa dell'overflow. Su una macchina a 64 bit il massimo che si può fare è elevare 2 alla 63, 3 alla 40, 4 alla 31 ecc, quindi k vale al massimo 63. Il tempo di esecuzione è limitato superiormente da questo limite molto basso, quindi potremmo scrivere che al massimo è O(63), che equivale a O(1) (tempo costante, o comunque limitato superiormente a un valore costante).

Se avessi bisogno del massimo della velocità, mi farei una bella tabella di look-up con le potenze precalcolate per i primi interi (che sono quelli che richiedono più cicli), quindi ancora O(1).

Per i numeri in virgola mobile, nella libreria math esiste la funzione pow(base, esponente). Non ne conosco l'implementazione, ma di solito queste funzioni sono implementate con serie numeriche o iterazioni che convergono abbastanza rapidamente, e ci si ferma a un numero piccolo di termini della serie o iterazioni, quando l'errore è inferiore al bit meno significativo della mantissa. Quindi, anche qui, direi O(1).

Una complessità O(log k) mi sa di ricerca in un array ordinato o in un albero, ma davvero non vedo come possa avere a che fare con il calcolo di un elevamento a potenza.

[rugweri]

quella materia astratta dove si usano solo pseudocodici

Da questa sola frase posso certificare che tu della materia non hai capito una mazza.

Detto questo, ci sono moltissimi algoritmi men che lineari per il calcolo delle potenze... giusto per fare un esempio, Warren propone questo algoritmo di complessità (dove è ovviamente il numero di bit dell'esponente ):

Codice: Seleziona tutto

int iexp(int x, unsigned n)
{
    int p, y;
    y = 1;
    p = x;
    while(1)
    {
        if (n & 1) y = p*y;
        n = n >> 1;
        if (n == 0) return y;
        p = p*p;
    }
}


Questo algoritmo funziona per qualsiasi base e qualsiasi esponente , anche se non è detto che sia sempre ottimo.


GuidoB: Knuth, in effetti, propone un metodo di complessità logaritmica che sfrutta - se ben ricordo - un algoritmo di ricerca

[GuidoB]

Beh ma allora direi che l'interessante algoritmo di Warren indicato da rugweri abbia, grosso modo, proprio la complessità citata da Peternek, di O(log k).

Su macchine con interi a 32 o 64 bit comunque si fa presto ad andare in overflow. I guadagni sono eclatanti solo quando si trattano numeri con molti più bit.

EDIT: grazie rugweri per le ulteriori informazioni!

[Peternek]

Grazie a tutti per le risposte . In effetti come dice rugweri io di questa materia non capisco niente e tra l'altro in questo caso stavo svolgendo per esercizio il compito di una materia parallela simile quindi non so se magari loro hanno fatto qualcosa in più o usano delle convenzioni tipo "negli algoritmi per le potenze consideriamo il tempo necessario " come standard così magari non ci sarà quello che la considera O(1) per abitudine da certe librerie math di certi linguaggi oppure quello che se la calcola con un ciclo for in O(k). Ma è solo una mia ipotesi e fantasia quindi vi chiedo di non criticarmi: per questo vi ho scritto qua, nel dubbio che non fossero fesserie e che magari non ci fossero algoritmi con prestazioni molto migliori rispetto a che si usano solitamente.
Fatto sta che non dovrebbero aver studiato i compilatori o i riferimenti a come lo farebbe un compilatore concreto ad esempio quello di java (credo), ma anche se l'avessero fatto: mi avete già detto abbastanza vi ringrazio credo che considerino come prestazioni proprio l'algoritmo del tempo logaritmico