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.

Pages: 1 2

3 Responses to “Learn A New Language”

  1. Dr. Z. said

    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?

  2. Jussi Piitulainen said

    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.

  3. programmingpraxis said

    Thanks for the defense, Jussi. I generally ignore folks like him. If he does it again, he will be banned.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: