n über k - berechnen!?

[gammatester]

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

Das kommt darauf an, wofür man das Ergebnis verwenden will. Normalerweise braucht niemand 50000! mit ca 213000 Stellen. Und die Windowsrecher-Genauigkeit von ca 1e-32 ist sehr hoch verglichen mit double (ca 1e-17) oder extendend (ca 1e-19). In diesen Regionen ist eigentlich nur n! = Gamma(n+1) oder sogar nur lngamma(n+1) von Interesse; es sei denn, man will die Werte modulo irgendendeiner Zahl m > n, aber dann macht man besser die gesamte Rechnung modulo m.

PS: Wolfram Alpha: 3.347320509597144836915476094071486477912773223810 4... x 10^213236

[rollstuhlfahrer]

Zitat von Amateurprofi:

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 ?

Hallo Amatuerprofi,

hier handelt es sich ja leider auch noch um meinen eigenen Code, den ich allerdings mal schnell heruntergetippt habe. Bei den Tests habe ich die Prüfung auf "ende kleiner start" allerdings weggelassen. Es ist mir desshalb nicht aufgefallen. Ansonsten hätte ich auch bemerkt, dass da ne Exception kommt, wo keine kommen sollte, also in dem Sinn ist mir einfach ein logischer Fehler unterlaufen, den ich hätte vermeiden können.

Bernhard

[Amateurprofi]

Zitat von Wolfgang Mix:

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

Zitat von Sherlock:

Stimmt das Ergebnis denn?
Sherlock

Zitat von Wolfgang Mix:

@Sherlock:
Das würde ich nicht unterschreiben.

Aber ich ! (Das etwas genauere Ergebnis siehe weiter unten)

@Wolfgang:
Bei mir braucht der Windows-Rechner ca. 58 s, um 100000! zu berechnen. Mein (selbstgeschriebenes) Programm braucht knapp 2 s, allerdings rechnet es mit einer Genauigkeit von > 9600 Dezimalstellen und nicht nur mit 32.
Wenn ich die Genauigkeit auf ca. 39 Dezimalstellen einstelle dann steht das Ergebnis (subjektiv empfunden) ohne Verzögerung da.
Und um 10000000! zu berechnen braucht es dann < 1 s.
(10000000! ergibt ca. 1.2024234005159034561401534879443088711e+65657059) .
Teste doch mal, was der Windows-Rechner da macht. Schlapp macht er. 0 (null) Respekt!

Und was Hagens DECMath angeht, das Ding ist noch deutlich schneller. Und davor habe ich Respekt.

Hier 50000! mit etwas größerer Genauigkeit
3.347320509597144836915476094071486477912773223810 4548077301003219901680221
44365641697381231071916930879848043819020829989361 6384743066693742630572845
36378403832575628212335998726824407823597235604085 3854441373383753568565536
37116832740516607615516592140615607546129420179056 7479665498629242220022541
55351071815980161547645181061667497021799653747497 2541139338191638823500630
30764425687485727139465108190987490964348626858922 9807870031031008962861154
55397991161294065232739697149721103126114286073379 3509687837355811830609551
72890660383359253285163596173088527981195739949529 9450306354442478492641028
99006955963488352990055767655092917547592078804480 7622562415165130459046318
06851740676636001232955645406572422517547342818312 1029195715593787423641117
19451383859303800641313297631250898062395386984535 2836267459097392518734779
17386980548744182185648438503491964333743846071476 7001812780976866957155372
29628555028927220678139443841801928426215041072328 3833180314781970267867953
72029783990819120751438532031598735080259871533762 5358079963009440543477488
06234215447644741193387195605032356683069084291857 2341005321690441862428022
96921090618036854824667445724348826781455738959409 8679827750942585126459140
07833846753111628263754204800076909063514694266744 4841487805855830330025518
31254381959117405503220294415503007259939726738709 1090410509048935575856186
58401034313561349891577719514041343212219960564988 3727164515471756877418149
80812938062155738292992590160055537706172186808711 2516881136375809745667071
22942665347059240728748506701899063402337572640948 7683079892949781196018233
25599564846376697865287577921417929890190242903637 9098118717809157838949630
03880471121224233276543404046470240153283309003011 4837188050603998942611255
19176176026908189602575106421797616404727080478388 8429423075248611387991185
23126008705707117507249115073708165959364214054425 2179306969287380725056827
13425329656342471793529162352487106725091607448023 1341152017296504390921345
01606256319198329019952818880122308335154261074887 4511031648971929695646680
45075924372382592052548806644300315687507594904157 0874163813140312683487544
11426805416041631293774798419066052624397997306343 5611502591811288360112144
67181593960929122537991065158602184653184229976859 4001415779797353877639377
65931423775446857926737306782649106624524583064869 4658984214237406617175798
51439997673547477354702805319958975913055970122794 2085031348719992021803884
83975427234993927208131924680871512052721642052432 1314349116960268297877078
62368133064621851988313729306398789159925820921881 3095397525301970746047734
05709109097115983486596348376352381988248270014544 5889844023028723789545800
66488888620018023178602568754313667241385446018431 5351056508185003278679424
24025556556905533563330241447160434066025298051837 9980059275135742809559837
49341677704388852241906386305338118462810154859014 9538058307494475969657290
20915249096727737118764981555927585780938461626404 3358082536889785449853024
59523988883299345755780679044533322719307158020094 6189254503393397244035603
31866534051338367285514541589516281764158596826943 1814636358041252624584001
52284473011648133926579859349020706671209082437495 0750660708387827604509116
84240988342394805121417205741456815630812813879917 6916875880966168904504528
44961253985918031959165515767879873333624583333155 5464889127794987238171845
18246447129362073102190885064857929140797608374973 0914500672402874842123174
45336138460196179458852690642454886615270267016657 8294286932902889637245961
65479235247169984334144257296070261026669170404650 4565096781201921689522356
42439238423338762176776520696727158454262637455269 0432433987554961457515592
45686405264688547510050099492199175883797335947301 8314657440314083708331178
24658350103885828420103283014845638067930284689432 0372870400889008023065240
19999369591677464183305846021100700168754151704053 0759046723463540044394434
10255024438503902789367204461338442560555291317861 7200831852872047626774463
22978640983891458937258862323212909464309204908731 5704022170861491912272185
73172747931619086198170420514136871333683667035745 3609922877957415588945513
92999325441985356344116294391588571423617024082354 3022103566866399133489101
28275396120567620967013847802925593213486807617234 8471480235727782113262340
75973016104909913784842579889957807328876429585227 5262070163351641302243679
86758151263471969750400777169861384999364347001247 6690621432885398373304964
45127168823399631700094816780163389342942559122454 7789285583859853093670397
53221633592852675307269449760622693457304018952785 8800089574556701262222215
75944769082778143578956185111951681431210329548226 5498840121930821543729814
43455377500487341095644578008575316628572521796105 0886744793330875523618441
65491018319093706803539303348052647794955038081013 4243932119654813832490448
21472093790851775887635781170072182817499630751313 8766631171305200004238250
79770847682191963262426711243141177550503739530283 8782904608458558100732560
73469944394216684470158616948244426068010983996705 9482733542293874822127261
78521698810948877137032577881223928392519396774347 1331107975777545897629208
57089605854672791821138940405476196036461811511836 2476888617140685536209069
23405570580946888330284025983147090822244633559943 3624852366351023176895125
47161115440520822243668106479223776696856902543531 3501701661013097633311258
71823658163480203408355307989009249141638417521371 6007693590010041375234969
96466298444003110363735327851156475895832138965291 7018953639156254793271854
49376364864819744091405462267300714583030731778612 3400278117264794761103274
67621512965663622199269081870743522553551038308993 3296681735922170634807913
11784720493740330822203552365966975182278881810439 5010788805436309826735476
58466015970197695928368355311401118406833311690617 9535341922509705166700874
82640151129699208898425848286531550314900476014934 2565916862475240918672586
33668922294050434001688330425219492792764235150952 9297186363908009446867750
19014916896076515727445760682111218876527065920779 2647982850616088549748959
49949012742163808146156372406607407673968721921162 3177338007270899152885148
93100423127581051244740620135112723654962653344175 7508697437550593720787776
70842401741570383290932849189484458672586215495721 2861659562414377752729246
89614955324522408535762435822493231264052616461449 5709988019971547058602019
01223445494352423312024073938841660500269781064193 2319630648500496742385871
24324879900203659062679480765982210375552331814957 1177884976710368274760582
42510840639068053305978464713186330622784227797362 0714788250637123454400331
68113502776533875271632504786321575314816937758377 2065412760231637138537024
88785253850215710015994405928437455794950429681435 5119544010623556778850344
96832972982119216558099206309717133131574662146534 1623840638865957704904888
82294288288882311205661492742530221303236342673202 9061249102366740097662363
55063068816984649682564814713058888666039463686169 7481815484689136715237657
86889359321639287186173718813583855556344772367028 8989436411228630055442274
34253695225770403881133588264803030357157743504838 3566036250676055902953174
46179359830547894931863833068843995570589864158284 9317543477341113996373196
58379986863948488361324638169666887904680452700214 1572916259004771364212720
45186240328776788809947490899893416829046880377093 2292645508122577535101756
89401215345275335520954289754301647355785956496286 8798201069371192874491486
78786860037483779629500140846368755789364581257648 1077840105218070923499850
81455555475538476846344999254760717276217794138331 8129330012767754997069848
65072975718791596638204814836928188895807392661067 8714181320893272928339297
84078247774051595064180341045217677921996252605027 4742250165997647163883075
46477789229543317737279060129922161579858330354605 4226650544751564734436149
36428564073362273934585496845727858756394017445003 2402726042597397402600251
25320173747349747416225974407498254405160695457325 0562580301274043054086840
28870884988892616217785373211875166276312180989989 2439506304854674049094097
84137089360360134212964063982046658667691126667662 6970100182214899765055286
75916206357363305117081361764346263150305929703560 8789131067555773062918625
80919258715307500739987890679574965050688576877640 7984386387792883716099318
23564814006012694746741793692653512894291729973455 4031402189989660708331430
20753581642006968436115566244700140481708269846727 8873565319279707889045454
49110610381753266858493325318788621807737411285827 5221175121556281172167605
63925398161439353286176779265153466312876968705445 0149100229512424818801074
71997067856069766857757722859917834696207712980550 8382637013542220153675027
11554419395495485147446523912822390135647626596014 7686754443838624187133848
56503344773782728542222072839110507519942038634711 2008247746206173731155584
98445185516734128952566126905136958171696838850437 6423692613835914575180271
02945097923949366358690715272823805120585606278939 4935393792590771333032545
96648042389568496210664807588802833936940883977352 9500980913174802880292672
07838804609838304062201342730102751307551211828508 3501984438199445951899728
81184805086036136842499631396829626620703417531392 9211857046243978042961410
06298664138907483976763351455184098930911115813994 8207144690299485173772398
99341274260829037772860524194207363762089264188191 2634972033319416956927731
02097278624817490847013153159928416792176567889490 3166173335374076352819163
63809779691724180028279596097726150146235895125436 4638834496505708854392506
44516444549487746560429692175189797891338351233889 6955421815470512486009678
35252511976781382277332741572889031983726296368310 6510080636677547997308945
55963222916457380446224220229777281775606537322130 4036408182850772695937282
80846431236621000312926242804673510386183765936766 0750275639561022622054150
9046492689832901546308154578799079e+213236

