sieve_of_atkin.go

package main

import (
  m "math" 
)

const LIMIT = 100

func main() {
  // They don't recomend working with raw arrays, so use a slice
  prime_bools := make([]bool, LIMIT + 1)
  sqrt        := int(m.Sqrt(LIMIT))

  // Stay true to the algorithm description
  prime_bools[2], prime_bools[3], prime_bools[5] = true, true, true
  
  for i := 1; i <= sqrt; i++ {
    for j := 1; j <= sqrt; j++ {
      x := uint(i * i)
      y := uint(j * j)

      var n uint

      n = 4*x + y
      if (n <= LIMIT) && (n % 12 == 1 || n % 12 == 5) { prime_bools[n] = !prime_bools[n] }

      n = 3*x + y
      if (n <= LIMIT) && (n % 12 == 7)                { prime_bools[n] = !prime_bools[n] }

      n = 3*x - y
      if (i > j) && (n <= LIMIT) && (n % 12 == 11)    { prime_bools[n] = !prime_bools[n] }
    }
  }

  for i := 5; i <= LIMIT; i++ {
    q := i * i

    if prime_bools[i] {
      for k := 1; k*q <= LIMIT; k++ {
        prime_bools[k*q] = false
      }
    }
  }

  for i, flag := range prime_bools {
    if flag { println(i) }
  }
}

1. Заменить на uint(i * i) – это клево)

2. Странно, что для возведения целого числа в целую положительную степень в общем виде надо столько труда прикладывать: uint(m.Pow(float64(i), 2))

3. Stay true to the algorithm description

   Тут я смотрел на псевдокод, а он, похоже, псевдоправильный

Пара вопросов:

1. Присвоение x := в цикле, будет аллоцировать переменную в рантайме? Разве это лучше, чем если инициализировать переменную на этапе компиляции var x int? В нашем случае ведь это произойдет целых 100 раз (в двойном цикле) + еще 100 раз в цикле с i := 5...
2. Тоже самое с make([]bool, LIMIT + 1). Это же случится в рантайме? Разве не лучшим будет заранее инициализировать этот массив?
3. Можно ли как-то "красивым способом" превратить два умножения в одно на строках 39 и 40?

Странно, что для возведения целого числа в целую положительную степень в общем виде надо столько труда прикладывать: uint(m.Pow(float64(i), 2))

Для квадрата и куба подходят простые умножения. Если надо больше, я бы для целочисленных написал свою функцию. А math.Pow только для флоатов юзал бы.

На мейлинг листе кстати мелькала жалоба, что math работает только с float64. По ходу, это пока не собираются менять, так что можно искать сторонний пекедж с бОльшим набором функций. Или написать свой.

Присвоение x := в цикле, будет аллоцировать переменную в рантайме?

Не факт. Все зависит от продвинутости компилятора. Современные компиляторы даже умеют переставлять местами циклы (делать из вложенного цикла внешний), если это не влияет на семантику, но позволяет ускорить выполнение.

В данном случае, т.к. x и y существуют только внутри цикла, компилятор с большой вероятностью создаст их заранее на стеке. Я руководствуюсь таким правилом -- чем меньше область видимости твоей переменной, тем проще компилятору ее оптимизировать.

Тоже самое с make([]bool, LIMIT + 1). Это же случится в рантайме? Разве не лучшим будет заранее инициализировать этот массив?

Т.к. LIMIT это константа, уже на этапе компиляции размер будет известен. Этот массив скорей всего будет на стеке создан. Вчера только в IRC кто-то подтвердил, что компилятор может make() аллоцировать как на стеке, так и в хипе.

Можно ли как-то "красивым способом" превратить два умножения в одно на строках 39 и 40?

По ходу так. Только менее очевидно стало. Я б оставил, как есть.

    for i := 5; i <= LIMIT; i++ {
        q := i * i

        if prime_bools[i] {
            for q <= LIMIT {
                prime_bools[q] = false
                q += q  // это и есть наше умножение
            }
        }
    }