Rosetta Code

Bernoulli numbers: Difference between revisions

Page Discussion

Bernoulli numbers (view source)

Revision as of 22:03, 13 March 2020

16 bytes added ,  4 years ago
Rename Perl 6 -> Raku, alphabetize, minor clean-up
m (→‎{{header|Sidef}}: minor code simplications)
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 314:
B(58)= 84483613348880041862046775994036021/354
B(60)=-1215233140483755572040304994079820246041491/56786730</pre>
 
=={{header|C}}==
{{libheader|GMP}}
Line 377 ⟶ 378:
B(6 ) = 1 / 42
B(8 ) = -1 / 30
B(10) = 5 / 66
B(12) = -691 / 2730
B(14) = 7 / 6
B(16) = -3617 / 510
B(18) = 43867 / 798
B(20) = -174611 / 330
B(22) = 854513 / 138
B(24) = -236364091 / 2730
B(26) = 8553103 / 6
B(28) = -23749461029 / 870
B(30) = 8615841276005 / 14322
B(32) = -7709321041217 / 510
B(34) = 2577687858367 / 6
B(36) = -26315271553053477373 / 1919190
B(38) = 2929993913841559 / 6
B(40) = -261082718496449122051 / 13530
B(42) = 1520097643918070802691 / 1806
B(44) = -27833269579301024235023 / 690
B(46) = 596451111593912163277961 / 282
B(48) = -5609403368997817686249127547 / 46410
B(50) = 495057205241079648212477525 / 66
B(52) = -801165718135489957347924991853 / 1590
B(54) = 29149963634884862421418123812691 / 798
B(56) = -2479392929313226753685415739663229 / 870
B(58) = 84483613348880041862046775994036021 / 354
B(60) = -1215233140483755572040304994079820246041491 / 56786730
</pre>
 
=={{header|C++}}==
 
=== Using Boost | C++11 ===
{{libheader|boost}}
<lang cpp>
 
/**
* Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
* Apple LLVM version 9.1.0 (clang-902.0.39.1)
* Target: x86_64-apple-darwin17.5.0
* Thread model: posix
*/
 
#include <iostream> //std::cout
#include <iostream> //formatting
#include <vector> //Container
#include <boost/rational.hpp> // Rationals
#include <boost/multiprecision/cpp_int.hpp> //1024bit precision
 
 
typedef boost::rational<boost::multiprecision::int1024_t> rational; // reduce boilerplate
 
rational bernulli(size_t n){
 
auto out = std::vector<rational>();
 
for(size_t m=0;m<=n;m++){
out.emplace_back(1,(m+1)); // automatically constructs object
for (size_t j = m;j>=1;j--){
out[j-1] = rational(j) * (out[j-1]-out[j]);
}
}
return out[0];
}
 
int main() {
for(size_t n = 0; n <= 60;n+=n>=2?2:1){
auto b = bernulli(n);
std::cout << "B("<<std::right<<std::setw(2)<<n<<") = ";
std::cout << std::right<<std::setw(44)<<b.numerator();
std::cout << " / " << b.denominator() <<std::endl;
}
 
return 0;
}
</lang>
{{out}}
<pre>
B( 0) = 1 / 1
B( 1) = 1 / 2
B( 2) = 1 / 6
B( 4) = -1 / 30
B( 6) = 1 / 42
B( 8) = -1 / 30
B(10) = 5 / 66
B(12) = -691 / 2730
Line 849 ⟶ 768:
</pre>
 
=={{header|C++}}==
 
=== Using Boost | C++11 ===
{{libheader|boost}}
<lang cpp>
 
/**
* Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
* Apple LLVM version 9.1.0 (clang-902.0.39.1)
* Target: x86_64-apple-darwin17.5.0
* Thread model: posix
*/
 
#include <iostream> //std::cout
#include <iostream> //formatting
#include <vector> //Container
#include <boost/rational.hpp> // Rationals
#include <boost/multiprecision/cpp_int.hpp> //1024bit precision
 
 
typedef boost::rational<boost::multiprecision::int1024_t> rational; // reduce boilerplate
 
rational bernulli(size_t n){
 
auto out = std::vector<rational>();
 
for(size_t m=0;m<=n;m++){
out.emplace_back(1,(m+1)); // automatically constructs object
for (size_t j = m;j>=1;j--){
out[j-1] = rational(j) * (out[j-1]-out[j]);
}
}
return out[0];
}
 
int main() {
for(size_t n = 0; n <= 60;n+=n>=2?2:1){
auto b = bernulli(n);
std::cout << "B("<<std::right<<std::setw(2)<<n<<") = ";
std::cout << std::right<<std::setw(44)<<b.numerator();
std::cout << " / " << b.denominator() <<std::endl;
}
 
return 0;
}
</lang>
{{out}}
<pre>
B( 0) = 1 / 1
B( 1) = 1 / 2
B( 2) = 1 / 6
B( 4) = -1 / 30
B( 6) = 1 / 42
B( 8) = -1 / 30
B(10) = 5 / 66
B(12) = -691 / 2730
B(14) = 7 / 6
B(16) = -3617 / 510
B(18) = 43867 / 798
B(20) = -174611 / 330
B(22) = 854513 / 138
B(24) = -236364091 / 2730
B(26) = 8553103 / 6
B(28) = -23749461029 / 870
B(30) = 8615841276005 / 14322
B(32) = -7709321041217 / 510
B(34) = 2577687858367 / 6
B(36) = -26315271553053477373 / 1919190
B(38) = 2929993913841559 / 6
B(40) = -261082718496449122051 / 13530
B(42) = 1520097643918070802691 / 1806
B(44) = -27833269579301024235023 / 690
B(46) = 596451111593912163277961 / 282
B(48) = -5609403368997817686249127547 / 46410
B(50) = 495057205241079648212477525 / 66
B(52) = -801165718135489957347924991853 / 1590
B(54) = 29149963634884862421418123812691 / 798
B(56) = -2479392929313226753685415739663229 / 870
B(58) = 84483613348880041862046775994036021 / 354
B(60) = -1215233140483755572040304994079820246041491 / 56786730
</pre>
 
=={{header|Clojure}}==
Line 1,369:
B(60) = -1215233140483755572040304994079820246041491 / 56786730
</pre>
 
=={{header|Factor}}==
One could use the "bernoulli" word from the math.extras vocabulary as follows:
Line 1,453 ⟶ 1,454:
...
Running time: 0.004331652 seconds</lang>
 
=={{header|Fōrmulæ}}==
 
In [https://wiki.formulae.org/Bernoulli_numbers this] page you can see the solution of this task.
 
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for transportation effects more than visualization and edition.
 
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
 
=={{header|FreeBASIC}}==
Line 1,596 ⟶ 1,589:
B(60) = -1215233140483755572040304994079820246041491/56786730
</pre>
 
=={{header|Fōrmulæ}}==
 
In [https://wiki.formulae.org/Bernoulli_numbers this] page you can see the solution of this task.
 
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for transportation effects more than visualization and edition.
 
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
 
=={{header|GAP}}==
Line 2,424 ⟶ 2,425:
58 84483613348880041862046775994036021/354
60 -1215233140483755572040304994079820246041491/56786730</pre>
 
 
=={{header|Pascal|FreePascal}}==
Line 2,639:
}</lang>
with the difference being that Pari chooses <math>B_1</math> = -&frac12;.
 
=={{header|Perl 6}}==
 
===Simple===
 
First, a straighforward implementation of the naïve algorithm in the task description.
{{works with|Rakudo|2015.12}}
<lang perl6>sub bernoulli($n) {
my @a;
for 0..$n -> $m {
@a[$m] = FatRat.new(1, $m + 1);
for reverse 1..$m -> $j {
@a[$j - 1] = $j * (@a[$j - 1] - @a[$j]);
}
}
return @a[0];
}
 
constant @bpairs = grep *.value.so, ($_ => bernoulli($_) for 0..60);
 
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%2d) = \%{$width}d/%d\n";
 
printf $form, .key, .value.nude for @bpairs;</lang>
{{out}}
<pre>B( 0) = 1/1
B( 1) = 1/2
B( 2) = 1/6
B( 4) = -1/30
B( 6) = 1/42
B( 8) = -1/30
B(10) = 5/66
B(12) = -691/2730
B(14) = 7/6
B(16) = -3617/510
B(18) = 43867/798
B(20) = -174611/330
B(22) = 854513/138
B(24) = -236364091/2730
B(26) = 8553103/6
B(28) = -23749461029/870
B(30) = 8615841276005/14322
B(32) = -7709321041217/510
B(34) = 2577687858367/6
B(36) = -26315271553053477373/1919190
B(38) = 2929993913841559/6
B(40) = -261082718496449122051/13530
B(42) = 1520097643918070802691/1806
B(44) = -27833269579301024235023/690
B(46) = 596451111593912163277961/282
B(48) = -5609403368997817686249127547/46410
B(50) = 495057205241079648212477525/66
B(52) = -801165718135489957347924991853/1590
B(54) = 29149963634884862421418123812691/798
B(56) = -2479392929313226753685415739663229/870
B(58) = 84483613348880041862046775994036021/354
B(60) = -1215233140483755572040304994079820246041491/56786730</pre>
 
===With memoization===
 
Here is a much faster way, following the Perl solution that avoids recalculating previous values each time through the function. We do this in Perl 6 by not defining it as a function at all, but by defining it as an infinite sequence that we can read however many values we like from (52, in this case, to get up to B(100)). In this solution we've also avoided subscripting operations; rather we use a sequence operator (<tt>...</tt>) iterated over the list of the previous solution to find the next solution. We reverse the array in this case to make reference to the previous value in the list more natural, which means we take the last value of the list rather than the first value, and do so conditionally to avoid 0 values.
 
{{works with|Rakudo|2015.12}}
<lang perl6>constant bernoulli = gather {
my @a;
for 0..* -> $m {
@a = FatRat.new(1, $m + 1),
-> $prev {
my $j = @a.elems;
$j * (@a.shift - $prev);
} ... { not @a.elems }
take $m => @a[*-1] if @a[*-1];
}
}
 
constant @bpairs = bernoulli[^52];
 
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%d)\t= \%{$width}d/%d\n";
 
printf $form, .key, .value.nude for @bpairs;</lang>
{{out}}
<pre>B(0) = 1/1
B(1) = 1/2
B(2) = 1/6
B(4) = -1/30
B(6) = 1/42
B(8) = -1/30
B(10) = 5/66
B(12) = -691/2730
B(14) = 7/6
B(16) = -3617/510
B(18) = 43867/798
B(20) = -174611/330
B(22) = 854513/138
B(24) = -236364091/2730
B(26) = 8553103/6
B(28) = -23749461029/870
B(30) = 8615841276005/14322
B(32) = -7709321041217/510
B(34) = 2577687858367/6
B(36) = -26315271553053477373/1919190
B(38) = 2929993913841559/6
B(40) = -261082718496449122051/13530
B(42) = 1520097643918070802691/1806
B(44) = -27833269579301024235023/690
B(46) = 596451111593912163277961/282
B(48) = -5609403368997817686249127547/46410
B(50) = 495057205241079648212477525/66
B(52) = -801165718135489957347924991853/1590
B(54) = 29149963634884862421418123812691/798
B(56) = -2479392929313226753685415739663229/870
B(58) = 84483613348880041862046775994036021/354
B(60) = -1215233140483755572040304994079820246041491/56786730
B(62) = 12300585434086858541953039857403386151/6
B(64) = -106783830147866529886385444979142647942017/510
B(66) = 1472600022126335654051619428551932342241899101/64722
B(68) = -78773130858718728141909149208474606244347001/30
B(70) = 1505381347333367003803076567377857208511438160235/4686
B(72) = -5827954961669944110438277244641067365282488301844260429/140100870
B(74) = 34152417289221168014330073731472635186688307783087/6
B(76) = -24655088825935372707687196040585199904365267828865801/30
B(78) = 414846365575400828295179035549542073492199375372400483487/3318
B(80) = -4603784299479457646935574969019046849794257872751288919656867/230010
B(82) = 1677014149185145836823154509786269900207736027570253414881613/498
B(84) = -2024576195935290360231131160111731009989917391198090877281083932477/3404310
B(86) = 660714619417678653573847847426261496277830686653388931761996983/6
B(88) = -1311426488674017507995511424019311843345750275572028644296919890574047/61410
B(90) = 1179057279021082799884123351249215083775254949669647116231545215727922535/272118
B(92) = -1295585948207537527989427828538576749659341483719435143023316326829946247/1410
B(94) = 1220813806579744469607301679413201203958508415202696621436215105284649447/6
B(96) = -211600449597266513097597728109824233673043954389060234150638733420050668349987259/4501770
B(98) = 67908260672905495624051117546403605607342195728504487509073961249992947058239/6
B(100) = -94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330</pre>
 
