Nauwkeuriger berekenen java.

[Flisk]

Ik heb een programma geschreven dat pi benaderd. Het is echter slechts nauwkeurig tot op 7 cijfers na de komma:

Code: Selecteer alles

import java.io.*;

public class BerekenPi {

static int n;

public static void main(String[] args) throws IOException{

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

n=Integer.parseInt(br.readLine());

benaderPi(n);
	}

public static void benaderPi(int n){

double segment=Math.sqrt(3)/2;

int i=0;

while(i<n){

System.out.print(segment*3*Math.pow(2,i)+", ");

if(4*((i+1)/4)==i+1)System.out.print('\n');

segment=Math.sqrt((1-Math.sqrt(1-segment*segment))/2);

i++;

}

System.out.print(segment*3*Math.pow(2,n));
	}
}

De input n>0 bepaald hoeveel keer de lus in de benaderPi methode doorlopen wordt. Vanaf je n groter als 13 invoert verbetert het resultaat niet meer. Vanaf n=17 wordt het resultaat zelfs slechter.

Voorbeeld van output n=30:

Code: Selecteer alles

2.598076211353316, 2.9999999999999996, 3.1058285412302498, 3.132628613281237, 
3.139350203046872, 3.14103195089053, 3.1414524722853443, 3.141557607911622, 
3.141583892148936, 3.1415904632367617, 3.1415921060430483, 3.1415925165881546, 
3.1415926186407894, 3.1415926453212157, 3.1415926453212157, 3.1415926453212157, 
3.1415926453212157, 3.141593669849427, 3.1415923038117377, 3.1416086962248038, 
3.1415868396550413, 3.1416742650217575, 3.1416742650217575, 3.1430727401700396, 
3.1598061649411346, 3.181980515339464, 3.3541019662496847, 4.242640687119286, 
6.0, 0.0, 0.0

Ik denk dat dit te maken heeft met afrondingsfouten van de methode Math.sqrt(double a). Heeft er iemand een idee hoe je ervoor kan zorgen dat die fout kleiner wordt?

[Math-E-Mad-X]

Ik weet niet precies hoe het zit, maar ik denk dat het eerder aan de eindige precisie van het type double ligt. Het is immers theoretisch gezien onmogelijk om een oneindige precisie te bereiken met een eindig aantal bits. Het lijkt me dat Math.sqrt() zodanig geïmplementeerd is dat ze de maximaal haalbare precisie geeft.
 
De enige oplossing is dus om een nieuwe implementatie te schrijven die geen gebruikt maakt van doubles, maar van objecten van een andere klasse.
 
bijvoorbeeld: http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html

[Flisk]

De klasse BigDecimal ziet er inderdaad veelbelovend uit. Probleem is wel dat die geen methode voor worteltrekking heeft. In dat geval zal ik dus zelf een sqrt methode moeten schrijven. Ik heb eens gezocht op stackoverflow.com, dus nieuwe methode/overnemen schrijven zal waarschijnlijk de enige optie zijn.

 

Het is immers theoretisch gezien onmogelijk om een oneindige precisie te bereiken met een eindig aantal bits. 

Uiteraard, maar 7 cijfers na de komma is wel heel erg zielig  . Nu ja, het algoritme is niet echt ideaal

[aadkr]

Flisk, ik kan je helaas niet helpen, omdat ik totaal geen verstand heb van java als programmeertaal.
maar  wil je het getal pi benaderen m.b.v. reeksontwikkeling, en zo ja welke reeksontwikkeling heb je gebruikt?

[Math-E-Mad-X]

Uiteraard, maar 7 cijfers na de komma is wel heel erg zielig  .

 
Ja, als het maar 7 cijfers zijn dan kun je waarschijnlijk beter eerst proberen je eigen algoritme te verbeteren.
Zou je de benaderings formule die je gebruikt hier in latex kunnen zetten? Dat is wat makkelijker te lezen dan code.

[Math-E-Mad-X]

