Hallo,
Was sind denn überhaupt die Ergebnisse zu binomial(1754,600)
http://www.wolframalpha.com/input/?i...81754%2C600%29
Mit pascalschem Dreieck oder simpler Schleife gerechnet:
Delphi-Quellcode:
program TestNueberK;
uses
sysutils;
type
Ttesttype = extended;
function binomPas(n, k: Integer): Ttesttype;
var x, y,idx,g: Integer;
s:
array[0..1]
of Ttesttype;
pas_dreieck:
array of Ttesttype;
begin
result:=0;
if n-k < k
then k := n-k;
if k=0
then
result := 1;
if k=1
then
result := n;
// Jetzt beginnst
if k>1
then
begin
//nicht unnötig lang
setlength(pas_dreieck,k+1);
//vorbelegen
for y:=0
to k
do
pas_dreieck[y] := 1;
//Berechne Pascalsches Dreieck der Höhe n-1
//Spart k-1 Additionen in der letzten Zeile
for y:= 1
to n-1
do
begin
S[0] := 1;
//:= pas_dreieck[0];
idx:=1;
g := y-1;
if g>k
then
g:= k;
for x:= 1
to g
do
begin
//Wert retten
S[idx] := pas_dreieck[x];
//Überschreiben mit der Summe der Vorgänger
pas_dreieck[x] := S[0]+S[1];
idx:=1-idx;
//FlipFlop 0,1,0,1,0,1,0..
end;
end;
//Bestimme das Ergebnis bei Höhe n
result := pas_dreieck[k]+pas_dreieck[k-1];
end;
end;
function Binom(n,k:integer): Ttesttype;
var
i : integer;
begin
{triviales abfangen fehlt}
//k mit n-k tauschen, falls es sich lohnt
i := n-k;
If k>i
then
k := i;
result := 1;
For i := 1
to k
do
begin
result := (n*result) / i;
// Ist immer ohne Rest
dec(n);
end;
end;
var
T1,T0:tdatetime;
i : integer;
begin
T0 := time;
for i := 1
to 10
do
binomPas(1754,600);
T1 := time;
writeln('
Zeit insgesamt',FormatDateTime('
hh:mm:ss.zzz ',T1-t0));
writeln('
Zeit pro Runde ',86400*(T1-t0) / 10);
writeln(binomPas(1754,600));
Writeln;
T0 := time;
for i := 1
to 10000
do
binom(1754,600);
T1 := time;
writeln('
Zeit insgesamt',FormatDateTime('
hh:mm:ss.zzz ',T1-t0));
writeln('
Zeit pro Runde ',86400*(T1-t0) / 10000);
writeln(binom(1754,600));
//EDIT faelschlicherweise binomPas vorher, aber ist es ist tatsächlich das gleiche Ergebnis
Writeln
end.
Code:
Ergibt für AMD X2 2300 Mhz:
Zeit insgesamt 00:00:00.391
Zeit pro Runde 3.90999999996566E-002
4.5114986794473264E+0487
Zeit insgesamt 00:00:00.188
Zeit pro Runde 1.88000000001232E-005
4.5114986794473264E+0487
Man sieht, das Pascal'sche Dreieck ist hierbei mehr als 2000-fach langsamer.
Die Abweichung in der letzten Stelle, gegenüber der exakten Zahl, könnte auch durchs runden kommen.
Aber was macht es für einen Sinn die ersten 15 Stellen von 487 zu haben ?
Gruß Horst
P.S.:
Hagen (alias negaH) Redmann hatte doch auch mal was vor langer Zeit dazu komponiert, auch mit direktem kürzen der großen Zahlen.
Ich glaube hat hat von jedem Faktor die Primzahlzerlegung genutzt, das sind ja nur die Primzahlen von 2..n.
Beim Faktor im Zähler nur die Anzahl der jeweiligen Primzahlfaktoren erhöhen, beim Divisor entsprechend erniedriegen, irgendwie so.