Factorial/Go: Difference between revisions
→{{header|Go}}: library changes
m (Factorial isn't a collection) |
(→{{header|Go}}: library changes) |
||
Line 1:
An implementation of one of Peter Luschny's [http://www.luschny.de/math/factorial/FastFactorialFunctions.htm fast factorial algorithms]. Fast as this algorithm is, I believe there is room to speed it up more with parallelization and attention to cache effects. The Go library has a nice Karatsuba multiplier but it is yet single threaded.
<lang go>package main
import (
"math/big"
"fmt"
"time"
Line 48 ⟶ 47:
func df(s *sieve, n uint) {
start := time.
a := s.factorial(n)
stop := time.
fmt.Printf("n = %d -> factorial %
dtrunc := int64(float64(a.BitLen())
var first, rest big.Int
rest.Exp(first.SetInt64(10), rest.SetInt64(dtrunc), nil)
Line 60 ⟶ 58:
fstr := first.String()
fmt.Printf("%d! begins %s... and has %d digits.\n",
n, fstr, int64(len(fstr))
}
Line 102 ⟶ 100:
rootK := int64(floorSqrt(uint64(k)))
var i int
s.iterateFunc(3, rootK, func(p int64) bool {
q := int64(k) / p
Line 122 ⟶ 120:
return false
})
r := product(factors[0:i])
return r.Mul(r, s.primorial(int64(k/2+1), int64(k)))
}
func (s *sieve) primorial(m, n int64) *big.Int {
Line 131 ⟶ 129:
return big.NewInt(1)
}
if n-m < 200 {
var r, r2 big.Int
Line 138 ⟶ 136:
r.Mul(&r, r2.SetInt64(p))
return false
})
return &r
}
Line 199 ⟶ 197:
}
return true
}
// constants dependent on the word size of sieve.isComposite.
const (
bitsPerInt = 64
mask = bitsPerInt - 1
log2Int = 6
)
func (s *sieve) sieve(n int64) {
if n <= 0 {
Line 227 ⟶ 225:
for c = s1; c < max; c += inc {
s.isComposite[c>>log2Int] |= 1 << (c & mask)
}
for c = s1 + s2; c < max; c += inc {
s.isComposite[c>>log2Int] |= 1 << (c & mask)
Line 304 ⟶ 302:
}
halfLen := len(seq) / 2
lprod := product(seq[0:halfLen])
rprod := product(seq[halfLen:])
return lprod.Mul(lprod, rprod)
} </lang>▼
▲</lang>
Output:
I did 800 because a few others had computed it. Answers come pretty fast up to 10^5 but slow down after that. Times shown are for computing the factorial only. Producing the printable base 10 representation takes longer and isn't fun to wait for.
Line 320 ⟶ 317:
65! pass.
402! pass.
n = 800 -> factorial
800! begins 7710530113... and has 1977 digits.
n = 100000 -> factorial
100000! begins 28242294079... and has 456574 digits.
n = 1000000 -> factorial
1000000! begins 8263931688... and has 5565709 digits.
</pre>
| |||