Het zit em waarschijnlijk in het feit dat je een onnauwkeurig getal steeds met zichzelf vermenigvuldigt, en daar neem je dan weer de wortel van en dat herhaal je een heleboel keer. Bij elke berekening wordt het resultaat steeds iets onnauwkeuriger, dus het kan best dat uiteindelijk nog maar 7 decimalen aan precisie over houdt.

[Math-E-Mad-X]

Ik weet niet hoe java doubles representeerd, dus ik weet niet zeker of Math.pow(2, n) exact gerepresenteerd wordt.
 
Mocht dat niet zo zijn, dan kun je in  elk geval de precisie van die berekening verbeteren door Math.pow(2, n) te vervangen door 1<<n. Dat is de int die je verkrijgt door de bits van het getal 1 n plaatsen naar links te verschuiven, wat toevallig precies hetzelfde is als 2 tot de macht n. Hiervan weet je in elk geval zeker dat de berekening exact is, maar ik heb geen idee of het hier echt uit zal maken.

Ah, waarschijnlijk kun je een nog veel efficientere optimalisatie verkrijgen als je het volgende opmerkt:
 
elke iteratie eindigt met de uitdrukking
   segment = Math.sqrt(...
Maar in de volgende iteratie, is het eerste wat je met segment doet het volgende:
   segment * segment
 
Dat is natuurlijk niet zo efficient

Edit: mijn vorige opmerking over Math.pow() vervangen door 1<<n kun je trouwens wel vergeten. Ik zie nu dat je die uitdrukking alleen in de allerlaatste regel echt gebruikt dus dat gaat vrijwel niets opleveren.

[Flisk]

Ik ga niet direct een nieuw algoritme schrijven, ik was eerder nieuwsgierig hoe nauwkeurig/snel deze zou zijn. Uiteraard bestaan er veel betere algoritmes. Het is geen reeksontwikkeling. Het komt erop neer dat de omtrek van een cirkel benaderd wordt door de omtrek van een regelmatige veelhoek.

n=0 stelt een driehoek voor, n=1 een zeshoek, ..., n=n een 3*2ⁿ hoek.

De lus halveert bij elke iteratie de hoek van een driehoekje en berekent er de sinus van. Eigenlijk dus gewoon de halveringsformule

\(sin(a)=\sqrt{\frac{1-\sqrt{1-sin(2a)^2}}{2}}\)

Dan krijg je een dubbel aantal driehoekjes en moet je dus maal twee doen, daarom dat het eindresultaat na n iteraties maal 3*2ⁿ wordt gedaan.

Het probleem zal bij het type double zitten, ik ga morgen eens herschrijven naar BigDecimal en er zo hopelijk iets meer uit krijgen. In de zin dat het programma enkele seconden/minuten draait voordat het afloopt. Nu is het telkens direct klaar.

 

Ah, waarschijnlijk kun je een nog veel efficientere optimalisatie verkrijgen als je het volgende opmerkt:
 
elke iteratie eindigt met de uitdrukking
   segment = Math.sqrt(...
Maar in de volgende iteratie, is het eerste wat je met segment doet het volgende:
   segment * segment
 
Dat is natuurlijk niet zo efficient

Inderdaad, zal ik eens veranderen. Dan wordt er toch al elke lus één sqrt minder genomen.

EDIT:

Net methode veranderd, het verschil is nauwelijks merkbaar.

Code: Selecteer alles

public static void benaderPi(int n){

double segment=0.75;

System.out.println("Benadering van pi (regelmatige "+3*Math.pow(2,n)+" hoek):");

for(int i=0;i<n;i++){

segment=(1-Math.sqrt(1-segment))/2;

}

System.out.print(Math.sqrt(segment)*3*Math.pow(2,n)+", ");
	}

Voor n=17 (3.1415923038117377) is het resultaat weeral slechter dan voor n=16 (3.1415926453212157)

[Flisk]

Kleine update, het gebruik maken van BigDecimal heeft het probleem opgelost. Resultaten zijn nu veel nauwkeuriger.