Go
golang
数学
素数

Golangで「エラトステネスの篩」で「1.3秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた

More than 1 year has passed since last update.


はじめに

スミマセン完全にネタ投稿です。

詳しくはリンク先を参照。

golang は Hello World 程度しか書いたことない1のですが、この素数無限列挙ネタは知っていたので「それほんのちょっとの工夫でさらに1.5倍速できるよ」ということで。アンサーソングというか何というか。


クロージャを用いた実装(改)2

私が追記修正した主な箇所に「// ←ココ」みたいなコメント書いておきました3


prime_generator_with_clojure_ex.go

package main

import (
"fmt"
)

type PrimeGenerator struct {
Next func() uint32
}

func NewPrimeGenerator() *PrimeGenerator {
primeGenerator := PrimeGenerator{}

multiples := map[uint32]uint32{}
var num uint32
var d uint32 // ←ココ
primeGenerator.Next = func() uint32 {
if num == 0 {
num = 1
return 2
}
if d == 0 { // ←ココ
d = 4
return 3
}

for ;; {
num += d
d = 6 - d
var k uint32 = 2 // ←ココ

factor, hasFactor := multiples[num]
if hasFactor {
delete(multiples, num)
// ↓ココ
if (num + factor) % 3 == 0 {
k = 1
}
} else {
factor = num
}

// ↓ココ
for newNum := num + (factor << k); ; newNum += factor << k {
_, hasNewFactor := multiples[newNum]
if !hasNewFactor {
multiples[newNum] = factor
break
}
k ^= 3 // ←ココ
}

if !hasFactor {
return num
}
}
}

return &primeGenerator
}

func main() {
n := 1000000
primeGenerator := NewPrimeGenerator()
for i := 1; i < n; i++ {
primeGenerator.Next()
}
fmt.Printf("%d番目の素数: %d", n, primeGenerator.Next())
}



結果

ideone: https://ideone.com/cunq6q (1.32s)


簡単に解説

元記事 の prime_generator_with_clojure.go では、num にどんどん 2 を足すことで奇数をどんどん生成し、それを篩にかけています。

でも奇数って、3回に1回は3の倍数になります。(3より大きい)3の倍数は当たり前ですが素数ではありません。それを毎回篩にかけるのはもったいない。

そこで、num = 1 から始めて、num += 4num += 2num += 4num += 2 … と繰り返すと、1, 5, 7, 11, 13, … となり、3の倍数をうまく除いて奇数を列挙できます!

この仕組みを利用したのが、先ほどの prime_generator_with_clojure_ex.go と言うわけです4

チェックする数値の個数が 2/3 に減るので、速度は理論上 x1.55、ということです。


参考





  1. これが golang 初記事です。 



  2. チャネルを用いた実装も同様の修正で x1.5化 できます(はず)。取り敢えずクロージャの方が速いのでそちらだけ示します。 



  3. golang に関しては超初心者なので、私が書き足した部分に関して「もっとこう書いた方が良いよ」という Suggest があればコメントなり編集リクエストなりいただければありがたいです。 



  4. 実際にはnewNumを算出する際にも一工夫必要です。詳しくはコードと参考に挙げた私の過去ブログ記事による解説等を参照してください。 



  5. 実測値は(たまたまですが)約x1.6 になっていますね。