[Horst_]

Hallo,

Die von gammatester genannte Seite
http://www.luschny.de/math/factorial...lFunctions.htm
ist ja überaus passend und sehr einfallsreich in der Anzahl der Algorithmen.
Witzig, dass das Pascalsche Dreieck in einer Zeile zu einem Moessner Algorithmus wird.
Es bleibt immer noch die Frage , wozu diese Genauigkeit.
Selbst Annäherungen http://www.luschny.de/math/factorial...mpleCases.html kommen schnell auf hohe Genauigkeiten.
http://www.luschny.de/math/factorial/approx/plo.gif

Gruß Horst

[Amateurprofi]

Zitat von rollstuhlfahrer:

Zitat von Amateurprofi:

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 ?

Hallo Amatuerprofi,

hier handelt es sich ja leider auch noch um meinen eigenen Code, den ich allerdings mal schnell heruntergetippt habe. Bei den Tests habe ich die Prüfung auf "ende kleiner start" allerdings weggelassen. Es ist mir desshalb nicht aufgefallen. Ansonsten hätte ich auch bemerkt, dass da ne Exception kommt, wo keine kommen sollte, also in dem Sinn ist mir einfach ein logischer Fehler unterlaufen, den ich hätte vermeiden können.

Bernhard

Hallo Bernhard,
Tja, dann hab ich im Code aus #36 auch mal die Prüfung auf "ende kleiner start" weggelassen.
Dann ergibt NueberK(49,6) = 83902896, und als fleißige Lottospieler wissen wir doch, daß 49 über 6 = 13983816 ergibt.
Dein Programm errechnet das Produkt aus 6*7*8*...*49 und teilt das dann durch 43!.
Sorry, aber mir ist immer noch nicht klar was das soll.
Du sagtest "Ich hab in den einfachen Code das mit dem Kürzen mal integriert. Die Zwischenergebnisse sollten hier wesentlich kleiner sein.".
Wenn man 49 über 6 konventionell rechnet dann so (49*48*47*46*45*44) / 6!.
Da ist das größte Zwischenergebnis 10068347520. Bei dir ist das kleinste Zwischenergebnis 6.0415E+0052.
Was hat denn das mit Kürzen zu tun ? Das ist doch genau das Gegenteil. Verstehe ich alles nicht.

[rollstuhlfahrer]

So, nun nochmal. Ich scheine mich wohl nicht nur während irgendwelchen Mathearbeiten grundsätzlich irgendwo zu verrechnen. Scheint wohl irgendwo erblich veranlagt zu sein. Zu dem viel zu hohen Zwischenergebnis: falsch Optimiert. Ich hab das falsche gekürzt, weil ich dachte, dass sich das andere irgendwie anders errechnet. War aber nicht so.
Zu dem total falschen Ergebnis: 7! / 6! = 7 und nicht 42, was meine Routine fakultaet2 errechnet hat.

Delphi-Quellcode:

function fakultaet2(start, ende: integer): extended;
var
  i: integer;
begin
  Result := start + 1;
  for i := (start + 2) to ende do
  begin
    Result := Result * i;
  end;
end;

function fakultaet(N: integer): Extended;
var  i: Integer;
begin
  Result := 1;
  for i := 1 to trunc(N) do
    Result := Result * i
end;

function nueberk(n, k: integer): Extended;
begin
  // alte Funktion
  Result := fakultaet(n) / (fakultaet(n - k) * fakultaet(k));
  // die jetzt hoffentlich richtige
  Result := fakultaet2(n - k, n) / (fakultaet(k));
end;

Zu dem "was soll das?": ja, errare humanus est. Ich habe insgesamt jetzt 3 Fehler gemacht. Wenn noch einer einen findet, sind es mehr. Fehler 1: Größer/Kleiner habe ich schon in der Grundschule mir nur per Merkregel merken können. In der 6. Klasse habe ich eine andere Merkregel gelernt, die ich jetzt immernoch verwende. Fehler 2 war die falsche Fakultät und Fehler 3 war das Nicht-Nachrechnen des Ergebnisses.
Das zu meinen Fehlern. Wie viele machst du?

Bernhard

[Wolfgang Mix]

Eselsbrücke:

Aus < kann man ein k basteln

[rollstuhlfahrer]

ja und der Pfeil zeigt auf das kleinere. Ich weiß-

[Amateurprofi]

Zitat von rollstuhlfahrer:

Zu dem "was soll das?": ja, errare humanus est. Ich habe insgesamt jetzt 3 Fehler gemacht. Wenn noch einer einen findet, sind es mehr. Fehler 1: Größer/Kleiner habe ich schon in der Grundschule mir nur per Merkregel merken können. In der 6. Klasse habe ich eine andere Merkregel gelernt, die ich jetzt immernoch verwende. Fehler 2 war die falsche Fakultät und Fehler 3 war das Nicht-Nachrechnen des Ergebnisses.
Das zu meinen Fehlern. Wie viele machst du?
Bernhard

Hallo Bernhard,
Zunächst zu deiner abschließenden Frage:
Ich weiß nicht, wie viele Fehler ich mache, weil ich wenig Hinweise auf Fehler erhalte. Aber es wäre nett, wenn du meine Beiträge einmal kritisch anschaust und darüber berichtest. Ich freue mich, wenn man mir meine Fehler aufzeigt, denn das gibt mir die Möglichkeit, daraus zu lernen.

Dann zu deinem Vorschlag, wie N über K gerechnet werden kann:
Was mich irritierte war die Einleitung zu deinem #36 in der du schriebst, du hättest "das mit dem Kürzen mal integriert" und die Erkenntnis, daß in der gezeigten Routine überhaupt nichts gekürzt wird. Unter "Kürzen" versteht man die Streichung gemeinsamer Faktoren in Nenner und Zähler, so daß ganz platt gesagt die Zahlen kleiner werden, der Wert des Bruches aber unverändert bleibt.
Zum Beispiel deine (jetzige) Routine rechnet 49 über 6 so : (49*48*47*46*45*44) / (1*2*3*4*5*6). Da ist nichts gekürzt. Meine in #37 gezeigte Routine rechnet 49 über 6 so : 49*47*46*3*44. Die 48 wurde gegen 6,4 und 2 gekürzt, und 45 gegen 3 und 5.
Das kostet zwar einiges an Rechenzeit, erhöht aber den Rechenbereich.
Was ich weiterhin an deiner Routine nicht gut finde, ist, daß Sonderfälle und fehlerhafte Parameter nicht abgefangen werden.
Beispiele:
N über 0 (null) zum Beispiel ergibt 0, deine Routine liefert N+1.
Negatives N und/oder negatives K sollten Fehlermeldungen ergeben, deine Routine liefert Resultate, die man durchaus für richtig halten könnte.

Mein Vorschlag für eine Verbesserung deines Codes wäre
(Achtung : nicht geprüft - nur so hingeschrieben)

Delphi-Quellcode:

FUNCTION NueberK(n,k:integer):extended;
FUNCTION Mul(first,last:integer):extended;
var i:integer;
begin
   result:=last;
   for i:=last-1 downto first do result:=result*i;
end;
begin
   if (n<0) or (k<0) then result:=NaN // oder raise ....
      else if (k>n) then result:=0
         else if (k=n) or (k=0) then result:=1
            else result:=Mul(n-k+1,n)/Mul(2,k);
end;

Zu "errare humanus est". Tja, irren ist menschlich ... aber hieß das nicht "errare humanum est"?

An anderer Stelle schrieb ich kürzlich : "Es wäre schön, wenn alle, die so oft "aus der Hüfte geschossene" Kommentare abgeben, vorher prüfen, ob das, was sie schreiben wollen auch korrekt ist."
Schön wäre es auch, wenn User, die hier einen Code posten, vorher prüfen, ob der auch korrekt arbeitet, oder zumindest (wie man es ja gelegentlich sieht) einen klaren Hinweis geben, daß der Code ungeprüft ist.

[negaH]

Zitat:

(49*48*47*46*45*44) / (1*2*3*4*5*6)

Und das lässt sich nach A.Schönhage noch weiter kürzen.


49*48*47*46*45*44
----------------- =
1*2*3*4*5*6


7*7 * 2*2*2*2*3 * 47 * 2*23 * 2*2*11
------------------------------------ =
2*3*2*2*5*2*3

2^7 * 3^1 * 7^2 * 11 * 47
------------------------- =
2^4 * 3^2 * 5^1

nun Exponenten kürzen, also 2^7 / 2^4 = 2^(7-4) = 2^3

2^3 * 7^2 * 11^1 * 47^1
----------------------- =
3^1 * 5^1

bei der Berechnung dieses Bruches und der Potenzen kann man nun ebenfalls zwei Tricks anwenden:

1.) Potenzen ausmultiplizieren mit Hilfe der "Binary Powering" Methode.
Zb. 2^3 ist 2^011b wenn man die Potenz von 3 in binär darstellt -> 2^3 -> 2^2 * 2^1. 2^2 ist 2 zum Quadrat und man kann statt einfacher Multiplikation mit einem schnelleren Quadrierungs Algortihmus arbeiten. Die Quadrierung einer großen Zahl ist 1.5 mal schneller durchfüphrbar als die entsprechene Multipikatation.
Man nimmt nun die Potenz 3 binär -> 11b. Geht die Bits in einer Schleife von MSB-1 zu LSB durch und quadriert in jedem Schritt das Resultat. Wenn ein Bit im Exponenten gesetzt ist multipliziert man das Ergebnis noch mit der Basis.

2.) "Binary Splitting" dabei hat man eine ganze Liste von Zwischenprodukten die man ausmultiplizieren möchte. Zb. 2*3*4*5. Man teilt diese Liste in der Hälfte und rechnet rekursiv die Linke und Rechte Hälfte aus. Also (2*3) * (4*5). So stellt man sicher das die Zischenprodukte während der Multiplikationen immer möglichst gleich groß sind und somit deie höchtste Performance der verwendeten Multiplikationsalgorithmen erreicht.

Alle diese Tricks verwendet mein DECMath. Mal hier rein lesen http://www.delphipraxis.net/internal...orial&start=20
Das Binomial ist nichts anderes als die Division zweier Fakultäten. Also zerlegt man beide Fakultäten in deren Primzahlpotenzen und subtrahiert nun die Exponenten mit gleicher Basis voneinander. Übrig bleibt die Potenzschreibweise des gesuchten Binomials.


Gruß Hagen