Springen naar inhoud

Nauwkeuriger berekenen java.


  • Log in om te kunnen reageren

#1

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 10 september 2014 - 15:48

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

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:

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?

Je leest maar niet verder want je, je voelt het begin van wanhoop.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2382 berichten
  • Ervaren gebruiker

Geplaatst op 10 september 2014 - 16:47

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.c...BigDecimal.html

Veranderd door Math-E-Mad-X, 10 september 2014 - 16:49

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#3

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 10 september 2014 - 17:09

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

Je leest maar niet verder want je, je voelt het begin van wanhoop.

#4

aadkr

    aadkr


  • >5k berichten
  • 5441 berichten
  • Pluimdrager

Geplaatst op 10 september 2014 - 20:39

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?

Veranderd door aadkr, 10 september 2014 - 20:51


#5

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2382 berichten
  • Ervaren gebruiker

Geplaatst op 10 september 2014 - 20:58

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.

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#6

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2382 berichten
  • Ervaren gebruiker

Geplaatst op 10 september 2014 - 21:07

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.

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#7

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2382 berichten
  • Ervaren gebruiker

Geplaatst op 10 september 2014 - 21:22

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.

Veranderd door Math-E-Mad-X, 10 september 2014 - 21:20

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#8

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 10 september 2014 - 22:37

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*2n hoek.
De lus halveert bij elke iteratie de hoek van een driehoekje en berekent er de sinus van. Eigenlijk dus gewoon de halveringsformule LaTeX

Dan krijg je een dubbel aantal driehoekjes en moet je dus maal twee doen, daarom dat het eindresultaat na n iteraties maal 3*2n 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.

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)

Veranderd door Flisk, 10 september 2014 - 22:49

Je leest maar niet verder want je, je voelt het begin van wanhoop.

#9

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 11 september 2014 - 16:46

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

Je leest maar niet verder want je, je voelt het begin van wanhoop.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures