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

はじめに

スミマセン完全にネタ投稿です。
詳しくはリンク先を参照。

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

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

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

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

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 と言うわけです⁴。
チェックする数値の個数が 2/3 に減るので、速度は理論上 x1.5⁵、ということです。

参考

• 汎用的でけっこう速い素数無限列挙（5年前に私が書いたブログ記事、↑とほぼ同等のコードを Ruby で書いています）
• 汎用的で省メモリかつかなり速い素数無限列挙（↑の翌日に書いた記事、少し詳しい解説とさらに高速な別のコード提示）
• 上限を決めずに素数を生成の高速化(Ruby版)（↑↑のさらに元とした記事。2006/06/19 なので、論文 The Genuine Sieve of Eratosthenes よりもさらに3年前ですね）

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

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

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

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

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