Binomial-Koeffizienten mit Perl
|
Pascal-Algorithmus
Die rechts vorgestellte Funktion binomial_coef_1()
berechnet einen einzelnen Binomial-Koeffizienten
rekursiv nach dem oben angegebenen 'Pascal-Algorithmus'.
Anwendung in einem Perl-Programm:
$k = binomial_coef_1($i,$j);
Rechenzeit: (Vergleichswerte eines typischen PC)
(10|5) in 0.18ms, (20|10) in 120ms, (30|15) in 96000ms
Die Rechenzeiten steigen für größere Argumente so stark an,
dass die Funktion in der Praxis kaum noch verwendbar ist.
|
Berechnung eines Binomial-Koeffizienten mit
Perl
sub binomial_coef_1 {
my($i,$j)=@_;
my($k);
$k=0;
if($j<=$i) {
if($j>$i/2) {$j=$i-$j;}
if($j==1) {$k=$i;}
elsif(!$j) {$k=1;}
else{
$k=binomial_coef_1($i-1,$j)+binomial_coef_1($i-1,$j-1);
}
}
return $k;
}
|
Produkt-Algorithmus
Die rechts vorgestellte Funktion binomial_coef_2()
berechnet einen einzelnen Binomial-Koeffizienten
nach dem oben angegebenen 'Produkt-Algorithmus'.
Anwendung in einem Perl-Programm:
$k = binomial_coef_2($i,$j);
●
Diese Variante rechnet für einzelne Binomial-Koeffizienten bis
zu (1029|*) besonders schnell, allerdings nur
mit einer maximalen Genauigkeit von 15 Dezimalstellen.
Rechenzeit: (Vergleichswerte eines typischen PC)
(10|5) in 0.003ms, (50|25) in 0.011ms, (100|50) in 0.02ms
|
Berechnung eines Binomial-Koeffizienten mit
Perl
nach dem Produkt-Algorithmus:
sub binomial_coef_2 {
my($n,$k)=@_;
my($j,$p);
$p=1.0;
for($j=1;$j<=$k;$j++) {
$p*=($n+1-$j)/$j;
}
return $p;
}
|
Array von Binomial-Koeffizienten
Das rechts vorgestellte Perl-Programm berechnet alle Binomial-Koeffizienten
bis zu einer vorgegebenen Grenze (hier: $imax,$jmax),
die hier im Programm vorgegeben wird. Dazu wird der 'Pascal-Algorithmus' verwendet.
Die Berechnung der Koeffizienten wird von der Funktion create_bca()
durchgeführt. Die Ergebnisse werden in einem
→ Array
(hier @bca) gespeichert.
Das →
Array @bca ist im Beispiel global, man braucht daher
seine Adresse nicht an die Funktion zu übergeben.
Als Beispiel für die Anwendung wird im Hauptprogramm ein einzelner
Koeffizient aus dem Array entnommen und angezeigt.
●
Diese Variante berechnet ein komplettes Array von Binomial-Koeffizienten
besonders schnell, allerdings nur mit einer maximalen Genauigkeit von 15
Dezimalstellen. Für exakte große Zahlen verwendet man das ↓
Perl-Modul Math::BigInt
Rechenzeit: (Vergleichswerte eines typischen PC):
(10|10) in 0.08ms, (50|50) in 1.2ms, (100|100) in 4.6ms
|
Berechnung eines Arrays von Binomial-Koeffizienten mit mit
Perl
#!/usr/bin/perl
use strict;
my($imax,$jmax,$k,@bca);
$imax = 10;
$jmax = floor($i/2);
bca_create($imax,$jmax);
$k = $bca[$i][$j];
print "($i|$j) = $k\n";
sub bca_create {
my($imax,$jmax)=@_;
my($i,$j,$bc);
for($i=0;$i<=$imax;$i++) {
for($j=0;$j<=$jmax;$j++) {
if(!$j) {$bc = 1;} # col 0
elsif($j>$i) {$bc = 0;} # illegal
elsif($j==1) {$bc = $i;} # col 1
elsif($j>($i/2)) {$bc = $bca[$i][$i-$j];} # sym
else {$bc = $bca[$i-1][$j] + $bca[$i-1][$j-1];} # add
$bca[$i][$j] = $bc;
}
}
}
|
Produkt-Algorithmus für große Zahlen
Perl bietet das
kostenfreie Modul Math::Big zum Rechnen mit beliebig
großen ganzen Zahlen. Diese werden bei der Ein- und Ausgabe als
Ziffern-Strings verwaltetet. Das Modul arbeitet langsamer als Standard-Perl,
berechnet jedoch fast beliebige Binomial-Koeffizienten mit absoluter Genauigkeit.
Das Beispiel zeigt ein vollständiges Perl-Programm. Es demonstriert die Einbindung
des Math::Big Moduls, die Funktion und seine Anwendung.
Beachten sie bei der Anwendung, dass die Funktion einen String (!) zurückgibt.
Zur übersichtlichen Ausgabe muss man den String in ein lesbares Format bringen,
z.B. mit Funktion bint_to_sci() von der Seite zur
→ Fakultät-Funktion.
Der Algorithmus verwendet Bruchzahlen (Rationale Zahlen), daher ist das
Teil-Modul Math::BigRat wesentlich besser zur Rechnung geeignet
als Math::Float
Rechenzeit: (Vergleichswerte eines typischen PC)
(10|5) in 0.70ms, (100|50) in 8.6ms, (1000|500) in 250ms, (10000|5000) in 20s
|
Berechnung eines Binomial-Koeffizienten mit
Perl
nach dem 'Produkt-Algorithmus':
#!/usr/bin/perl
use strict;
use Math::BigRat;
my($i,$j,$bc);
$i=1200; $j=600;
$bc = binomial_coef_big($i,$j);
printf("(%d|%d) = %s\n",$i,$j,$bc);
sub binomial_coef_big {
my($n,$k)=@_;
my($j,$p);
$p = Math::BigRat->new(1);
for($j=1;$j<=$k;$j++) {
$p->bmul($n+1-$j);
$p->bdiv($j);
}
return $p;
}
|
Array für große Zahlen
Das rechts vorgestellte Perl-Programm berechnet mit dem Modul
Math:BigInt alle Binomial-Koeffizienten bis zu einer vorgegebenen Grenze
(hier: $imax,$jmax), die hier im Programm vorgegeben wird.
Dazu wird der 'Pascal-Algorithmus' verwendet.
Die Berechnung der Koeffizienten wird von der Funktion create_bca_big()
durchgeführt. Die Ergebnisse (Strings !) werden in einem
→ Array
(hier @bca) gespeichert.
Als Beispiel für die Anwendung wird im Hauptprogramm ein einzelner
Koeffizient aus dem Array entnommen und (als String !) angezeigt.
●
Diese Variante berechnet ein komplettes Array von Binomial-Koeffizienten
mit absoluter Genauigkeit, dafür jedoch deutlich langsamer als die oben
vorgestellte Version für gewöhnliche Gleitkomma-Zahlen.
Rechenzeit: (Vergleichswerte eines typischen PC):
(10|10) in 0.45ms, (50|50) in 13ms, (100|100) in 50ms, (1000|1000) in 8s,
(2000|2000) in 50s
|
Berechnung eines Arrays von Binomial-Koeffizienten mit mit
Perl
#!/usr/bin/perl
use strict;
use Math::BigInt;
my($imax,$jmax,$k,@bca);
$imax = 10;
$jmax = floor($i/2);
bca_create_big($imax,$jmax);
$bc = $bca[$i][$j];
printf("(%d|%d) = %s\n",$i,$j,$bc);
sub bca_create_big {
my($imax,$jmax)=@_;
my($i,$j,$bc);
for($i=0;$i<=$imax;$i++) {
for($j=0;$j<=$jmax;$j++) {
if(!$j) {$bc = 1;} # col 0
elsif($j>$i) {$bc = 0;} # illegal
elsif($j==1) {$bc = $i;} # col 1
elsif($j>($i/2)) {$bc = $bca[$i][$i-$j];} # sym
else {
$bc=Math::BigInt->new($bca[$i-1][$j]);
$bc->badd($bca[$i-1][$j-1]);
}
$bca[$i][$j] = $bc;
}
}
}
|
Algorithmen
Auf der Seite der 
Live-Demonstration: Klicken sie in eine Zelle: Alle Zellen, aus denen der
Algorithmus diesen Wert berechnet, werden rot unterlegt.
Der 'Pascal-Algorithmus' verwendet - im Gegensatz zur Fakultät-Funktion -
ausschließlich Additionen und wird daher normalerweise wesentlich
rascher als diese ausgeführt.
Ausgewählte Links: