Перейти большой. Внутри факториала с рекурсией

Я пытаюсь реализовать этот бит кода:

func factorial(x int) (result int) {
  if x == 0 {
    result = 1;
  } else {
    result = x * factorial(x - 1);
  }
  return;
}

как большой. Чтобы сделать его эффективным при больших значениях х.

Возвращается значение 0 для fmt.Println(factorial (r))

Факториал 7 должен быть 5040?

Любые идеи о том, что я делаю неправильно?

package main

import "fmt"
import "math/big"

func main() {
        fmt.Println("Hello, playground")

    //n := big.NewInt(40)
    r := big.NewInt(7)

    fmt.Println(factorial(r))

}

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = n.Mul(n, factorial(n.Sub(n, c)))
    }
    return result
}

Этот код на игровой площадке: http://play.golang.org/p/yNlioSdxi4

Ответы

Ответ 1

В вашей версии int каждый int отличается. Но в вашей версии big.Int вы фактически используете значения big.Int. Поэтому, когда вы говорите

result = n.Mul(n, factorial(n.Sub(n, c)))

Выражение n.Sub(n, c) на самом деле сохраняет 0 обратно в n, поэтому, когда n.Mul(n, ...) оценивается, вы в основном делаете 0 * 1, и в результате вы возвращаетесь 0.

Помните, что результаты операций big.Int не просто возвращают их значение, но также сохраняют их в приемнике. Вот почему вы видите повторение в выражениях типа n.Mul(n, c), например. почему он принимает n снова как первый параметр. Поскольку вы также можете сказать result.Mul(n, c), и вы получите то же значение обратно, но оно будет храниться в result вместо n.

Вот ваш код, переписанный, чтобы избежать этой проблемы:

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = new(big.Int)
        result.Set(n)
        result.Mul(result, factorial(n.Sub(n, c)))
    }
    return
}

И вот немного более очищенная/оптимизированная версия (я попытался удалить посторонние выделения big.Int s): http://play.golang.org/p/feacvk4P4O

Ответ 2

Go package math.big имеет func (*Int) MulRange(a, b int64). Когда вызывается с первым параметром, установленным в 1, он возвращает b!:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x := new(big.Int)
    x.MulRange(1, 10)
    fmt.Println(x)
}

Произведет

3628800

Ответ 3

Например,

package main

import (
    "fmt"
    "math/big"
)

func factorial(x *big.Int) *big.Int {
    n := big.NewInt(1)
    if x.Cmp(big.NewInt(0)) == 0 {
        return n
    }
    return n.Mul(x, factorial(n.Sub(x, n)))
}

func main() {
    r := big.NewInt(7)
    fmt.Println(factorial(r))
}

Вывод:

Ответ 4

Нерекурсивная версия:

func FactorialBig(n uint64) (r *big.Int) {
    //fmt.Println("n = ", n)
    one, bn := big.NewInt(1), new(big.Int).SetUint64(n)
    r = big.NewInt(1)
    if bn.Cmp(one) <= 0 {
        return
    }
    for i := big.NewInt(2); i.Cmp(bn) <= 0; i.Add(i, one) {
        r.Mul(r, i)
    }
    return
}

playground