Cos’è un algoritmo efficiente per trovare tutti i fattori di un intero?

Stavo scrivendo un programma molto semplice per esaminare se un numero potesse dividere un altro numero in modo uniforms:

// use the divider squared to reduce iterations for(divider = 2; (divider * divider) <= number; divider++) if(number % divider == 0) print("%d can divided by %d\n", number, divider); 

Ora ero curioso di poter eseguire l’operazione trovando la radice quadrata del numero e confrontandola con il divisore. Tuttavia, sembra che sqrt () non sia realmente in grado di aumentare l’efficienza. Come è stato gestito sqrt () in C e come posso aumentare l’efficienza di sqrt ()? Inoltre, c’è un altro modo per affrontare la risposta con un’efficienza ancora maggiore?

Anche il

 number % divider == 0 

è usato per verificare se il divisore può equamente dividere il numero, c’è anche un modo più efficiente di fare il test oltre all’utilizzo di%?

    Non ho intenzione di definire quale sia il miglior algoritmo per trovare tutti i fattori di un intero. Invece vorrei commentare il tuo metodo attuale.

    Ci sono i casi di test condizionali da considerare

    1. (divider * divider) <= number
    2. divider <= number/divider
    3. divider <= sqrt(number)

    Vedi i test Condizionali nella primalità per divisione di prova per ulteriori detials.

    Il caso da utilizzare dipende dai tuoi obiettivi e dall'hardware.

    Il vantaggio del caso 1 è che non richiede una divisione. Tuttavia, può overflow quando il divider*divider è più grande del numero intero più grande. Il secondo caso non ha il problema di overflow ma richiede una divisione. Per caso3 lo sqrt deve essere calcolato solo una volta ma richiede che la funzione sqrt ottenga i quadrati perfetti corretti.

    Ma c'è qualcos'altro da considerare che molti set di istruzioni, incluso il set di istruzioni x86, restituiscono il resto anche quando si fa una divisione. Dato che stai già facendo il number % divider questo significa che puoi ottenerlo gratuitamente quando fai il number / divider .

    Pertanto, il caso 1 è utile solo nel sistema in cui la divisione e il resto non sono calcolati in un'unica istruzione e non sei preoccupato per l'overflow.

    Tra il caso 2 e il case3 penso che il problema principale sia di nuovo il set di istruzioni. Scegli caso 2 se sqrt è troppo lento rispetto a case2 o se la tua funzione sqrt non calcola correttamente i quadrati perfetti. Scegli il caso 3 se il set di istruzioni non calcola il divisore e il resto in un'unica istruzione.

    Per il set di istruzioni x86, caso 1, il caso 2 e il caso 3 dovrebbero fornire prestazioni sostanzialmente uguali. Quindi non ci dovrebbero essere motivi per usare il caso 1 (vedi comunque un punto sottile sotto). La libreria standard C garantisce che il sqrt dei quadrati perfetti sia fatto correttamente. Quindi non vi è alcun svantaggio nemmeno nel caso 3.

    Ma c'è un punto sottile sul caso 2. Ho trovato che alcuni compilatori non riconoscono che la divisione e il resto sono calcolati insieme. Ad esempio nel seguente codice

     for(divider = 2; divider <= number/divider; divider++) if(number % divider == 0) 

    GCC genera due istruzioni di divisione anche se ne è necessaria solo una. Un modo per risolvere questo problema è mantenere la divisione e il promemoria vicino in questo modo

     divider = 2, q = number/divider, r = number%divider for(; divider <= q; divider++, q = number/divider, r = number%divider) if(r == 0) 

    In questo caso GCC produce solo un'istruzione division e case1, case 2 e case 3 hanno le stesse prestazioni. Ma questo codice è un po 'meno leggibile di

     int cut = sqrt(number); for(divider = 2; divider <= cut; divider++) if(number % divider == 0) 

    quindi penso che il caso 3 sia la scelta migliore almeno con il set di istruzioni x86.

    Tuttavia, sembra che sqrt () non sia realmente in grado di aumentare l’efficienza

    Ciò è prevedibile, poiché la moltiplicazione salvata per iterazione è in gran parte dominata dall’operazione di divisione molto più lenta all’interno del ciclo.

    Inoltre, il number % divider = 0 viene utilizzato per verificare se il divisore può equamente dividere il numero, esiste anche un modo più efficiente per eseguire il test oltre all’utilizzo di%?

    Non che io sappia. Controllare se a % b == 0 è almeno tanto difficile quanto controllare a % b = c per qualche c, perché possiamo usare il primo per calcolare quest’ultimo (con un’aggiunta extra). E almeno sulle architetture Intel, il calcolo di quest’ultimo è altrettanto costoso come una divisione, che è tra le operazioni più lente nei processori tipici e moderni.

    Se vuoi prestazioni significativamente migliori, hai bisogno di un algoritmo di fattorizzazione migliore, di cui ce ne sono molte . Uno in particolare semplice con runtime O (n 1/4 ) è l’algoritmo ρ di Pollard . Puoi trovare un’implementazione C ++ diretta nella mia libreria di algoritmi . L’adattamento a C è lasciato come esercizio al lettore:

     int rho(int n) { // will find a factor < n, but not necessarily prime if (~n & 1) return 2; int c = rand() % n, x = rand() % n, y = x, d = 1; while (d == 1) { x = (1ll*x*x % n + c) % n; y = (1ll*y*y % n + c) % n; y = (1ll*y*y % n + c) % n; d = __gcd(abs(x - y), n); } return d == n ? rho(n) : d; } void factor(int n, map& facts) { if (n == 1) return; if (rabin(n)) { // simple randomized prime test (eg Miller–Rabin) // we found a prime factor facts[n]++; return; } int f = rho(n); factor(n/f, facts); factor(f, facts); } 

    Costruire i fattori di n dai suoi fattori primi è quindi un compito facile. Usa tutti i possibili esponenti per i fattori primi trovati e combinali in ogni modo ansible.

    In C, puoi prendere radici quadrate di numeri in virgola mobile con la famiglia di funzioni sqrt() nell’intestazione .

    Prendere le radici quadrate di solito è più lento della divisione perché l’algoritmo per prendere le radici quadrate è più complicato dell’algoritmo di divisione. Questa non è una proprietà del linguaggio C ma dell’hardware che esegue il tuo programma. Sui processori moderni, prendere radici quadrate può essere altrettanto veloce quanto la divisione. Ciò vale, ad esempio, nella microarchitettura Haswell.

    Tuttavia, se i miglioramenti algoritmici sono buoni, la velocità leggermente più lenta di una chiamata sqrt() solito non ha importanza.

    Per confrontare solo fino alla radice quadrata del number , utilizzare un codice come questo:

     #include  /* ... */ int root = (int)sqrt((double)number); for(divider = 2; divider <= root; divider++) if(number % divider = 0) print("%d can divided by %d\n", number, divider); 

    Questo è solo il mio pensiero casuale, quindi per favore commentalo e commentalo se è sbagliato.

    L’idea è precomputare tutti i numeri primi al di sotto di un certo intervallo e usarli come tabella.

    Se si esegue il cicloing della tabella, controllare se il numero primo è un fattore, se lo è, quindi aumentare il contatore per quel numero primo, se non lo è, quindi aumentare l’indice. Termina quando l’indice raggiunge la fine o il numero primo da controllare supera l’input.

    Alla fine, il risultato è una tabella di tutti i fattori primi dell’input e dei loro conteggi. Quindi generare tutti i fattori naturali dovrebbe essere trival, non è vero?

    Nel peggiore dei casi, il ciclo deve andare fino alla fine, quindi occorrono 6542 iterazioni.

    Considerando l’input è [0, 4294967296] questo è simile a O(n^3/8) .

    Ecco il codice MATLAB che implementa questo metodo:

    se p è generato da p=primes(65536); questo metodo funzionerebbe per tutti gli input tra [0, 4294967296] (ma non testato).

     function [ output_non_zero ] = fact2(input, p) output_table=zeros(size(p)); i=1; while(i 1.5) % the last and largest prime factor could be larger than 65536 % hence would skip from the table, add it to the end of output % if exists output_non_zero = [output_non_zero,[input;1]]; end end 

    test

     p=primes(65536); t = floor(rand()*4294967296); b = fact2(t, p); % check if all prime factors adds up and they are all primes assert((prod(b(1,:).^b(2,:))==t)&&all(isprime(b(1,:))), 'test failed');