Quadratwurzel

[Freakfer]

Hallo

wie drücke ich folgende Zeile ohne Math.sqrt aus ?


int teiler_max = (int)(Math.sqrt(n))

Danke

 

[dotlens]

indem du dir selbst eine Methode schreibst die das macht, wofür brauchst du das denn?

 

[Guest]

Hierfür soll aber ziemlich einfach aufgebaut sein und da ist der math.srt zu kompliziert

class Primes222
{
	public static void main(String[] args)
	{	
		int start = 0,
		    end = 0;

		// Wert einlesen
		start = Integer.parseInt(args[0]);
		end   = Integer.parseInt(args[1]);

		int Primes = 0;
	
		for(int i = start; i <= end; i++)
		{
			int teiler_max = (int)(Math.sqrt(n));

			// Primzahlprüfung
		
			int rest, teiler;	
	
			teiler = 2;

			while(i%teiler > 0 && teiler<teiler_max)
			{
				teiler++;
			}

			if(teiler==teiler_max)
			{
				System.out.println(n);
				Primes++;
			}
	
		}	

		System.out.println("Anzahl von Primzahlen : " + Primes);	
	}
}

Edit von L-ectron-X: Code-Tags eingefügt

 

[0xdeadbeef]

wie drücke ich folgende Zeile ohne Math.sqrt aus ?


int teiler_max = (int)(Math.sqrt(n))

So:

int teiler_max = (int)Math.exp(0.5*Math.log(n)));

 

[Guest]

danke
versuche ich es mal so :lol:

 

[dotlens]

:shock: und was ist daran weniger kompliziert?

 

[Guest]

Ja das ist die Frage vielleicht gehts noch einfacher ?

:roll:

 

[0xdeadbeef]

War als Scherz gedacht :?

Diese Umschreibung ist zwar mathematisch korrekt, aber vermutlich noch langsamer als sqrt.

Ich nehme an, diie Wurzelberechnung machst Du aus diesem Grund:

Will man prüfen, ob eine Zahl n eine Primzahl ist, so genügt es, mögliche Teiler t der Zahl nur für alle t mit t2<n zu suchen, denn größere Zahlen m können keine Teiler von n mehr sein, wenn keine kleineren Teiler existieren: m·m>n. Beim Testen, ob die Zahl 5987 eine Primzahl ist, muß also nur für die Primzahlen bis Ö5987, also bis 73 geprüft werden, ob sie 5987 teilen. Wenn sich bis da keine Primzahl findet, die Teiler von 5987 ist, ist 5987 eine Primzahl. (Sie ist es.)

Ganz ehrlich bezweifle ich, daß Du auf die schnelle einen wesentlich perfomanteren Algorithmus zur Wurzelberechnung hinbekommst als den aus Math. Allerdings brauchst Du ja nur eine Näherung nach oben, also eine Funktion f(x), für die immer gilt: x >= f(x) >= sqrt(x)

Unter Umständen findet sich so eine Funktion, die wesentlich schneller zu berechnen ist. Je größer allerdings die Abweichung, um so mehr unnötige Schleifendurchläufe machst Du, womit der eventuelle Geschwindigkeitsvorteil wieder verloren ist.

Was Du mal versuchen könntest, wäre sowas:
http://home.t-online.de/home/arndt.bruenner/mathe/scripts/heronframe.htm

 

[CelikBlek]

Ist es so nicht komplizierter? Fehlen dir dabei die Werte :autsch: ? oder warum willst du es nicht benutzen?
Ob du sqrt benutzt oder exp ?!? Jedenfalls für deine Rödelmaschine ist es ziemlich egal

 

[Guest]

Hallo

das Problem bin ja nicht ich sondern unser Professor dem ist es einfach zu kompliziert für 3 Punkte :?
Aber einen Punkt ist es ihm immerhin auch so wert

Gruß

Aufgabe war:


Schreiben Sie ein effizientes Programm Primes, das alle Primzahl in einem gegebenen Zahlenintervall auflistet. Die Grenzen des Intervalls (beide inklusive) werden auf der Kommandozeile angegeben.

Ein Beispiel:

$ java Primes 10 20
11
13
17
19

Stellen Sie fest, wie viele Primzahlen zwischen 1.000.000.000 (109 = 1 Milliarde) und 1.000.100.000 (1 Milliarde und Einhunderttausend) liegen.

Idee: Prüfen Sie systematisch alle potentiellen Teiler t einer Zahl n. Wenn es kein t gibt, das n ohne Rest teilt (Modulus-Operator!), dann ist n eine Primzahl; andernfalls ist es keine Primzahl. Überlegen Sie genau, welche potentiellen Teiler t überhaupt überprüft werden müssen.

Das Programm erwartet als Kommandozeilenargumente zwei ganze, positive Zahlen fr die Grenzen des Zahlenintervalls, in dem Primzahlen gesucht werden.
Die Ausgabe besteht aus der Liste der Primzahlen in aufsteigender Reihenfolge.

 

[0xdeadbeef]

Vielleicht gab's den Punktabzug ja auch für das nicht verwendete "rest" und gar nicht für die (IMHO korrekte) Quadratwurzel?

 

[dotlens]

ich habs ja auch als witz aufgefasst, war dann nur erstaunt als er schrieb er probiere das mal

Überlegen Sie genau, welche potentiellen Teiler t überhaupt überprüft werden müssen.

soviel ich weiss können gerade zahlen keine primzahlen sein, oder? das könnte doch auch schon ein ansatz sein

 

[0xdeadbeef]

Die Teiler können aber schon gerade sein und wenn die zu teilende Zahl gerade ist, wird die while-Schleife nach der ersten Modulo-Berechnung verlassen.
-> man könnte etwas Geschwindigkeit gewinnen, wenn man die ungeraden Zahlen überspringt, aber das macht den Algorithmus unübersichtlicher und es werden ja nicht wirklich viele Operationen in der Schleife gespart.
[EDIT]
Ziehe ich zurück. Natürlich ist es sinnlos, gerade Teiler zu teste, weil jeder gerade Teiler auch durch 2 teilbar ist. Das dürfte dramatisch Zeit sparen!

 

[Reality]

int teiler_max = (int)Math.exp(0.5*Math.log(n)));

Super! Auf sowas wäre ich nicht gekommen! :toll:

Liebe Grüße
Reality

 

[abollm]

...
wie drücke ich folgende Zeile ohne Math.sqrt aus ?
int teiler_max = (int)(Math.sqrt(n))
...

Mit Berücksichtigung der sonstigen Postings würde ich mal sagen, dass du mit dem guten alten Newton-Verfahren auch operieren kannst.
Außerdem kann man sich eigentlich für jede aus Math. stammende Funktion eine eigene schreiben, wenn man weiß wie es geht. Stichwort: Konvergenzbeschleunigende Verfahren

 

[0xdeadbeef]

Das oben vorgeschlagene Heron-Verfahren entspricht (mehr oder weniger) dem Newton-Verfahren zum Finden von Nullstellen.
Die Frage ist aber wie gesagt, ob solch eine Näherung hinreichend viel schneller ist als die Wurzelbildung, um die dadurch auftretende Ungenauigkeit zu rechtgertigen. Abweichungen nach unten führen u.U. zu Fehlern in der Primzahlenbestimmung (also nicht tolerierbar), Abweichungen nach oben sorgen dafür, daß Teiler getestet werden, die zu keinem Ergebnis führen können.

 

[0xdeadbeef]

So, habe das Teil mal lauffähig implementiert und etwas getestet:

class Prime
{
    
    static double heron_sqrt(double x, int iter) {
        double result = x-1;
        if (result<=0) 
            result=1;
        for (int i=0; i<iter; i++) {
            x = (result + (x/result))/2; 
        }
        return result;
    }
    
    public static void main(String[] args)
    {
        int start=0, end=0;
        int numPrimes = 0;
        int teiler_max;
        int rest, teiler;
        
        // Werte einlesen
        try {
            start = Integer.parseInt(args[0]);
            end = Integer.parseInt(args[1]);
        } catch (NumberFormatException ex) {
            System.out.println("Ungültige Werte");
            System.exit(0);
        }               
        
        long ts = System.currentTimeMillis();
        for(long i = start; i <= end; i++) {
            if ((i&1)!=1) // gerade Zahlen können nicht prim sein!
                continue;
            
            teiler_max = (int)(Math.sqrt(i)); // nur Teiler bis sqrt(i) prüfen
            //teiler_max = (int)(heron_sqrt(i,4)); // nur Teiler bis sqrt(i) prüfen
            
            // Primzahlprüfung            
            for (teiler=3; teiler<=teiler_max; teiler+=2)
                if (i%teiler == 0)
                    break;
            if (teiler > teiler_max) {
                numPrimes++;
                System.out.println(i);
            }              
        }
        long te = System.currentTimeMillis();
        System.out.println("Anzahl von Primzahlen : " + numPrimes);
        System.out.println("Rechenzeit : " + (te-ts) + "ms");
    }
}

Freakfers Code ist nicht lauffähig, weil er i und n vertauscht hat. Weil ich hier und da rumoptimiert habe, sollte diese Version aber eh deutlich schneller sein.

In meiner Implementierung habe ich sowohl die geraden Zahlen bei den zu testenden Zahlen als auch bei den Teilern unterdrückt. Die Sonderfälle 1 (keine Primzahl) und 2 (Primzahl) habe ich nicht berücksichtigt: fängt man bei 1 an, bekommt man also 1,3,5,... anstelle von 2,3,5. Für eine ordentliche Implementierung müßte man also diese beiden Sonderfälle getrennt abfangen.

Um die Dikussion zum Wurzelziehen zu beenden, habe ich zudem einen einfachen Iterationsalgorithmus nach dem Heron-Verfahren implementiert. Bei einer Iterationstiefe von 4 liefert der Algorithmus zwischen 3 und 10000 korrekte Ergebnisse, braucht allerdings mehr als 3mal so lange. Weil das bereits bei relativ kleinen Zahlen so ist, kann man davon ausgehen, daß der Algorithmus bereits bei 4 Iterationsschritten erheblich länger braucht als die (vermutlich nativ implementierte) "normale" Wurzelfunktion. Bei großen Zahlen dürfte das Heron-Verfahren noch mehr Zeit kosten, weil dann die unnötig ausgeführten Schleifendurchläufe stärker ins Gewicht fallen.