Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Le potenze nello studio degli algoritmi

Linguaggi e sistemi

Moderatori: Foto UtentePaolino, Foto UtenteMassimoB

0
voti

[1] Le potenze nello studio degli algoritmi

Messaggioda Foto UtentePeternek » 5 lug 2018, 10:57

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 n^k con un n fissato, dice che sarebbe necessario un tempo \log k per calcolarla.
In java o altri linguaggi io farei n^k senza chiedermi quanto ci impiega la macchina, sperando che il tempo sia bassissimo. In realtà non so quanto ci impiegano, \log k sarebbe diciamo il classico tempo necessario n queste situazioni, o quello che si usa per convenzione negli algoritmi?
Avatar utente
Foto UtentePeternek
45 1 4
New entry
New entry
 
Messaggi: 62
Iscritto il: 17 ott 2017, 22:38

0
voti

[2] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtenteEdmondDantes » 5 lug 2018, 11:31

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.
Il Conte di Montecristo
Penso di poter stare sveglio fino a quell'ora. James Clerk Maxwell
Avatar utente
Foto UtenteEdmondDantes
5.762 5 10 13
G.Master EY
G.Master EY
 
Messaggi: 1656
Iscritto il: 25 lug 2009, 22:18
Località: Marsiglia

0
voti

[3] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtentePeternek » 5 lug 2018, 12:39

Si chiedo scusa non sono riuscito a spiegarmi bene usando la n: 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 \log k ad essere eseguita dalla macchina?
Per n quindi non intendevo la complessità dell'algoritmo ma un qualsiasi parametro
Avatar utente
Foto UtentePeternek
45 1 4
New entry
New entry
 
Messaggi: 62
Iscritto il: 17 ott 2017, 22:38

1
voti

[4] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtenteExodus » 5 lug 2018, 14:36

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

[-X
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 :ok:
Se i dati si trovano già nella cache, o nella memoria centrale (RAM).
Insomma il logaritmo non c'entra nulla ;-)
Avatar utente
Foto UtenteExodus
145 1
New entry
New entry
 
Messaggi: 99
Iscritto il: 25 ago 2017, 17:30

2
voti

[5] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtenteGuidoB » 5 lug 2018, 15:09

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.
Big fan of ƎlectroYou!
Avatar utente
Foto UtenteGuidoB
13,7k 6 12 13
G.Master EY
G.Master EY
 
Messaggi: 2054
Iscritto il: 3 mar 2011, 16:48
Località: Madrid

3
voti

[6] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto Utentewruggeri » 5 lug 2018, 15:18

Peternek ha scritto: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à \lfloor \log_2(n) \rfloor + Bits(n) - 1 (dove Bits(n) è ovviamente il numero di bit dell'esponente n):

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 x \in \mathbb{N} e qualsiasi esponente n \in (\mathbb{N} - \{0, 1\}), anche se non è detto che sia sempre ottimo.


Foto UtenteGuidoB: Knuth, in effetti, propone un metodo di complessità logaritmica che sfrutta - se ben ricordo - un algoritmo di ricerca ;-)
Rispondo solo a chi si esprime correttamente in italiano.
Se non conosci un argomento, non parlarne.
Gli unici fatti sono quelli dimostrabili, il resto è opinione.
Non dirò una parola sulla politica e sul M5S, del quale aspetto solo l'estinzione.
Avatar utente
Foto Utentewruggeri
4.011 1 6 13
Expert EY
Expert EY
 
Messaggi: 728
Iscritto il: 25 nov 2016, 18:46

2
voti

[7] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtenteGuidoB » 5 lug 2018, 15:41

Beh ma allora direi che l'interessante algoritmo di Warren indicato da Foto Utentewruggeri abbia, grosso modo, proprio la complessità citata da Foto UtentePeternek, 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 Foto Utentewruggeri per le ulteriori informazioni! :ok:
Big fan of ƎlectroYou!
Avatar utente
Foto UtenteGuidoB
13,7k 6 12 13
G.Master EY
G.Master EY
 
Messaggi: 2054
Iscritto il: 3 mar 2011, 16:48
Località: Madrid

0
voti

[8] Re: Le potenze nello studio degli algoritmi

Messaggioda Foto UtentePeternek » 5 lug 2018, 17:36

Grazie a tutti per le risposte :ok: . In effetti come dice wruggeri io di questa materia non capisco niente :mrgreen: 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 \log k" 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 \log k 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
Avatar utente
Foto UtentePeternek
45 1 4
New entry
New entry
 
Messaggi: 62
Iscritto il: 17 ott 2017, 22:38


Torna a PC e informatica

Chi c’è in linea

Visitano il forum: Nessuno e 7 ospiti