计算完美数时 F# 并行化问题？

Question

我正在尝试优化一个根据给定指数计算完美数的小程序。

程序运行(几乎)完美，但当我打开任务管理器时，它仍然在单线程上运行。这意味着我一定做错了什么，但我对 F# 的了解仍处于“开始”阶段。

我会尽量把这个问题说清楚，但如果我没说清楚，请告诉我。

完美数是指所有除数之和(除了数字本身)等于数字本身的数字(例如 6 是完美数，因为它的除数 1、2 和 3 之和为 6)。

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

我在网上看了好几篇文章(我还没有买到一本好书，太丢人了)，我发现序列比列表表现更好。所以这就是为什么我首先开始创建一个生成完美数字序列的函数:

   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 的实现如下:

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

我使用位移运算符，因为所有幂计算的基数都来自 2，因此这可能是一种简单的方法。当然，我仍然感谢对我提出的问题的贡献:F# Power issues which accepts both arguments to be bigints> F# Power issues which accepts both arguments to be bigints

Juliet 创建的函数(borrowed here)如下:

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% 的速度运行(一个内核满载)，我认为我可以通过并行计算结果来加快计算速度。

所以我改变了我的 perfectnumber 函数如下:

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

为了调用这个函数，我使用了一个小的辅助函数来运行它:

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

异步计算的结果被忽略，因为我在perfectNumbersAsync 函数。

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

我使用 F# 的次数越多，我就越学会欣赏这门语言，但对于这种情况，有时我需要一些专家 :)。

预先感谢您阅读本文，我只希望我让自己清楚一点...

罗伯特。

Answer 1

@Jeffrey Sax 的评论肯定很有趣，所以我花了一些时间做了一个小实验。 Lucas-Lehmer检验写法如下:

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 测试，我可以非常快地获得前几个完美数字:

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 位数字组成。

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

#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 合理地构造和划分输入范围，结果可能会进一步改善。