New to go; how to use math/big

Question

I am new to Go but not to programming. I am trying to implement a few functions on prime numbers as a way to learn. Here's my code, which you can run at http://ideone.com/qxLQ0D:

// 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))
}

That works fine. I would like to know how to initialize wheel as a constant at compile time so that it can be shared by isPrime and factors, and I would appreciate any comments on style or other aspects of my program.

I eventually want to implement some factoring algorithms on big integers, using the math/big package. But I'm having much trouble. Simplifying to just the trial division via a 2,3,5-wheel part of the algorithm, here's my code:

package main

import (
    "fmt"
    "math/big"
)

func factors(n big.Int) (fs []big.Int) {
    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}
    w := 0;
    f := two;
    for big.Mul(*f, *f).Cmp(n) <= 0 {
        for big.Mod(n, *f).Cmp(*zero) {
            fs = append(fs, *f)
            n = big.Div(n, *f)
        }
        f = big.Add(f, wheel[w])
        w += 1
        if w > 11 { w = 3 }
    }
    fs = append(fs, n)
    return fs
}

func main() {
    fmt.Println(factors(*big.NewInt(13290059)))
}

That doesn't work; ideone complains that the Add, Div, Mod and Mul functions are not found. And it looks rather ugly to me, stylistically.

Please tell me how to fix my factors function.

EDIT 1: Thanks to @TClaverie, I now have a function that compiles. Now I am getting a runtime error, and ideone points to the Mul function. Once again, can anyone help? My revised code is shown below and at http://ideone.com/aVBgJg:

package main

import (
    "fmt"
    "math/big"
)

func factors(n *big.Int) (fs []big.Int) {
    var z *big.Int
    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}
    w := 0
    f := two
    z.Mul(f, f)
    for z.Cmp(n) <= 0 {
        z.Mod(n, f)
        for z.Cmp(zero) == 0 {
            fs = append(fs, *f)
            n.Div(n, f)
            z.Mod(n, f)
        }
        f.Add(f, wheel[w])
        w += 1
        if w > 11 { w = 3 }
        z.Mul(f, f)
    }
    fs = append(fs, *n)
    return fs
}

func main() {
    fmt.Println(factors(big.NewInt(13290059)))
}

EDIT 2: Thanks to @TClaverie, I've learned a lot about Go, and I'm close to a solution. But I still have one problem; the program

package main

import (
    "fmt"
    "math/big"
)

func main() {
    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}
    f := two; w := 0
    for f.Cmp(big.NewInt(40)) < 0 {
        fmt.Println(f, w, wheel)
        f.Add(f, wheel[w])
        w += 1; if w == 11 { w = 3 }
    }
}

prints the following output, which shows that wheel is being modified in the call to Add:

2 0 [1 2 2 4 2 4 2 4 6 2 6]
3 1 [1 3 3 4 3 4 3 4 6 3 6]
6 2 [1 6 6 4 6 4 6 4 6 6 6]
12 3 [1 12 12 4 12 4 12 4 6 12 6]
16 4 [1 16 16 4 16 4 16 4 6 16 6]
32 5 [1 32 32 4 32 4 32 4 6 32 6]
36 6 [1 36 36 4 36 4 36 4 6 36 6]

What's the right way to prevent that from happening?

Answer 1

So, if you look at the documentation, you'll see that Add, Div and Mul are defined for the type *big.Int, so you have to call them using a *big.Int with the dot notation. Also, they expect arguments of type *big.Int, but you're giving them big.Int.

If you look at the documentation, you'll also see that those functions are of the type: z.Op(x, y). They apply x Op y and store the result into another *big.Int called z. So, you need a dummy *big.Int, that I'll call z (the methods return it at the same time).

Finally, it's better to work with pointers in this case, as all methods work with pointers.

func factors(n big.Int) (fs []big.Int) --> func factors(n *big.Int) (fs []big.Int)
wheel := [11]big.Int{*one,*two,*two,*four,*two,*four,*two,*four,*six,*two,*six} -->
wheel := [11]*big.Int{one,two,two,four,two,four,two,four,six,two,six}

big.Mul(*f, *f) --> z.Mul(f, f)
big.Mod(n, *f) --> z.Mod(n, f)
n = big.Div(n, *f) --> n.Div(n, f)
f = big.Add(f, wheel[w]) -−> f.Add(f, wheel[w])

A last thing: your condition is broken in the second for, because you are giving it an int instead of a boolean.

So, I do not guarantee the code works after those modifications, but you will be able to make it compile and debug it.