===Functional===
 
And if you're a pure enough FP programmer to dislike destroying and reconstructing the array each time, here's the same algorithm without side effects. We use zip with the pair constructor <tt>=></tt> to keep values associated with their indices. This provides sufficient local information that we can define our own binary operator "bop" to reduce between each two terms, using the "triangle" form (called "scan" in Haskell) to return the intermediate results that will be important to compute the next Bernoulli number.
{{works with|Rakudo|2016.12}}
 
<lang perl6>sub infix:<bop>(\prev, \this) {
this.key => this.key * (this.value - prev.value)
}
 
sub next-bernoulli ( (:key($pm), :value(@pa)) ) {
$pm + 1 => [
map *.value,
[\bop] ($pm + 2 ... 1) Z=> FatRat.new(1, $pm + 2), |@pa
]
}
 
constant bernoulli =
grep *.value,
map { .key => .value[*-1] },
(0 => [FatRat.new(1,1)], &next-bernoulli ... *)
;
 
constant @bpairs = bernoulli[^52];
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%d)\t= \%{$width}d/%d\n";
printf $form, .key, .value.nude for @bpairs;</lang>
 
Same output as memoization example
 
=={{header|Phix}}==
Line 3,254 ⟶ 3,089:
B(58) = 84483613348880041862046775994036021/354
B(60) = -1215233140483755572040304994079820246041491/56786730</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
 
===Simple===
 
First, a straighforward implementation of the naïve algorithm in the task description.
{{works with|Rakudo|2015.12}}
<lang perl6>sub bernoulli($n) {
my @a;
for 0..$n -> $m {
@a[$m] = FatRat.new(1, $m + 1);
for reverse 1..$m -> $j {
@a[$j - 1] = $j * (@a[$j - 1] - @a[$j]);
}
}
return @a[0];
}
 
constant @bpairs = grep *.value.so, ($_ => bernoulli($_) for 0..60);
 
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%2d) = \%{$width}d/%d\n";
 
printf $form, .key, .value.nude for @bpairs;</lang>
{{out}}
<pre>B( 0) = 1/1
B( 1) = 1/2
B( 2) = 1/6
B( 4) = -1/30
B( 6) = 1/42
B( 8) = -1/30
B(10) = 5/66
B(12) = -691/2730
B(14) = 7/6
B(16) = -3617/510
B(18) = 43867/798
B(20) = -174611/330
B(22) = 854513/138
B(24) = -236364091/2730
B(26) = 8553103/6
B(28) = -23749461029/870
B(30) = 8615841276005/14322
B(32) = -7709321041217/510
B(34) = 2577687858367/6
B(36) = -26315271553053477373/1919190
B(38) = 2929993913841559/6
B(40) = -261082718496449122051/13530
B(42) = 1520097643918070802691/1806
B(44) = -27833269579301024235023/690
B(46) = 596451111593912163277961/282
B(48) = -5609403368997817686249127547/46410
B(50) = 495057205241079648212477525/66
B(52) = -801165718135489957347924991853/1590
B(54) = 29149963634884862421418123812691/798
B(56) = -2479392929313226753685415739663229/870
B(58) = 84483613348880041862046775994036021/354
B(60) = -1215233140483755572040304994079820246041491/56786730</pre>
 
===With memoization===
 
Here is a much faster way, following the Perl solution that avoids recalculating previous values each time through the function. We do this in Perl 6 by not defining it as a function at all, but by defining it as an infinite sequence that we can read however many values we like from (52, in this case, to get up to B(100)). In this solution we've also avoided subscripting operations; rather we use a sequence operator (<tt>...</tt>) iterated over the list of the previous solution to find the next solution. We reverse the array in this case to make reference to the previous value in the list more natural, which means we take the last value of the list rather than the first value, and do so conditionally to avoid 0 values.
 
{{works with|Rakudo|2015.12}}
<lang perl6>constant bernoulli = gather {
my @a;
for 0..* -> $m {
@a = FatRat.new(1, $m + 1),
-> $prev {
my $j = @a.elems;
$j * (@a.shift - $prev);
} ... { not @a.elems }
take $m => @a[*-1] if @a[*-1];
}
}
 
