F# problema parallelizzante quando si calcola numeri perfetti?
-
27-10-2019 - |
Domanda
Sto cercando di ottimizzare un piccolo programma che calcola i numeri perfetti da un determinato esponente.
Il programma funziona (quasi) perfettamente, ma quando apro il Task Manager, funziona ancora su un singolo thread. Ciò significa che devo fare qualcosa di sbagliato, ma la mia conoscenza di F# è ancora in una fase "iniziale".
Cercherò di mettere questa domanda il più chiaro possibile, ma se non riesco a farlo, per favore fatemelo sapere.
Un numero perfetto è un numero in cui la somma di tutti i suoi divisori (ad eccezione del numero stesso) è uguale al numero stesso (ad esempio 6 è perfetta, poiché la somma dei suoi divisori 1, 2 e 3 è 6).
Uso numeri primi per accelerare il calcolo, cioè non mi interessa elenchi (enormi) in cui tutti i divisori sono archiviati. Per fare ciò, uso la formula che Euclid si è rivelata corretta: (2* (potenza di num - 1))* (2* (potenza di Num - 1)) dove quest'ultimo è un primo mersenne. Ho usato un algoritmo molto veloce da StackOverflow (di @juliet) per determinare se un determinato numero è un primo.
Dato che ho letto diversi articoli (non ho ancora acquistato un buon libro, quindi una vergogna per me) su Internet, ho scoperto che le sequenze funzionano meglio delle liste. Ecco perché ho iniziato a creare una funzione che genera una sequenza di numeri perfetti:
let perfectNumbersTwo (n : int) =
seq { for i in 1..n do
if (PowShift i) - 1I |> isPrime
then yield PowShift (i-1) * ((PowShift i)-1I)
}
Il powshift di Helperfunction è implementato come segue:
let inline PowShift (exp:int32) = 1I <<< exp ;;
Uso un operatore di bit shift, poiché la base di tutti i calcoli di potenza è da 2, quindi questo potrebbe essere un modo semplice. Ovviamente sono ancora grato per i contributi sulla domanda che ho posto su questo: F# Problemi di potere che accetta entrambi gli argomenti per essere bigint>F# Problemi di potere che accettano entrambi gli argomenti come bigint
La funzione ha creato Juliet (preso in prestito qui) è il seguente:
let isPrime ( n : bigint) =
let maxFactor = bigint(sqrt(float n))
let rec loop testPrime tog =
if testPrime > maxFactor then true
elif n % testPrime = 0I then false
else loop (testPrime + tog) (6I - tog)
if n = 2I || n = 3I || n = 5I then true
elif n <= 1I || n % 2I = 0I || n % 3I = 0I || n % 5I = 0I then false
else loop 7I 4I;;
Usando questo codice, senza parallelo, ci vogliono circa 9 minuti sul mio laptop per trovare il nono numero perfetto (che consiste in 37 cifre e può essere trovato con il valore 31 per l'esponente). Dato che il mio laptop ha una CPU con due core e solo uno è in esecuzione al 50 percento (carico completo per un nucleo), anche se potrei accelerare i calcoli calcolando i risultati paralleli.
Quindi ho cambiato la mia funzione perfetta come segue:
//Now the function again, but async for parallel computing
let perfectNumbersAsync ( n : int) =
async {
try
for x in 1.. n do
if PowShift x - 1I |> isPrime then
let result = PowShift (x-1) * ((PowShift x)-1I)
printfn "Found %A as a perfect number" result
with
| ex -> printfn "Error%s" (ex.Message);
}
Per chiamare questa funzione, utilizzo una piccola funzione di supporto per eseguirla:
let runPerfects n =
[n]
|> Seq.map perfectNumbersAsync
|> Async.Parallel
|> Async.RunSynchronously
|> ignore
Laddove il risultato del calcolo dell'asincronizzazione viene ignorato, poiché lo sto mostrando all'interno della funzione perfettanumbersasync.
Il codice sopra compila e funziona, tuttavia utilizza ancora solo un core (sebbene funziona più velocemente quando si calcola il 9 ° numero perfetto). Temo che debba fare qualcosa con l'helper funzioni Powshift e isprime, ma non sono sicuro. Devo mettere il codice di queste funzioni di supporto all'interno del blocco asincrico di PerfectNumbersync? Non migliora la leggibilità ...
Più gioco con F#, più imparo ad apprezzare questa lingua, ma come in questo caso, ho bisogno di alcuni esperti a volte :).
Grazie in anticipo per aver letto questo, spero solo di avermi chiarito un po '...
Roberto.
Soluzione
Il commento di @jeffrey sax è decisamente interessante, quindi ho impiegato del tempo per fare un piccolo esperimento. Il test Lucas-Lehmer è scritto come segue:
let lucasLehmer p =
let m = (PowShift p) - 1I
let rec loop i acc =
if i = p-2 then acc
else loop (i+1) ((acc*acc - 2I)%m)
(loop 0 4I) = 0I
Con il test Lucas-Lehmer, posso ottenere i primi numeri perfetti molto velocemente:
let mersenne (i: int) =
if i = 2 || (isPrime (bigint i) && lucasLehmer i) then
let p = PowShift i
Some ((p/2I) * (p-1I))
else None
let runPerfects n =
seq [1..n]
|> Seq.choose mersenne
|> Seq.toArray
let m1 = runPerfects 2048;; // Real: 00:00:07.839, CPU: 00:00:07.878, GC gen0: 112, gen1: 2, gen2: 1
Il test Lucas-Lehmer aiuta a ridurre il tempo di controllo dei numeri primi. Invece di testare la divisibilità di 2^p-1 che prende O(sqrt(2^p-1))
, usiamo il test di primalità che è al massimo O(p^3)
. Insieme a n = 2048
, Sono in grado di trovare i primi 15 numeri di Mersenne in 7,83 secondi. Il 15 numero di Mersenne è quello con i = 1279
ed è composto da 770 cifre.
Ho provato a parallelizzare runPerfects
usando il modulo pSeq in F# powerpack. PSEQ non preserva l'ordine della sequenza originale, quindi per essere onesti ho ordinato la sequenza di output. Poiché il test di primalità è abbastanza equilibrato tra gli indici, il risultato è piuttosto incoraggiante:
#r "FSharp.Powerpack.Parallel.Seq.dll"
open Microsoft.FSharp.Collections
let runPerfectsPar n =
seq [1..n]
|> PSeq.choose mersenne
|> PSeq.sort (* align with sequential version *)
|> PSeq.toArray
let m2 = runPerfectsPar 2048;; // Real: 00:00:02.288, CPU: 00:00:07.987, GC gen0: 115, gen1: 1, gen2: 0
Con lo stesso input, la versione parallela ha richiesto 2,28 secondi, equivalente a 3,4x SpeedUp sulla mia macchina quad-core. Credo che il risultato potrebbe essere migliorato ulteriormente se usi Parallel.For
costruisci e partizione l'intervallo di input in modo sensato.
Altri suggerimenti
Un rapido commento su velocità e parallelibilità,
Tuo isPrime
è o (sqrt (n)) e ogni n -successivo è circa 2 x grande come l'ultimo, quindi richiederà circa 1,5 x per calcolare, il che significa che il calcolo degli ultimi numeri richiederà molto più tempo
Ho fatto un po 'di hacking con i test per la primalità e alcune cose che ho trovato che sono utili sono:
Per Big N, (stai testando numeri con 20 cifre), la densità primaria è in realtà piuttosto bassa, quindi farai molte divisioni in base a numeri compositi. Un approccio migliore è quello di precalcolare una tabella di numeri primi (usando un setaccio) fino a un limite massimo (probabilmente determinato dalla quantità di memoria). Si noti che è più probabile che tu trovi fattori con piccoli numeri. Una volta esaurito la memoria per la tua tabella, puoi testare il resto dei numeri con la tua funzione esistente, con un punto di partenza più ampio.
Un altro approccio è utilizzare più thread nel controllo. Ad esempio, attualmente controlli
x,x+4,x+6...
come fattori. Essendo leggermente più intelligente, puoi fare il numero congruente a 1 mod 3 in 1 thread e i numeri congruenti a 2 mod 3 in un altro thread.
Il n. 2 è più semplice, ma il n. 1 è più efficace e fornisce il potenziale per eseguire il flusso di controllo con outofmemoryexceptions che possono sempre essere interessanti
MODIFICARE:Così ho implementato entrambe queste idee, trova 2305843008139952128 quasi istantaneamente, trovando 2658455991569831744654692615953842176 impiegando 7 minuti sul mio computer (Quad Core AMD 3200). Il più delle volte viene dedicato al controllo di 2^61 è primo, quindi un algoritmo migliore sarebbe probabilmente migliore per controllare i numeri primi: codice qui
let swatch = new System.Diagnostics.Stopwatch()
swatch.Start()
let inline PowShift (exp:int32) = 1I <<< exp ;;
let limit = 10000000 //go to a limit, makes table gen slow, but should pay off
printfn "making table"
//returns an array of all the primes up to limit
let table =
let table = Array.create limit true //use bools in the table to save on memory
let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
table.[1] <- false //special case
[2..tlimit]
|> List.iter (fun t ->
if table.[t] then //simple optimisation
let mutable v = t*2
while v < limit do
table.[v] <- false
v <- v + t)
let out = Array.create (50847534) 0I //wolfram alpha provides pi(1 billion) - want to minimize memory
let mutable idx = 0
for x in [1..(limit-1)] do
if table.[x] then
out.[idx] <- bigint x
idx <- idx + 1
out |> Array.filter (fun t -> t <> 0I) //wolfram no is for 1 billion as limit, we use a smaller number
printfn "table made"
let rec isploop testprime incr max n=
if testprime > max then true
else if n % testprime = 0I then false
else isploop (testprime + incr) incr max n
let isPrime ( n : bigint) =
//first test the table
let maxFactor = bigint(sqrt(float n))
match table |> Array.tryFind (fun t -> n % t = 0I && t <= maxFactor) with
|Some(t) ->
false
|None -> //now slow test
//I have 4 cores so
let bases = [|limit;limit+1;limit+3;limit+4|] //uses the fact that 10^x congruent to 1 mod 3
//for 2 cores, drop last 2 terms above and change 6I to 3I
match bases |> Array.map (fun t -> async {return isploop (bigint t) 6I maxFactor n}) |> Async.Parallel |> Async.RunSynchronously |> Array.tryFind (fun t -> t = false) with
|Some(t) -> false
|None -> true
let pcount = ref 0
let perfectNumbersTwo (n : int) =
seq { for i in 2..n do
if (isPrime (bigint i)) then
if (PowShift i) - 1I |> isPrime then
pcount := !pcount + 1
if !pcount = 9 then
swatch.Stop()
printfn "total time %f seconds, %i:%i m:s" (swatch.Elapsed.TotalSeconds) (swatch.Elapsed.Minutes) (swatch.Elapsed.Seconds)
yield PowShift (i-1) * ((PowShift i)-1I)
}
perfectNumbersTwo 62 |> Seq.iter (printfn "PERFECT: %A") //62 gives 9th number
printfn "done"
System.Console.Read() |> ignore