はじめに
スミマセン完全にネタ投稿です。
詳しくはリンク先を参照。
- C#で「エラトステネスの篩」で「2.6秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた
- Golangで「エラトステネスの篩」で「2.1秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた
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 += 4、num += 2、num += 4、num += 2 … と繰り返すと、1, 5, 7, 11, 13, … となり、3の倍数をうまく除いて奇数を列挙できます！
この仕組みを利用したのが、先ほどの prime_generator_with_clojure_ex.go と言うわけです4。
チェックする数値の個数が 2/3 に減るので、速度は理論上 x1.55、ということです。
参考
- 汎用的でけっこう速い素数無限列挙（5年前に私が書いたブログ記事、↑とほぼ同等のコードを Ruby で書いています）
- 汎用的で省メモリかつかなり速い素数無限列挙（↑の翌日に書いた記事、少し詳しい解説とさらに高速な別のコード提示）
- 上限を決めずに素数を生成の高速化(Ruby版)（↑↑のさらに元とした記事。2006/06/19 なので、論文 The Genuine Sieve of Eratosthenes よりもさらに3年前ですね）