n über k - berechnen!?

[rollstuhlfahrer]

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:

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

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).

Code:

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

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.

Bernhard

PS: Die Formatierung ist etwas misslungen

[Wolfgang Mix]

... wir bleiben 'dran

[Horst_]

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:
http://www.delphi-forum.de/viewtopic.php?t=81018
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

[Amateurprofi]

Zitat:

Zitat von rollstuhlfahrer

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

Hallo Bernhard,
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.

[Horst_]

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.

[Wolfgang Mix]

Habe spaßenshalber mal den Windows-Rechner getestet
50.000! = 3,3473205095971448369154760940715e+213236
er kann aber noch höher ...

Respekt!

[Sherlock]

Stimmt das Ergebnis denn?

Sherlock

[gammatester]

Zitat:

Zitat von Horst_

...
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.

Wen's interessiert: Hier gibt's mehr Infos zu schnellen Binomialkoeffizienten incl. Java- oder C#-Implementationen.

[Wolfgang Mix]

@Sherlock:
Das würde ich nicht unterschreiben.
Vielleicht hat ja jemand ein professionelles
Matheproggi und vergleicht ...

[Medium]

@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.