Help us understand the problem. What is going on with this article?

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

More than 3 years have 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 になっていますね。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした