F＃完全な問題を計算するときの問題？

StackOverflow https://stackoverflow.com/questions/8368107

質問

特定の指数から完全な数値を計算する小さなプログラムを最適化しようとしています。

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

この質問をできる限り明確にしようとしますが、そうすることに失敗した場合はお知らせください。

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

私は素数を使用して計算を加速します。つまり、すべての除数が保存されている（巨大な）リストには興味がありません。そうするために、ユークリッドが正しいことが証明された式を使用します：（2*（num -1））*（2*（num -1））ここで、後者はMersenneプライムです。 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＃のパワーの問題は、両方の議論をbigintsに受け入れます>f＃両方の引数をbigintsに受け入れるパワーの問題

ジュリエットが作成した関数（ここで借りた）次のようです：

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で見つけることができます）を見つけます。私のラップトップには2つのコアが付いたCPUがあり、1つだけが50パーセント（1つのコアの全負荷）で実行されているため、結果を並列に計算することで計算をスピードアップできます。

そこで、私は自分の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

Async計算の結果は無視されます。これは、PerfectNumbersAsync関数内で表示されているためです。

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

F＃で遊ぶほど、この言語に感謝することを学ぶことができますが、この場合と同様に、私は時々専門家を必要としています:)。

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

ロバート。

役に立ちましたか？

解決

@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のMersenne数を見つけることができます。 15番目のMersenne番号はあります i = 1279 770桁で構成されています。

私は並行しようとしました runPerfects PSEQモジュールを使用します F＃PowerPack. 。 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 入力範囲を賢明に構築して分割します。

他のヒント

速度と並列性に関する1つの簡単なコメント、

君の isPrime o（sqrt（n））であり、各成功nは最後のnと同じくらい大きいので、計算するのに約1.5 xかかります。つまり、最後の数値を計算するにはもっと時間がかかります。

私は、原始性のテストでハッキングをしました。

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

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

No. 2は最も簡単ですが、No。1がより効果的であり、AutofMemoryExceptionsで制御フローを実行する可能性を提供します。

編集：そこで、これらの両方のアイデアを実装しました。230584300813952128をほぼ瞬時に見つけます。2658455991569831744654692615953842176のコンピューターで7分かかります（Quad Core AMD 3200）。ほとんどの時間は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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top