Programming Praxis

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.

Pages: 1 2