Bernoulli numbers: Difference between revisions
→{{header|Sidef}}: code simplications and added 2 more algorithms
(Fix the R solution) |
(→{{header|Sidef}}: code simplications and added 2 more algorithms) |
||
Line 3,759:
=={{header|Sidef}}==
Built-in:
<lang ruby>say bernoulli(42).as_frac #=> 1520097643918070802691/1806</lang>
Recursive solution (with auto-memoization):
<lang ruby>func bernoulli_number(n) is cached {
n.is_one && return 1/2▼
n.is_odd && return 0▼
binomial(n, k) * (bernoulli_number(k) / (n - k + 1))▼
1 - sum(^n, {|k|
})
}
}</lang>
Using Ramanujan's congruences (pretty fast):
▲ n.is_one && return 1/2
<lang ruby>func ramanujan_bernoulli_number(n) is cached {
▲ n.is_odd && return 0
return 1/2 if n.is_one
return 0 if n.is_odd
((n%6 == 4 ? -1/2 : 1) * (n+3)/3 - sum(1 .. (n - n%6)/6, {|k|
binomial(n+3, n - 6*k) * __FUNC__(n - 6*k)
})) / binomial(n+3, n)
}</lang>
Using Euler's product formula for the Riemann zeta function and the Von Staudt–Clausen theorem (very fast):
<lang ruby>func bernoulli_number_from_zeta(n) {
n.is_zero && return 1
n.is_one && return 1/2
n.is_odd && return 0
var log2B = (log(4*Num.tau*n)/2 + n*log(n) - n*log(Num.tau) - n)/log(2)
local Num!PREC = *(int(n + log2B) + (n <= 90 ? 18 : 0))
var K = 2*(n! / Num.tau**n)
var d = n.divisors.grep {|k| is_prime(k+1) }.prod {|k| k+1 }
var N = ceil((K*d).root(n-1))
var z = 1
for p in (primes(N)) {
z *= (1 - float(p)**(-n))
}
(-1)**(n/2 + 1) * int(ceil(d*K / z)) / d
▲for i (0..60) {
▲ printf("B(%2d) = %44s / %s\n", i, num.nude)
}</lang>
The Akiyama–Tanigawa algorithm:
<lang ruby>func bernoulli_print {
var a = []
| |||