Learn A New Language
May 31, 2016
I’ve been studying the Go programming language for several weeks, and I spent several hours this weekend writing my standard prime-number programs in the language:
// prime numbers package main import ( "fmt" ) // list of primes less than n: // sieve of eratosthenes func primes(n int) (ps []int) { sieve := make([]bool, n) for i := 2; i < n; i++ { if !(sieve[i]) { ps = append(ps, i) for j := i * i; j < n; j += i { sieve[j] = true } } } return ps } // true if n is prime, else false: // trial division via 2,3,5-wheel func isPrime(n int) (bool) { wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6} w := 0 f := 2 for f*f <= n { if n % f == 0 { return false } f += wheel[w] w += 1 if w == 11 { w = 3 } } return true } // greatest common divisor of x and y: // via euclid's algorithm func gcd(x int, y int) (int) { for y != 0 { x, y = y, x % y } return x } // absolute value of x func abs(x int) (int) { if x < 0 { return -1 * x } return x } // list of prime factors of n: // trial division via 2,3,5-wheel // to 1000 followed by pollard rho func factors(n int) (fs []int) { wheel := [11]int{1,2,2,4,2,4,2,4,6,2,6} w := 0 // wheel pointer f := 2 // current trial factor for f*f <= n && f < 1000 { for n % f == 0 { fs = append(fs, f) n /= f } f += wheel[w]; w += 1 if w == 11 { w = 3 } } if n == 1 { return fs } h := 1 // hare t := 1 // turtle g := 1 // greatest common divisor c := 1 // random number parameter for !(isPrime(n)) { for g == 1 { h = (h*h+c) % n // the hare runs h = (h*h+c) % n // twice as fast t = (t*t+c) % n // as the tortoise g = gcd(abs(t-h), n) } if isPrime(g) { for n % g == 0 { fs = append(fs, g) n /= g } } h, t, g, c = 1, 1, 1, c+1 } fs = append(fs, n) return fs } func main() { fmt.Println(primes(100)) fmt.Println(isPrime(997)) fmt.Println(isPrime(13290059)) fmt.Println(factors(13290059)) }
Here’s the output of that program:
[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97] true false [3119 4261]
There’s nothing too tricky here. Most operators look about the same as they do in other languages. The only thing odd is the array slice (fs []int)
to collect factors; in my study of Go, I’ve learned that array slices are a powerful and useful feature of the language. Next, I adapted the factoring program shown above to operate on big integers, which are provided in Go’s standard library:
package main import ( "fmt" "math/big" "sort" ) // sort []*big.Int into increasing order, using sort package type BigIntSlice []*big.Int func (s BigIntSlice) Len() int { return len(s) } func (s BigIntSlice) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 } func (s BigIntSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } func (s BigIntSlice) Sort() { sort.Sort(s) } var ( zero = big.NewInt(0); one = big.NewInt(1); two = big.NewInt(2); four = big.NewInt(4); six = big.NewInt(6); wheel = [11]*big.Int{one,two,two,four,two,four,two,four,six,two,six} ) func factors(n *big.Int) (fs []*big.Int) { mod := new(big.Int) // modulus div := new(big.Int) // dividend limit := big.NewInt(1000) // switch to rho z := big.NewInt(0); // temporary storage w := 0 // wheel index f := big.NewInt(2); // trial divisor z.Mul(f, f) for z.Cmp(n) <= 0 && f.Cmp(limit) <= 0 { div.DivMod(n, f, mod) for mod.Cmp(zero) == 0 { fs = append(fs, new(big.Int).Set(f)) n.Set(div) div.DivMod(n, f, mod) } f.Add(f, wheel[w]); z.Mul(f, f) w += 1; if w == 11 { w = 3 } } if n.Cmp(one) == 0 { return fs } h := big.NewInt(1) // hare t := big.NewInt(1) // tortoise g := big.NewInt(1) // greatest common divisor c := big.NewInt(1) // random number parameter for !(n.ProbablyPrime(20)) { for g.Cmp(one) == 0 { z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z) z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z) z.Mul(t, t); z.Add(z, c); z.Mod(z, n); t.Set(z) z.Sub(t, h); z.Abs(z) g.GCD(nil, nil, z, n) } if g.ProbablyPrime(20) { div.DivMod(n, g, mod) for mod.Cmp(zero) == 0 { fs = append(fs, new(big.Int).Set(g)) n.Set(div) div.DivMod(n, g, mod) } h.Set(one) t.Set(one) g.Set(one) c.Add(c, one) } } fs = append(fs, new(big.Int).Set(n)) sort.Sort(BigIntSlice(fs)) return fs } func main() { fmt.Println(factors(big.NewInt(13290059))) x := big.NewInt(583910384809) y := big.NewInt(291648291013) x.Mul(x,y) fmt.Println(x) fmt.Println(factors(x)) }
And here’s the output:
[3119 4261] 170296465834288046421517 [291648291013 583910384809]
That’s a little bit more complicated, a consequence of the use of big integers instead of native integers. Sorting has to be specially configured. It took me a while to understand where asterisks were needed for indirection, and to know the differences between dot-notation (like div.DivMod(n, g, mod)
), assignment (like fs = append(fs, new(big.Int).Set(g))
), and declaration (like x := big.NewInt(583910384809)
). Still, Go is simpler than C, with its pointers and non-existent memory management, and is a useful language, deserving of a programmer’s toolbox.
You can run the two programs at http://ideone.com/qxLQ0D and http://ideone.com/fXvo2R.
Go, really? The only reason this language hasn’t fallen into oblivion is that it has Google behind it. If it were to compete in fair terms with other languages today, it is bound to fail to make the cut.
Here is the equivalent code for factoring an integer in Julia:
factor(13290059)
As for the primes:
primes(n)
Note that it doesn’t need to import any libraries either, while its performance is comparable to C. So, if you want to learn a new language, do yourself a favor and learn something useful.
Also, since when is 170296465834288046421517 a big Int? Is Go’s memory management so feeble that it can’t handle a 78 bit integer?
Dr. Z., there is no call for such rudeness.
Incidentally, Julia developers have moved these functions out of Base. Need to be imported, they will.
Thanks for the defense, Jussi. I generally ignore folks like him. If he does it again, he will be banned.