Okej, det var ett tag sen vi hade några "veckans nöt". Den här veckan kör vi med "hasselnöt". Det var ett tråkigt skämt. Skit samma.

Problem:
Du behöver skapa en population till ett spel, t.ex., och för att få det verklighetstroget vill du ha en normalfördelning på t.ex. gubbarnas längder. (Och för enkelhetens skull får du själv välja om längderna får lov att vara negativa eller inte...)

Problemet är att du har en perfekt slumptalsgenerator som antingen returnerar en likformig (rektangulär-) fördelning med heltal i intervallet [0, n) (välj n själv) eller reella tal i intervallet [0, 1).

Gör en så snabb kod som möjligt för att returnera normalfördelade tal i valfritt språk, utan att använda inbyggda eller externa färdiga funktioner för det. (Du får naturligtvis använda flera vanliga slumptal för att generera ett normalfördelat.)

Har några ideer själv men det skulle vara intressant att se vilka varianter som kommer upp.

PS. Summan av två slumptal blir inte normalfördelat, utan triangulärfördelat, den går inte.

http://www.taygeta.com/random/gaussian.html

Jag kom på att det var en ganska dumt formulerad uppgift strax efter att jag hade skrivit den. Grejen är att det där ju är standardvarianten, men den blir ganska seg. Först leta efter en punkt i enhetscirkeln, sen köra en logaritm, en kvadratrot och en sinus/cosinus.

Min lösning bygger på en lookuptabell, som jag interpolerar linjärt. Problemet är att det då i princip inte spelar någon roll om man använder Box-Muller-transformationen (den i länken) eller en invers till fördelningsfunktionen.

Har sett en annan variant också, med en summa där man bör välja k=12*n^2, men mer kommer jag inte ihåg (det ligger alltså en sqrt(k/12) i den, om någon känner igen det).

Nåja, om någon har någon annan intressant lösning, kan ni ju posta den.

Den polära formen kör varken sin eller cos.

Jaja, det är ändå en hel del flyttalsoperationer. Säg, ungefär 10 mult+add för roten och 10 för logaritmen.

Om man får in det som ett heltal i [0, k*n] så kan man ju mappa det mot en lookup på [0, n] ganska enkelt, och på det sättet få en (godtyckligt) hygglig approximation. Och använder man inversa metoden så blir det bara en lookup och ett slumptal.