superpotenze di 2

[bortolozz]

oggi, facendo qualche esercizio per allenarmi per le olimpiadi di informatica mi sono imbattuto in questo problema:

Descrizione del problema

Conveniamo di chiamare ennesima superpotenza di 2 il valore di 22n. Ad esempio la terza superpotenza di 2 è 223 = 28 = 256. Si chiede di calcolare la ennesima superpotenza di 2 modulo m.

Dati di input

Il file di input contiene due interi: n (0 <= n <= 10^5) ed m (2 <= m <= 10^4).

Dati di output

Il risultato richiesto dal problema.

per esempio se in input ho
3 1000 l'output sarà 256 perché 2^(2^3)=2^8=256 256%1000=256


qualcuno saprebbe darmi un algoritmo valido?

[demos88]

sinceramente non capisco cosa ti serve... codice? in che linguaggio? quali parti del codice (lettura da file, calcolo del risultato...)?

[__ZERO_UNO__]

Neanche io ho capito bene qual'è il problema perchè mi sembra piuttosto semplice la risposta. Comunque, se vuoi un algoritmo in pseudo-codice senza l'uso esplicito della funzione potenza una soluzione potrebbe essere lo shift a sinistra della rappresentazione binaria di due



result = 2;
e = 1;
while n > 0 do
shift-to-left e;
--n; // in pratica è più efficiente di n-- ;)
end

--e; // uno shift come già fatto.
while e > 0 do
shift-to-left result;
--e;
end

result %= m;


Non è granchè come algoritmo lo so.

[bortolozz]

Neanche io ho capito bene qual'è il problema perchè mi sembra piuttosto semplice la risposta. Comunque, se vuoi un algoritmo in pseudo-codice senza l'uso esplicito della funzione potenza una soluzione potrebbe essere lo shift a sinistra della rappresentazione binaria di due



result = 2;
e = 1;
while n > 0 do
shift-to-left e;
--n; // in pratica è più efficiente di n-- ;)
end

--e; // uno shift come già fatto.
while e > 0 do
shift-to-left result;
--e;
end

result %= m;


Non è granchè come algoritmo lo so.

il fatto è che una soluzione di questo tipo funziona solo per n molto piccoli infatti gia mettendo n=20 si ha che la potenza è 2^(2^20) cioe 2^1048576
è le specifiche del problema dicono che 1<n<100000 e questo rende impossibile l'utilizzo di un algoritmo che calcoli la soluzione eseguendo la potenza

[ndakota]

Ho provato a pensarci un po' su carta(in realtà su notepad :D ) ma non so quanto ti possa aiutare.. Spero di non aver scritto castronerie e comunque il problema rimane estrarne un algoritmo..

2^10 (mod 1000) = 1024 (mod 1000) = 24

modo lento

2^10 (mod 1000) 2*2*2*2*2*2*2*2*2*2 (mod 1000) = 1024 (mod 1000) = 24

modo più veloce

10 = 5 * 2
(2*2*2*2*2)^2
2^5 (mod 1000) = 32
32^2 (mod 1000) = 1024 (mod 1000) = 24

però serve la fattorizzazione che è un problema computazionalmente intrattabile..

modo meno efficiente

2^2 (mod 1000) = 4 (mod 1000) = 4
4^2 (mod 1000) = 16(mod 1000) = 16
16^2 (mod 1000) = 256 (mod 1000) = 256
256*4 (mod 1000) = 1024 (mod 1000) = 24

[demos88]

Mh... credo di aver capito.
Essendo i giochi matematici/informatici subdolamente legati alla teoria matematica, penso di aver "mangiato la foglia" supponendo che la teoria che sta dietro al problema è quella dell' Aritmetica Modulare (http://it.wikipedia.org/wiki/Aritmetica_modulare).
In altre parole, puoi facilmente verificare che una funzione del tipo 2^n mod m con n,m naturali è ciclica nell'insieme dei numeri naturali.
Esempio con m = 20:
2^0 mod 20 = 0
2^1 mod 20 = 2
2^2 mod 20 = 4
2^3 mod 20 = 8
2^4 mod 20 = 16
2^5 mod 20 = 12
2^6 mod 20 = 4
2^7 mod 20 = 8
2^8 mod 20 = 16
2^9 mod 20 = 12
2^10 mod 20 = 4
2^11 mod 20 = 8
2^12 mod 20 = 16
2^13 mod 20 = 12
ecc...

ho evidenziato i cicli, come vedi, a partire da 2^n con n = 2 in poi, i resti della divisione per 20 si ripetono ciclicamente, in altre parole il resto della divisione per l'intero m può essere determinato analizzando solo l'esponente. Questo succede per ogni numero m divisore, ovviamente la lunghezza, i valori e l'indice di partenza del primo ciclo dipendono dall'm scelto.

Penso tu possa usare questa caratteristica a tuo vantaggio, ma così su due piedi non saprei darti un algoritmo. E sicuramente c'è un ulteriore passaggio da fare in quanto tu lavori con 2^(2^n) e l'esponente può raggiungere valori molto alti

[ndakota]

Di sicuro deve applicare il modulo dopo qualsiasi moltiplicazione, qualsiasi sia il metodo. Così rimane sempre su valori bassi. Se m è il modulo, credo possa raggiungere massimo m^2 in questo modo.

[rеpne scasb]

■

[banryu79]

Se interessa spiego.
Iscritto :D

[onbi]

la soluzione di repne si basa sul fatto che

2^(2^N) = (2^(2^(N-1)))^2
l'ennesima superpotenza è uguale al quadrato della ennemenounesima superpotenzapotenza.

bertolozz dove hai trovato questo problema? Sono molto curioso di provare a risolverne altri.

[ndakota]

Non so dove lo abbia preso ma se vuoi divertirti con cose del genere eccoti servito :D

http://projecteuler.net/problems

Edit: quello è solo per vedere i problemi prima di registrarti. Se ti registri, ti spiega il problema, e hai un campo di testo per inserire il risultato(che puoi trovare in qualsiasi modo). Una volta che risolvi un problema hai accesso ad una discussione con tutte le soluzioni date dagli utenti a quel problema(moltissime delle quali in Assembly :asd:).

[bortolozz]

grazie a tutti delle risposte
comunque questo esercizio l'ho trovato qui http://81.208.32.83:8080/ioi/index2.php?option=com_wrapper&view=wrapper&Itemid=331&lang=it dopo aver fatto la registrazione si può vedere il testo di tutti i problemi delle edizioni passate delle olimpiadi di informatica ed è possibile inviare la propria soluzione ad un correttore automatico che eseguira alcuni test di prova

[rеpne scasb]

■