constant @bpairs = bernoulli[^52];
 
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%d)\t= \%{$width}d/%d\n";
 
printf $form, .key, .value.nude for @bpairs;</lang>
{{out}}
<pre>B(0) = 1/1
B(1) = 1/2
B(2) = 1/6
B(4) = -1/30
B(6) = 1/42
B(8) = -1/30
B(10) = 5/66
B(12) = -691/2730
B(14) = 7/6
B(16) = -3617/510
B(18) = 43867/798
B(20) = -174611/330
B(22) = 854513/138
B(24) = -236364091/2730
B(26) = 8553103/6
B(28) = -23749461029/870
B(30) = 8615841276005/14322
B(32) = -7709321041217/510
B(34) = 2577687858367/6
B(36) = -26315271553053477373/1919190
B(38) = 2929993913841559/6
B(40) = -261082718496449122051/13530
B(42) = 1520097643918070802691/1806
B(44) = -27833269579301024235023/690
B(46) = 596451111593912163277961/282
B(48) = -5609403368997817686249127547/46410
B(50) = 495057205241079648212477525/66
B(52) = -801165718135489957347924991853/1590
B(54) = 29149963634884862421418123812691/798
B(56) = -2479392929313226753685415739663229/870
B(58) = 84483613348880041862046775994036021/354
B(60) = -1215233140483755572040304994079820246041491/56786730
B(62) = 12300585434086858541953039857403386151/6
B(64) = -106783830147866529886385444979142647942017/510
B(66) = 1472600022126335654051619428551932342241899101/64722
B(68) = -78773130858718728141909149208474606244347001/30
B(70) = 1505381347333367003803076567377857208511438160235/4686
B(72) = -5827954961669944110438277244641067365282488301844260429/140100870
B(74) = 34152417289221168014330073731472635186688307783087/6
B(76) = -24655088825935372707687196040585199904365267828865801/30
B(78) = 414846365575400828295179035549542073492199375372400483487/3318
B(80) = -4603784299479457646935574969019046849794257872751288919656867/230010
B(82) = 1677014149185145836823154509786269900207736027570253414881613/498
B(84) = -2024576195935290360231131160111731009989917391198090877281083932477/3404310
B(86) = 660714619417678653573847847426261496277830686653388931761996983/6
B(88) = -1311426488674017507995511424019311843345750275572028644296919890574047/61410
B(90) = 1179057279021082799884123351249215083775254949669647116231545215727922535/272118
B(92) = -1295585948207537527989427828538576749659341483719435143023316326829946247/1410
B(94) = 1220813806579744469607301679413201203958508415202696621436215105284649447/6
B(96) = -211600449597266513097597728109824233673043954389060234150638733420050668349987259/4501770
B(98) = 67908260672905495624051117546403605607342195728504487509073961249992947058239/6
B(100) = -94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330</pre>
 
===Functional===
 
And if you're a pure enough FP programmer to dislike destroying and reconstructing the array each time, here's the same algorithm without side effects. We use zip with the pair constructor <tt>=></tt> to keep values associated with their indices. This provides sufficient local information that we can define our own binary operator "bop" to reduce between each two terms, using the "triangle" form (called "scan" in Haskell) to return the intermediate results that will be important to compute the next Bernoulli number.
{{works with|Rakudo|2016.12}}
 
<lang perl6>sub infix:<bop>(\prev, \this) {
this.key => this.key * (this.value - prev.value)
}
 
sub next-bernoulli ( (:key($pm), :value(@pa)) ) {
$pm + 1 => [
map *.value,
[\bop] ($pm + 2 ... 1) Z=> FatRat.new(1, $pm + 2), |@pa
]
}
 
constant bernoulli =
grep *.value,
map { .key => .value[*-1] },
(0 => [FatRat.new(1,1)], &next-bernoulli ... *)
;
 
constant @bpairs = bernoulli[^52];
my $width = max @bpairs.map: *.value.numerator.chars;
my $form = "B(%d)\t= \%{$width}d/%d\n";
printf $form, .key, .value.nude for @bpairs;</lang>
 
Same output as memoization example
 
=={{header|REXX}}==
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/241637"