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

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

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.