Approximationer av pi

• Monte Carlo-metoder är en klass av metoder där man använder slumptal för att approximera lösningen till vissa beräkningsproblem, t.ex. inom statistisk mekanik. I följande uppgift kommer du att använda en primitiv Monte Carlo-metod för att approximera en area och på detta vis beräkna en approximation av talet pi.

  Tänk dig att du kastar pil mot en cirkulär piltavla (radie en halv längdenhet), uppsatt på en kvadratisk skiva med sidan 1 längdenhet (det gröna området, utanför piltavlan, i bilden nedan). Antag att pilen träffar piltavla eller skiva (om vi missar piltavlan) i punkten (x, y), som är två slumptal. Om vi kastar många pilar så kommer andelen kastade pilar som träffar piltavlan dividerat med totala antalet pilar att approixmera pi / 4 (varför?).

  

  Skriv ett program som använder denna idé för att approximera pi. Approximationen och felet (avvikelsen från pi) skall skrivas ut.

  En nackdel med Monte Carlo-metoder är den långsamma konvergensen, så du får utföra många pilkast, åtminstone en miljon, för att få en hyfsad approximation av pi.

• Nu till ett annat sätt att approximera pi. 355 / 113 är en rätt bra (och mycket gammal) approximation av pi. Låt p och q vara positiva heltal. Skriv ett program för att hitta det minsta värdet på q (och tillhörande p) som uppfyller villkoret | p / q - pi | < | 355 / 113 - pi | dvs hitta den första rationella approximationen, av pi, som är bättre än 355 / 113. Observera att q står i nämnaren och inte i täljaren.

  Ledning: några av följande funktioner kan (beroende på hur man löser problemet) vara användbara, pi, abs, ceil, floor, round.