计算完美数时出现F#并行化问题? [英] F# parallelizing issue when calculating perfect numbers?

问题描述

我正在尝试优化一个小程序，该程序可以根据给定的指数计算出完美的数字.

I am trying to optimize a small program which calculates perfect numbers from a given exponent.

该程序(几乎)完美运行，但是当我打开任务管理器时，它仍在单个线程上运行.这意味着我必须做错了事，但是我对F#的了解仍处于开始"阶段.

The program runs (almost) perfectly, but when I open the task manager, it still runs on a single thread. That means that I must be doing something wrong, but my knowledge of F# is still in a 'beginning' phase.

我会尽力澄清这个问题，但是如果我没有这样做，请告诉我.

I will try to put this question as clear as I possibly can, but if I fail in doing so, please let me know.

一个完美数是一个数字，其中所有除数的总和(数字本身除外)等于数字本身(例如6是完美的，因为其除数1、2和3的和为6).

A perfect number is a number where the sum of all it's divisors (except for the number itself) is equal to the number itself (e.g. 6 is perfect, since the sum of it's divisors 1, 2 and 3 are 6).

我使用质数来加快计算速度，也就是说，我对存储所有除数的(巨大)列表不感兴趣.为此，我使用Euclid证明是正确的公式:(2 *(num的幂-1))*(2 *(num的幂-1))，其中后者是梅森素数.我使用了来自stackoverflow(@Juliet)的非常快速的算法来确定给定的数字是否为质数.

I use prime numbers to speed up the calculation, that is I am not interested in (huge) lists where all the divisors are stored. To do so, I use the formula that Euclid proved to be correct: (2*(power of num - 1)) * ( 2* (power of num - 1)) where the latter is a Mersenne prime. I used a very fast algorithm from stackoverflow (by @Juliet) to determine whether a given number is a prime.

当我在互联网上阅读几篇文章(我还没有购买好书，真可惜)时，我发现序列的表现比列表更好.因此，这就是为什么我首先开始创建一个生成一系列完美数字的函数的原因:

As I have been reading through several articles (I have not yet purchased a good book, so shame on me) on the Internet, I found out that sequences perform better than lists. So that is why I first started to create a function which generates a sequence of perfect numbers:

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

辅助功能PowShift的实现方式如下:

The helperfunction PowShift is implemented as following:

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

我使用一位移位运算符，因为所有功率计算的基数均从2开始，因此这可能是一种简单的方法.当然，对于在以下问题上提出的问题，我仍然感激不尽:F#电源问题，接受两个参数均为bigints>

I use a bit shift operator, since the base of all power calculations is from 2, hence this could be an easy way. Of course I am still grateful for the contributions on the question I asked about this on: F# Power issues which accepts both arguments to be bigints>F# Power issues which accepts both arguments to be bigints

朱丽叶创建的函数(在这里借用)如下:

The function Juliet created (borrowed here) is as following:

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;;

使用此代码时，如果没有并行操作，则需要9分钟才能在我的笔记本电脑上找到第9个完美数字(该数字由37位数字组成，并且指数值为31).由于我的笔记本电脑的CPU具有两个核心，并且只有一个以50％的速度运行(一个核心的满负载)，因此我可以通过并行计算结果来加快计算速度.

Using this code, without parallel, it takes about 9 minutes on my laptop to find the 9th perfect number (which consists of 37 digits, and can be found with value 31 for the exponent). Since my laptop has a CPU with two cores, and only one is running at 50 percent (full load for one core) I though that I could speed up the calculations by calculating the results parallel.

所以我将我的perfectnumber函数更改如下:

So I changed my perfectnumber function as following:

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

要调用此函数，我使用一个小的辅助函数来运行它:

To call this function, I use a small helper function to run it:

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

异步计算的结果将被忽略，因为我将其显示在 perfectNumbersAsync函数.

Where the result of async calculation is ignored, since I am displaying it within the perfectNumbersAsync function.

上面的代码可以编译并运行，但是它仍然仅使用一个内核(尽管在计算第9个完美数字时运行速度快了10秒).恐怕它必须与辅助函数PowShift和isPrime做一些事情，但是我不确定.我是否必须将这些辅助函数的代码放入perfectNumbersAsync的异步块中?它不会提高可读性...

The code above compiles and it runs, however it still uses only one core (although it runs 10 seconds faster when calculating the 9th perfect number). I am afraid that it has to do something with the helper functions PowShift and isPrime, but I am not certain. Do I have to put the code of these helper functions within the async block of perfectNumbersAsync? It does not improve readability...

我玩F#的次数越多，我越会学会使用这种语言，但是在这种情况下，有时我需要一些专家:).

The more I play with F#, the more I learn to appreciate this language, but as with this case, I am in need of some experts sometimes :).

多谢阅读此书，我只希望自己能清楚一点...

Thanks in advance for reading this, I only hope that I made myself a bit clear...

罗伯特.

推荐答案

@Jeffrey Sax的评论确实很有趣，因此我花了一些时间做一个小实验. Lucas-Lehmer检验的编写如下:

@Jeffrey Sax's comment is definitely interesting, so I took some time to do a small experiment. The Lucas-Lehmer test is written as follows:

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

通过卢卡斯·莱默(Lucas-Lehmer)测试，我可以非常快速地得到前几个完美数字:

With the Lucas-Lehmer test, I can get first few perfect numbers very fast:

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

Lucas-Lehmer测试有助于减少检查素数的时间.而不是测试2 ^ p-1的除数O(sqrt(2^p-1))，而是使用最多为O(p^3)的素数测试. 使用n = 2048，我能够在7.83秒内找到前15个梅森数字.第15个梅森编号是带有i = 1279的数字，它由770位数字组成.

The Lucas-Lehmer test helps to reduce the time checking prime numbers. Instead of testing divisibility of 2^p-1 which takes O(sqrt(2^p-1)), we use the primality test which is at most O(p^3). With n = 2048, I am able to find first 15 Mersenne numbers in 7.83 seconds. The 15th Mersenne number is the one with i = 1279 and it consists of 770 digits.

我尝试使用 F#Powerpack 中的PSeq模块并行化runPerfects. PSeq不会保留原始序列的顺序，因此，为了公平起见，我对输出序列进行了排序.由于素数测试在各个指标之间相当平衡，因此结果令人鼓舞:

I tried to parallelize runPerfects using PSeq module in F# Powerpack. PSeq doesn't preserve the order of the original sequence, so to be fair I have sorted the output sequence. Since the primality test is quite balance among indices, the result is quite encouraging:

#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

使用相同的输入，并行版本花费了2.28秒，相当于我的四核计算机上的3.4倍加速.我相信，如果您使用Parallel.For构造并合理地划分输入范围，则可以进一步改善结果.

With the same input, the parallel version took 2.28 seconds which is equivalent to 3.4x speedup on my quad-core machine. I believe the result could be improved further if you use Parallel.For construct and partition the input range sensibly.

这篇关于计算完美数时出现F#并行化问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！