F# ¿Problema de paralelización al calcular números perfectos?

https://stackoverflow.com/questions/8368107

27-10-2019
|

Pregunta

Estoy tratando de optimizar un pequeño programa que calcule los números perfectos de un exponente dado.

El programa se ejecuta (casi) perfectamente, pero cuando abro el administrador de tareas, todavía se ejecuta en un solo hilo. Eso significa que debo estar haciendo algo mal, pero mi conocimiento de F# todavía está en una fase de 'comienzo'.

Intentaré hacer esta pregunta tan clara como sea posible, pero si fallo en hacerlo, hágamelo saber.

Un número perfecto es un número en el que la suma de todos sus divisores (excepto el número en sí) es igual al número en sí (por ejemplo, 6 es perfecto, ya que la suma de sus divisores 1, 2 y 3 son 6).

Utilizo números primos para acelerar el cálculo, es decir, no estoy interesado en las listas (enormes) donde se almacenan todos los divisores. Para hacerlo, uso la fórmula que Euclid demostró ser correcta: (2* (potencia de num - 1))* (2* (potencia de num - 1)) donde este último es un mersenne prime. Utilicé un algoritmo muy rápido de StackOverflow (por @Juliet) para determinar si un número dado es un primo.

Mientras he estado leyendo varios artículos (aún no he comprado un buen libro, así que Shame Me) en Internet, descubrí que las secuencias funcionan mejor que las listas. Por eso comencé a crear una función que genera una secuencia de números perfectos:

   let perfectNumbersTwo (n : int) =  
    seq { for i in 1..n do 
           if (PowShift i) - 1I |> isPrime 
           then yield PowShift (i-1) * ((PowShift i)-1I)
        }

El Helperfunction PowShift se implementa como lo siguiente:

    let inline PowShift (exp:int32) = 1I <<< exp ;;

Utilizo un operador de cambio de bit, ya que la base de todos los cálculos de potencia es de 2, por lo tanto, esto podría ser una manera fácil. Por supuesto, todavía estoy agradecido por las contribuciones sobre la pregunta en la que hice sobre esto: F# Problemas de poder que acepta ambos argumentos para ser Bigints>F# problemas de poder que acepta ambos argumentos como bigints

La función que Juliet creó (Toma prestado aquí) es el siguiente:

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 este código, sin paralelo, se tarda unos 9 minutos en mi computadora portátil para encontrar el noveno número perfecto (que consta de 37 dígitos, y se puede encontrar con el valor 31 para el exponente). Dado que mi computadora portátil tiene una CPU con dos núcleos, y solo uno se ejecuta al 50 por ciento (carga completa para un núcleo), pensé que podría acelerar los cálculos calculando los resultados paralelos.

Así que cambié mi función de Number perfects como lo siguiente:

//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);
    }

Para llamar a esta función, uso una función de ayuda para ejecutarla: ejecutarlo:

 let runPerfects n =
    [n]
        |> Seq.map perfectNumbersAsync
        |> Async.Parallel
        |> Async.RunSynchronously
        |> ignore

Donde se ignora el resultado del cálculo de asíncrono, ya que lo estoy mostrando dentro de la función PerfectNumbersasync.

El código anterior compila y se ejecuta, sin embargo, todavía usa solo un núcleo (aunque se ejecuta 10 segundos más rápido al calcular el noveno número perfecto). Me temo que tiene que hacer algo con las funciones de ayudante PowShift e IsPrime, pero no estoy seguro. ¿Tengo que poner el código de estas funciones auxiliares dentro del bloque Async de PerfectNumersasync? No mejora la legibilidad ...

Cuanto más juego con F#, más aprendo a apreciar este idioma, pero como con este caso, a veces necesito algunos expertos :).

Gracias de antemano por leer esto, solo espero que me haya dejado un poco claro ...

Robert.

Solución

El comentario de @Jeffrey Sax es definitivamente interesante, así que me tomé un tiempo para hacer un pequeño experimento. La prueba de Lucas-Lehmer se escribe de la siguiente manera:

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 la prueba de Lucas-Lehmer, puedo obtener los primeros números perfectos muy rápido:

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

La prueba de Lucas-Lehmer ayuda a reducir el tiempo comprobando los números primos. En lugar de probar la divisibilidad de 2^p-1 que toma O(sqrt(2^p-1)), usamos la prueba de primalidad que es como máximo O(p^3). Con n = 2048, Puedo encontrar los primeros 15 números de Mersenne en 7.83 segundos. El número 15 de Mersenne es el de i = 1279 y consta de 770 dígitos.

Traté de paralelizar runPerfects Usando el módulo PSEQ en F# Powerpack. PSEQ no preserva el orden de la secuencia original, por lo que para ser justos he ordenado la secuencia de salida. Dado que la prueba de Primalidad es bastante equilibrada entre los índices, el resultado es bastante alentador:

#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 la misma entrada, la versión paralela tomó 2.28 segundos que es equivalente a una aceleración de 3.4x en mi máquina de cuatro núcleos. Creo que el resultado podría mejorarse aún más si usa Parallel.For Construya y divide el rango de entrada con sensatez.

Otros consejos

Un comentario rápido sobre la velocidad y la paralelelabilidad,

Su isPrime es o (sqrt (n)), y cada N excesivo es aproximadamente 2 x tan grande como el último, por lo que tomará aproximadamente 1,5 x el tiempo en calcular, lo que significa que calcular los últimos números llevará mucho más tiempo más tiempo

He hecho un pirateo con pruebas de Primalidad y algunas cosas que he encontrado que son útiles son:

Para Big N, (está probando números con 20 dígitos), la densidad principal es bastante baja, por lo que hará muchas divisiones por números compuestos. Un mejor enfoque es precalcular una tabla de primos (usando un tamiz) hasta algún límite máximo (probablemente determinado por la cantidad de memoria). Tenga en cuenta que es más probable que encuentre factores con números pequeños. Una vez que se quede sin memoria para su tabla, puede probar el resto de los números con su función existente, con un punto de partida más grande.
Otro enfoque es usar múltiples hilos en la verificación. Por ejemplo, actualmente verifica x,x+4,x+6... como factores. Al ser un poco más inteligente, puede hacer el número congruente a 1 mod 3 en 1 subproceso y los números congruentes a 2 mod 3 en otro hilo.

El número 2 es más simple, pero el número 1 es más efectivo y proporciona potencial para hacer el flujo de control con OutOfMemoryExcepciones que siempre pueden ser interesantes

EDITAR:Así que implementé ambas ideas, encuentra 2305843008139952128 casi al instante, encontrar 2658455991569831744654692615953842176 toma 7 minutos en mi computadora (Quad Core AMD 3200). La mayor parte del tiempo se dedica a verificar 2^61 es primo, por lo que un algoritmo mejor probablemente sería mejor para verificar los números primos: código aquí

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

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow