Algoritmo fattorizzazione

Algoritmi, discussioni sulle possibili implementazioni, matematica, fisica e tutti gli argomenti correlati alla programmazione
Rispondi
Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Algoritmo fattorizzazione

Messaggio da doom13 »

Ragazzi mi servirebbe una mano sull'algoritmo di fattorizzazione. Attualmente ho usato per il metodo a forza bruta ma non è abbastanza efficiente, come potrei migliorarlo?
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
guidox
GMI Honor
Messaggi: 5765
Iscritto il: 26/07/2009, 17:23
Specialità: programmazione
Uso: GM:Studio 1.4 Android
Località: Marche
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da guidox »

Ho fatto una rapida ricerca su google ed ho trovato quello di Fermat: http://it.wikipedia.org/wiki/Metodo_di_ ... _di_Fermat
Ho provato a metterlo in codice e sembra funzionare:

Crea uno script "Fermat(numero)":

Codice: Seleziona tutto

var b2,a,b;
b2=2;
for(a=ceil(sqrt(argument0)); sqrt(b2) != floor(sqrt(b2)); a+=1) {
b2=sqr(a)-argument0;
}
a-=1;
b=sqrt(b2);

if (a-b == 1) {
ds_list_add(fattori,a+b);
}
else
if (a+b == 1) {
ds_list_add(fattori,a-b);
}
else
{
Fermat(a-b);
Fermat(a+b);
}
E poi utilizza questo codice, che metterà all'interno di una comoda ds_list i tuoi fattori primi. :D

Codice: Seleziona tutto

n=14153670;
fattori = ds_list_create();

while (n mod 2 == 0) {
n /= 2;
ds_list_add(fattori,2);
}

Fermat(n);

for(i=0; i<ds_list_size(fattori); i+=1) {
show_message(ds_list_find_value(fattori,i));
}
Immagine

Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

Grandissimo, in realtà mi serviva in java ma hai fatto anche troppo ci penserò io a convertirlo.
Grazie ancora.

Edit:
L'algoritmo deve essere abbastanza efficiente da calcolare la fattorizzazione di numeri a 19 cifre in 60 secondi massimo, questo ce la fa?
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
guidox
GMI Honor
Messaggi: 5765
Iscritto il: 26/07/2009, 17:23
Specialità: programmazione
Uso: GM:Studio 1.4 Android
Località: Marche
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da guidox »

19 cifre O.O
Guarda con GM è impossibile farglielo fare con così tante cifre. Comunque non credo che un algoritmo di questo tipo sia la soluzione per questo problema. Ma a cosa ti serve? D:
Immagine

Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

È un esercizio. Comunque potrebbe essere che il tuo script convertito in java vada bene.
È pure ricorsiva D: la bestia hai scomodato xD
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Nix
GMI Advanced
Messaggi: 2437
Iscritto il: 26/12/2008, 18:14
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da Nix »

Se usi i numeri interi a 64 bit dovrebbe andar bene per la dimensione, ma per il tempo 19 cifre mi sembrano comunque troppe. Se si tratta di un problema come quelli di Project Euler, probabilmente stai sbagliando approccio.

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

Nix ha scritto:Se usi i numeri interi a 64 bit dovrebbe andar bene per la dimensione, ma per il tempo 19 cifre mi sembrano comunque troppe. Se si tratta di un problema come quelli di Project Euler, probabilmente stai sbagliando approccio.
E' un "semplice" esercizio, stamattina mi stavo confrontando con alcuni amici e stavamo provando ad implementare altri algoritmi, abbiamo però alcuni problemi anche se non di tempo.
Al limite vi pubblico lo pseudocodice o direttamente il codice in java magari da lì sapreste darmi una mano.
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

Ho convertito il codice di guidox in java ma è troppo lento :(
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Nix
GMI Advanced
Messaggi: 2437
Iscritto il: 26/12/2008, 18:14
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da Nix »

Hai detto di aver provato con la forza bruta, ma hai diviso per tutti i numeri primi da 2 alla radice quadrata del numero?

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

Nix ha scritto:Hai detto di aver provato con la forza bruta, ma hai diviso per tutti i numeri primi da 2 alla radice quadrata del numero?
Allora l'avevo letto in giro per internet ma sai che non l'avevo mica messo?
Attualmente l'algoritmo che ho è questo, in parte preso da internet, in parte modificato da me:

Codice: Seleziona tutto

boolean found = true;
while(found) {
    found = false;
    for(long i=2; i<Math.sqrt(val); i++) { //ho aggiunto quel Math.sqrt che mi ero scordato
        if(val%i == 0) {
            System.out.print(times + i);
            val /= i;
            times = " * ";
            found = true;
            break;
        }
    }
if(!found) {
    System.out.println(times + val);
}
Pare funzionare e pure parecchio velocemente nonostante il numerone di prova che ho scelto (8234567890123456789) O.o
Intanto vi ringrazio, vi aggiorno per farvi sapere se sono riuscito a finire l'esercizio.
L'esercizio mi chiede di far ritornare una stringa che per 32 ad esempio è "2(3) 4". Mi rimane da aggiustarlo per far ritornare questo tipo di stringa e ho finito. Di nuovo grazie a tutti e due :sisisi:
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
guidox
GMI Honor
Messaggi: 5765
Iscritto il: 26/07/2009, 17:23
Specialità: programmazione
Uso: GM:Studio 1.4 Android
Località: Marche
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da guidox »

Nix ha scritto:Project Euler
Figoooo
Ora mi ci diverto un po'!
Immagine

Immagine

Nix
GMI Advanced
Messaggi: 2437
Iscritto il: 26/12/2008, 18:14
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da Nix »

Non so se effettivamente volevi questo ma così non stai fattorizzando in numeri primi, e generalmente si intende questo quando si parla di fattorizzazione (ma non necessariamente), infatti l'algoritmo di guidox (che comunque è meno efficiente della divisione) trova i fattori primi. Se vuoi fare questo puoi usare lo stesso algoritmo che stai usando per ora, controllando però anche che il numero sia primo. Ti conviene generarli tutti fino a [latex]\sqrt{n}[/latex] prima delle divisioni, per esempio col crivello di Eratostene, ma con numeri così grandi ci vuole troppa memoria e potrebbe darti dei problemi.

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: Algoritmo fattorizzazione

Messaggio da doom13 »

Allora aspetta, nell'esempio ho sbagliato a scrivere, con 32 deve restituirmi "2(5)".
Con 26 deve restituirmi "2 13", con 156 deve restituirmi "2(2) 3 13".
Quello che fa questo algoritmo è stamparmi:
156 = 2 * 2 * 3 * 13
Che è simile ma non quello che mi serve ovviamente. Devo modificarlo per far uscire quel tipo di stringa, non credo ci sia bisogno di calcolare i numeri primi fino a sqrt(n). Magari sto sbagliando eh
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti