BASE CINQUE FORUM

Qui sotto vedete l'algoritmo AKS (Agrawal-Kayal-Saxena) che permette di stabilire se un numero è primo in un tempo polinomiale.
E' tratto dall'articolo PRIMES in P del 2002 (credo) (https://www.cse.iitk.ac.in/users/manind ... ity_v6.pdf) Il primo punto del test consiste nel verificare se il numero dato è una potenza qualsiasi di un altro numero qualsiasi (naturale).
Ecco le mie domande:
a) Come si potrebbe fare per verificare se un numero è una potenza?
b) Sarebbe bello avere anche un programmino per computer che faccia il test.
c) Poi ci vuole anche la verifica che il programma faccia il test in un tempo polinomiale.
Cosa significa? Significa che il tempo impiegato sia proporzionale alla lunghezza della scrittura del numero (e non alla grandezza del numero).
Per esempio: 43046721 è circa 43 volte più grande di 1024 ma la sua scrittura (in base 10) è soltanto 2 volte più lunga, mentre in base 2 il rapporto è 2,5.

Uno spunto in Decimal Basic, con tutte le limitazioni del linguaggio, magari da tradurre in altro più conveniente.


Test per verificare se n=a^b interi, entro un limite per n fino a 15 cifre.
Non eseguibile in doppia precisione.
Esempi di numeri trattabili:
999706081460641, 953133216331392, 995009990004999, 995009990004999, 952809757913927, 952809757913927, 952809757913927

INPUT PROMPT "inserisci il valore di n ->":n
PRINT
LET b=1
LET t1=TIME
DO
LET b=b+1
LET a=n^(1/b)
LET k=INT(a)
IF a=k THEN
PRINT n;"=";a;"^";b
EXIT DO
ELSEIF k=1 THEN
PRINT n;"non è una potenza di a^b interi"
EXIT DO
END IF
LOOP WHILE k>1
LET t2=TIME
PRINT
PRINT "tempo impiegato = "; t2-t1
END

Bravo Pasquale!
L'algoritmo è talmente veloce che il risultato è quasi sempre praticamente 0 (centesimi di sec.) - nel range dei numeri trattabili.
Credevo che timer del DECIMAL misurasse i millesimi.
L'algoritmo comunque fa il test in un tempo polinomiale perché esegue al massimo $log_2 n$ cicli do-loop.
Infatti il numero massimo di cicli si ha con i numeri che sono potenze dispari di 2.
Mi è piaciuto!