Interessante (?) Frage Kombinatorik

[Michael II]

Zitat von Sinspin:

Bin gerade am überlegen was eine GraKa von der Arbeit halten würde.

Eine Grafikkarte hat an (wie vorliegend) O(4^n) Problemen keine Freude. Spannend für GPU Berechnungen sind Algorithmen mit linearer, linear logarithmischer, allenfalls polynomialer Komplexität.

Im 1000Euro Bereich hat eine NVIDIA RTX3080 10'240 CUDA Kerne; Wenn du alle rechnen lässt, dann kannst du von Uwes weiter oben berechneten 10^136 Jahren 5 vom Exponenten nehmen .

Nebenbei: In #18 sollte stehen: n! = 10^g ≈ 10^(0,f)*10^m, Beispiel 4! = 10^log(4!) = 10^log(1*2*3*4) = 10^(log(1)+log(2)+log(3)+log(4)). Die Summe s der logs kannst du auch für sehr grosse n noch mit einem Taschenrechner berechnen. Hier s=1.38021... - 10^1.38021... = 10^0.38021*10^1 = 2.4*10^1.
Ohne log rechnen: Bei n tief d = n!/(d!*(n-d)!) rechnest du die drei Fakultäten nicht einzeln, du kannst den Bruch kürzen und vermeidest so u.U. Overflows, wenn du mit grossen Werten rechnest. Beispiel 1024 tief 2 = 1024!/(2!*1022!) = 1024*1023/2