## Learn A New Language

I’ve been playing with the Go language for several weeks, and took several hours this Memorial Day weekend to do some programming in it. Here’s my standard set of prime number functions:

```// 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 := 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 := 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))
}```

When run, it produces this output:

```[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 particularly tricky here: `for` loops, arrays, and most arithmetic operations are familiar, the only thing a little bit odd is the array slice `(fs []int)` that accumulates factors (beware: slices are apparently a source of great power in the Go language). Then I rewrote the wheel/rho factoring function for big integers, which are provided by the standard library:

```// factors

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 = *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)
}
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)
}
}
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))
}```

When run, that produces this output:

```[3119 4261]
170296465834288046421517
[291648291013 583910384809]```

I had quite a bit of trouble remembering when functions were called in dot-notation (for instance, `div.DivMod(n, g, mod)` sets both `div` and `mod`) and normal expression notation (the call to `append` in the computation of `fs`), and having two different meanings for `=` and `:=` can’t be a good thing. And it took a while for the asterisk in `(fs []*big.Int)` to make sense (not to mention the “distributed” asterisk in the array definition). Still, I found Go mostly pleasant, rather different from the pointers and memory model of C even with a similar surface syntax.

You can run the two programs above at http://ideone.com/qxLQ0D and http://ideone.com/fXvo2R.

Pages: 1 2