go - 新的去；如何使用数学/大

Question

我是 Go 新手，但不是编程新手。我正在尝试在质数上实现一些函数作为一种学习方式。这是我的代码，您可以在 运行它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))
}

这很好用。我想知道如何在编译时将 wheel 初始化为常量，以便它可以被 isPrime 和 factors 共享，我会感谢对我程序的风格或其他方面的任何评论。

我最终想使用 math/big 包在大整数上实现一些因式分解算法。但是我有很多麻烦。通过算法的 2、3、5 轮部分简化为试验部分，这是我的代码:

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

那行不通； ideone 提示找不到 Add、Div、Mod 和 Mul 函数。在我看来，它在风格上相当丑陋。

请告诉我如何修复我的factors 函数。

编辑 1:感谢@TClaverie，我现在有了一个可以编译的函数。现在我遇到运行时错误，并且 ideone 指向 Mul 函数。再一次，有人可以帮忙吗？我修改后的代码显示在下方和 。 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)))
}

编辑 2:感谢@TClaverie，我学到了很多关于 Go 的知识，而且我已经接近解决方案了。但是我还有一个问题；程序

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

打印以下输出，表明 wheel 在调用 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]

防止这种情况发生的正确方法是什么？

Answer 1

因此，如果您查看文档，您会看到 Add、Div 和 Mul 是为类型 定义的>*big.Int，因此您必须使用带点符号的 *big.Int 来调用它们。此外，他们期望类型为 *big.Int 的参数，但您给他们的是 big.Int。

如果您查看文档，您还会看到这些函数属于以下类型:z.Op(x, y)。他们应用 x Op y 并将结果存储到另一个名为 z 的 *big.Int 中。因此，您需要一个虚拟的 *big.Int，我将其称为 z(这些方法同时返回它)。

最后，在这种情况下最好使用指针，因为所有方法都使用指针。

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])

最后一件事:你的条件在第二个 for 中被打破，因为你给它一个 int 而不是 boolean。

因此，我不保证这些修改后的代码可以正常工作，但您将能够编译和调试它。