2

与えられた指数から完全数を計算する小さなプログラムを最適化しようとしています。

プログラムは（ほぼ）完全に実行されますが、タスクマネージャーを開くと、単一のスレッドで実行されます。つまり、私は何か間違ったことをしているに違いありませんが、F＃に関する私の知識はまだ「始まり」の段階にあります。

この質問はできるだけ明確にしようと思いますが、うまくいかない場合はお知らせください。

完全数とは、すべての除数の合計（数自体を除く）が数自体と等しい数です（たとえば、除数1、2、および3の合計は6であるため、6は完全です）。

私は素数を使用して計算を高速化します。つまり、すべての除数が格納されている（巨大な）リストには興味がありません。そのために、Euclidが正しいことが証明された式を使用します：（2 *（numの累乗-1））*（2 *（numの累乗-1））ここで、後者はメルセンヌ素数です。（@Julietによる）stackoverflowの非常に高速なアルゴリズムを使用して、指定された数値が素数であるかどうかを判断しました。

インターネットでいくつかの記事を読んでいると（私はまだ良い本を購入していないので、恥ずかしいです）、シーケンスはリストよりも優れていることがわかりました。そのため、私は最初に完全数のシーケンスを生成する関数を作成し始めました。

   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からであるため、ビットシフト演算子を使用します。したがって、これは簡単な方法である可能性があります。もちろん、私がこれについて尋ねた質問への貢献にはまだ感謝しています：両方の引数をbigintsとして受け入れるF＃電源の問題> F＃両方の引数をbigintsとして受け入れる電源の問題

Julietが作成した（ここで借用した）関数は次のとおりです。

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番目の完全数（37桁で構成され、指数の値31で見つけることができます）を見つけるのに約9分かかります。私のラップトップには2つのコアを備えたCPUがあり、1つだけが50％（1つのコアの全負荷）で実行されているので、結果を並列に計算することで計算を高速化できます。

そこで、完全数関数を次のように変更しました。

//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関数内に表示しているため、無視されます。

上記のコードはコンパイルされて実行されますが、それでも1つのコアしか使用しません（ただし、9番目の完全数を計算すると10秒速く実行されます）。ヘルパー関数のPowShiftとisPrimeで何かをしなければならないのではないかと心配していますが、確かではありません。これらのヘルパー関数のコードをperfectNumbersAsyncの非同期ブロック内に配置する必要がありますか？読みやすさは向上しません...

F＃で遊ぶほど、この言語を理解するようになりますが、この場合と同様に、専門家が必要になることもあります:)。

これを読んでくれてありがとう、私は自分自身を少し明確にしたことを願っています...

ロバート。

4

2 に答える 2

3

@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検定は、素数をチェックする時間を短縮するのに役立ちます。を取る2^p-1の除算性をテストする代わりにO(sqrt(2^p-1))、最大でである素数性テストを使用しO(p^3)ます。を使用n = 2048すると、7.83秒で最初の15個のメルセンヌ数を見つけることができます。15番目のメルセンヌ数はであるものでi = 1279あり、770桁で構成されています。

F＃PowerpackrunPerfectsでPSeqモジュールを使用して並列化しようとしました。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構成を使用して入力範囲を適切に分割すると、結果がさらに改善される可能性があると思います。

于 2011-12-03T14:23:40.197 に答える
3

速度と並列性についての簡単なコメント、

あなたisPrimeはO（sqrt（n））であり、連続する各nは最後のnの約2倍の大きさであるため、計算に約1.5倍の時間がかかります。つまり、最後の数値の計算にははるかに長い時間がかかります。

私は素数性のテストでいくつかのハッキングを行いました、そして私が見つけたいくつかの有用なものは次のとおりです：

  1. 大きなN（20桁の数値をテストしている）の場合、素数密度は実際には非常に低いため、合成数で多くの除算を行うことになります。より良いアプローチは、（おそらくメモリの量によって決定される）いくつかの最大制限まで（ふるいを使用して）素数のテーブルを事前に計算することです。少数の因子を見つける可能性が最も高いことに注意してください。テーブルのメモリが不足したら、より大きな開始点を使用して、既存の関数で残りの数値をテストできます。

  2. 別のアプローチは、チェックで複数のスレッドを使用することです。たとえば、現在x,x+4,x+6...、要因としてチェックしています。少し賢くすることで、1つのスレッドで1 mod 3に一致する数を実行し、別のスレッドで2mod3に一致する数を実行できます。

No. 2は最も単純ですが、No。1の方が効果的であり、OutOfMemoryExceptionsを使用して制御フローを実行する可能性があります。これは常に興味深いものです。

編集： 私はこれらのアイデアの両方を実装しました、それはほぼ瞬時に2305843008139952128を見つけ、2658455991569831744654692615953842176を見つけるのに私のコンピューター（クアッドコアAMD 3200）で7分かかります。ほとんどの時間は2^61の素数のチェックに費やされるため、素数のチェックにはおそらくより良いアルゴリズムの方が適しています。ここにコードを記述します。

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
于 2011-12-03T22:50:59.807 に答える