计算完美数时的 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.

由于我已经阅读了 Internet 上的几篇文章(我还没有购买一本好书，我感到很惭愧)，我发现序列比列表表现得更好.所以这就是为什么我首先开始创建一个生成完美数字序列的函数:

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# Power issues which accepting both arguments to be bigints>F# Power 问题，它接受两个参数都是 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

Juliet 创建的函数(此处借用) 如下:

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.

所以我改变了我的完美数字函数如下:

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 检验有助于减少检查素数的时间.我们不使用 O(sqrt(2^p-1)) 测试 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屋！