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

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 = [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))
}

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

%d bloggers like this: