Interessante (?) Frage Kombinatorik

[Uwe Raabe]

Bei N = 4 erzeugt mein Algorithmus 35 Ausgaben, bei N = 10 sind es schon 92378, bei N = 16 sind es 300540195. Die Zahl entspricht dem Binomialkoeffizient (n über k) mit n = 2*N-1 und k = N-1. Jedes N + 1 erzeugt knapp 4x so viele Ausgaben wie N. Damit kannst du in etwa abschätzen, wie lange es bei N = 256 wohl dauern wird. (Hinweis: Die Zahl ist ca. 4,7e+152. Dauert eine Iteration lediglich eine Nanosekunde, dann sind das ca. 4,7e+143 Sekunden oder ca. 1,5e+136 Jahre. Zum Vergleich: Das Universum ist heute ca. 1,4e+10 Jahre alt.)

Auch eine Parallelisierung würde nur wenig bringen, denn wenn ich das ohne Overhead auf 4 Kerne verteilen könnte, würde das immer noch solange dauern, als würde ich statt N = 256 nur N = 255 vorgeben. Bei 16 Cores wäre es dann so schnell wie N = 254.