[C] calcolo potenza con costo log(n) anzichè n

[autista]

salve ragazzi, non riesco a creare un algoritmo che calcoli una potenza del tipo x^y con un costo log(n) anziché n; quest' ultimo caso è banale e sono riuscito a farlo con il normale prodotto

[71104]

assumo che l'esponente sia un naturale (coi reali non so neanche come si fa...).

il concetto di base è: devi elevare 2 alla quarta? inutile fare 3 prodotti, ovvero 2 * 2 * 2 * 2, poiché ne bastano solo 2: 2 * 2 = 4, 4 * 4 = 16.

da questo spunto lascio continuare te ;)

[autista]

assumo che l'esponente sia un naturale (coi reali non so neanche come si fa...).

il concetto di base è: devi elevare 2 alla quarta? inutile fare 3 prodotti, ovvero 2 * 2 * 2 * 2, poiché ne bastano solo 2: 2 * 2 = 4, 4 * 4 = 16.

da questo spunto lascio continuare te ;)

ascolta non mi torna una cosa, a me sembrano sempre essere 3 prodotti perché il primo prodotto deriva dal 2*2=4

poi tu fai 4*4 ma quest'ultimo 4 deriverà pure da un altro prodotto(cioè da 2*2) o no? sbaglio io?

[Ziosilvio]

Altro aiutino: se usi gli operatori bit-a-bit, te la cavi in tempo O(log n) e spazio O(1).

[autista]

Altro aiutino: se usi gli operatori bit-a-bit, te la cavi in tempo O(log n) e spazio O(1).

bit-a-bit non l'ho mai sentito, ma c'entra qualcosa con gli algoritmi di ordinamento come bubble_sort, quick_sort e altri?

[Ziosilvio]

bit-a-bit non l'ho mai sentito
Cerca sul Kernighan&Ritchie.

[71104]

ascolta non mi torna una cosa, a me sembrano sempre essere 3 prodotti perché il primo prodotto deriva dal 2*2=4

poi tu fai 4*4 ma quest'ultimo 4 deriverà pure da un altro prodotto(cioè da 2*2) o no? sbaglio io? nei moderni computers di memoria ne hai quanta ne vuoi, ti pare che non hai spazio per ricordare un misero 4 ottenuto da una moltiplicazione precedente? :Prrr:

1) moltiplica 2 * 2
2) ottieni 4
3) moltiplica 4 * 4

ora tutto sta a generalizzare un algoritmo.

[71104]

altro suggerimento: dove c'è logaritmo c'è albero. prova a rappresentare l'elevamento a potenza come una serie di moltiplicazioni e ad ordinare tali moltiplicazioni in un albero binario. ovviamente non sempre l'albero sarà completo perché capiteranno anche gli esponenti che non sono potenza di due, ma i casi particolari verranno dopo. inizialmente prova ad assumere che l'esponente sia una potenza di due (1, 2, 4, 8, 16, 32...).

[andbin]

Altro aiutino aiutino: si vuole per esempio calcolare 5^13 che, per la cronaca, fa 1220703125.

Come si rappresenta 13 in binario? Con 1101

Quindi 5^13 lo puoi esprimere come: 5^8 * 5^4 * 5^1

Quindi ti basta calcolare:

5^1 = 5
5^2 = 25 <--- non lo usi
5^4 = 625
5^8 = 390625

Quindi moltiplichi 5 * 625 * 390625.

[71104]

aiutino de che, che gliel'hai detto ormai :D

edit - però non è lo stesso sistema :mbe:
hm, hm, hm, interessante quest'altro metodo http://forums.nsn3.net/style_emoticons/default/55.gif

[andbin]

aiutino de che, che gliel'hai detto ormai :DBeh, gli ho solo fatto un esempio ... mica scritto il codice per intero! ;)
Tocca a lui generalizzare la cosa e scrivere del codice per implementare l'algoritmo.

edit - però non è lo stesso sistema :mbe:
hm, hm, hm, interessante quest'altro metodo Tu quale altro metodo avevi in mente? .... giusto per sapere.

[autista2]

Altro aiutino aiutino: si vuole per esempio calcolare 5^13 che, per la cronaca, fa 1220703125.

Come si rappresenta 13 in binario? Con 1101

Quindi 5^13 lo puoi esprimere come: 5^8 * 5^4 * 5^1

Quindi ti basta calcolare:

5^1 = 5
5^2 = 25 <--- non lo usi
5^4 = 625
5^8 = 390625

Quindi moltiplichi 5 * 625 * 390625.

ma la complessità di questo algoritmo non è sempre THETA(N)

PS. sono sempre io ma bannato per sbaglio :D

[HighVoltage]

PS. sono sempre io ma bannato per sbaglio :D

da verificare ;)

[andbin]

ma la complessità di questo algoritmo non è sempre THETA(N)È log2(n), se non sbaglio.

[autista2]

il problema è che devo risolverlo con qualcosa inerente gli algoritmi di ordinamento

quindi non so come strutturarlo :mc: :mc:

[andbin]

il problema è che devo risolverlo con qualcosa inerente gli algoritmi di ordinamentoSarò io che sono ignorante su tante cose .... ma cosa centra un algoritmo di ordinamento con un elevamento a potenza?? :confused:

[autista2]

Sarò io che sono ignorante su tante cose .... ma cosa centra un algoritmo di ordinamento con un elevamento a potenza?? :confused:

perché a lezione il professore ci ha assegnato questo esercizio 2 secondi dopo aver spiegato gli algoritmi di ordinamento e la ricerca binaria