![]() |
Re: n über k - berechnen!?
ich hab jetzt mal noch abschließend einen Speedtest über alle hier vorgestellten Funktionen gemacht. Als Basiswerte gelten für n=1754 und für k=600. Der Test wurde auf einer VM gemacht. Prozessor des Hosts: 1x AMD Turion x64 (2,0 GHz). Delphi 7
Es kamen folgende Ergebnisse zu stande:
Code:
Ich weiß nicht woran das liegt, aber die Funktionen, die in ASM bereitgestellt wurden, scheinen alle weit langsamer zu sein. Die Zahlen scheinen ein anderes Bild zu zeigen, aber die Anzahl der Testläufe ist unterschiedlich (100, 1.000 und 10.000).
Mit Optimierung (gemittelt aus 5 Tests)
N ueber K-Funktion Anzahl aus Post Dauer [Ticks] Dauer [ms] N_K_1: 10.000; #25 2312382 646 N_K_2: 100; #33 1953869 545,84 N_K_3: 10.000; #36 1330019 371,56 N_K_4: 1.000; #37 8680559 2425,04
Code:
Im Test ohne Optimierung wurden die Funktion 1 langsamer, die Funktionen 2 und 4 blieben etwa gleich schnell und die Funktion 3 wurde noch etwas schneller ( :?: ). Wahrscheinlich hat hier die Optimierung versagt.
Ohne Optimierung (gemittelt aus 4 Tests)
N ueber K-Funktion Anzahl aus Post Dauer [Ticks] Dauer [ms] N_K_1: 10.000; #25 2667633 745,25 N_K_2: 100; #33 1944674 543,28 N_K_3: 10.000; #36 1111184 310,43 N_K_4: 1.000; #37 8732180 2439,47 Bernhard PS: Die Formatierung ist etwas misslungen |
Re: n über k - berechnen!?
... wir bleiben 'dran
|
Re: n über k - berechnen!?
Hallo,
n über k ist immer ohne Rest direkt kürzbar bei der Berechnung,wenn man entsprechend k ändert, wenn k > n/2 ist. Denn erst teilt man durch einen Faktor / 1 dann durch 2 , dabei hat aber im Zähler zwei aufeinanderfolgende Zahlen gehabt => eine ist durch 2 teilbar, mit 3 das selbe... Genau wie bei Wikipedia beschrieben: ![]() aha, da habe N über k , unten als binomial bezeichnet, wiedergefunden mit Pascal'schem Dreieck in einer Zeile der Länge n. Aber auch da ist die Grenze für n über k bei 66. Wie man bei der Berechnung der Binomialverteilung sieht, kann man aber n= 1000000 und p = 0.05 noch recht genau berechnen indem man logarithmiert, was 1 und 1 Mio näher zusammen bringt, und die Multiplikationen dadurch zu Additionen macht. Das geht sicher auch für n über k Gruß Horst Edit: Ich habe mal mit Pascalschem Dreieck,Statt Int64 mit extended und logarithmiert extended gerechnet: Bei 66 über 27 ist die Abweicung schon ;-) 40 Bei 66 ueber 33 extended bei 40 und logarithmisch gerechnet dann schon 140
Code:
66 ueber 24
Dreieck 624439409096903400 logarithmisch 624439409096903400 extended 624439409096903400 66 ueber 27 Dreieck 2450791253481179840 logarithmisch 2450791253481179800 extended 2450791253481179800 66 ueber 30 Dreieck 5516694892996182896 logarithmisch 5516694892996182900 extended 5516694892996182900 66 ueber 33 Dreieck 7219428434016265740 logarithmisch 7219428434016265600 extended 7219428434016265700 |
Re: n über k - berechnen!?
Zitat:
Wenn ich deine Funktion NueberK aus #36 mit den Werten n=1754 und k=600 aufrufe dann wirft die eine Exception. Insofern bin ich nicht in der Lage deine Messergebnisse qualifiziert zu kommentieren. Die Exception wird in der Funktion Fakultaet2 ausgelöst, wobei mir nicht klar ist, was diese Funktion überhaupt machen soll. Die Funktion hat die Parameter start und ende und es gibt genau 3 mögliche Resultate: 1) Wenn ende > start, dann wirft sie eine Exception (dabei sollte das der Normalfall sein) 2) Wenn ende < start, dann ist das Ergebnis 1 3) Wenn ende = start, dann ist das Ergebnis = start Was soll das ?
Delphi-Quellcode:
function fakultaet2(start, ende: integer): extended;
var i: integer; begin if ende > start then raise EMathError.Create('Start kleiner als Ende'); Result := 1; for i := start to ende do begin Result := Result * i; end; end; Zur Performance der Routinen #33 und #37 sei gesagt, daß die nicht auf Performance optimiert sind, sondern auf Erhöhung des Rechenbereiches. |
Re: n über k - berechnen!?
Hallo,
Was sind denn überhaupt die Ergebnisse zu binomial(1754,600) ![]() 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:
Man sieht, das Pascal'sche Dreieck ist hierbei mehr als 2000-fach langsamer.
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 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. |
Re: n über k - berechnen!?
Habe spaßenshalber mal den Windows-Rechner getestet
50.000! = 3,3473205095971448369154760940715e+213236 er kann aber noch höher ... Respekt! |
Re: n über k - berechnen!?
Stimmt das Ergebnis denn?
Sherlock |
Re: n über k - berechnen!?
Zitat:
![]() |
Re: n über k - berechnen!?
@Sherlock:
Das würde ich nicht unterschreiben. Vielleicht hat ja jemand ein professionelles Matheproggi und vergleicht ... |
Re: n über k - berechnen!?
@Wolfgang: Das Ergebnis kann nur bis zu einer gewissen Genauigkeit stimmen, es sei denn der Windows TR implementiert eine BigNum-Technik. Das ist auch der Grund, warum so hohe Fakultäten mit den nativen Datentypen - auch wenn zumindest ein Ergbnis kommt - es meist total unbrauchbar, weil sehr ungenau ist.
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 13:15 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz