[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]

Originariamente inviato da 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

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]

Originariamente inviato da Ziosilvio

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]

Originariamente inviato da autista

bit-a-bit non l'ho mai sentito

Cerca sul Kernighan&Ritchie.

[71104]

Originariamente inviato da autista

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?

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

edit - però non è lo stesso sistema
hm, hm, hm, interessante quest'altro metodo

[andbin]

Originariamente inviato da 71104

aiutino de che, che gliel'hai detto ormai

Beh, 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.

Originariamente inviato da 71104

edit - però non è lo stesso sistema
hm, hm, hm, interessante quest'altro metodo

Tu quale altro metodo avevi in mente? .... giusto per sapere.

[autista2]

Originariamente inviato da 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.

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

PS. sono sempre io ma bannato per sbaglio

[HighVoltage]

Originariamente inviato da autista2

PS. sono sempre io ma bannato per sbaglio

da verificare

[andbin]

Originariamente inviato da autista2

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

[andbin]

Originariamente inviato da autista2

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

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

[autista2]

Originariamente inviato da andbin

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

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