Quadratzahl-Test

[0001001]

Hallo,

hab mir ein paar Zeilen geschrieben, die überprüfen sollen ob eine Zahl eine Quadratzahl (z.B. 9, 49, 64) ist. Allerdings ist der noch nicht wirklich effizient. Wäre super wenn sich das mal jemand anschauen könnte und vielleicht einen Verbesserungsvorschlag machen könnte.

	public boolean checkifsquarenumber2(int number){
		boolean check = false;		
		int lastnumber, secondlastnumber;
		String aaa = String.valueOf(number);
		lastnumber = Integer.parseInt(String.valueOf( aaa.charAt(aaa.length()-1)));		// get the last number
		secondlastnumber = Integer.parseInt(String.valueOf( aaa.charAt(aaa.length()-2))); // get the secondlast number
		if (secondlastnumber == 2 || secondlastnumber == 4 || secondlastnumber == 6 || secondlastnumber == 8 || secondlastnumber == 0){
			if (lastnumber == 1 || lastnumber == 4 || lastnumber == 9){
				if (Math.pow(Math.sqrt(Double.parseDouble(aaa)),2) == Double.parseDouble(aaa)){ 	// checks if: (number^(1/2))² == number				
					check = true;
				}
			}
		}
		if ((secondlastnumber == 1 || secondlastnumber == 3 || secondlastnumber == 5 || secondlastnumber == 7 || secondlastnumber == 9) && lastnumber == 6){	
			if (Math.pow(Math.sqrt(Double.parseDouble(aaa)),2) == Double.parseDouble(aaa)){						
				check = true;
			}			
		}
		return check;
	}

Hier eine kurze Beschreibung des Algorithmus:
Zuerst werden die letzten beiden Ziffern der übergebenen Zahl gespeichert. Das liegt daran, dass man anhand der letzten beiden Ziffern oft ausschliessen kann dass es eine Quadratzahl ist. Bei einer Quadratzahl gibt es es nur 22 Möglichkeiten: 00, x1, x4, 25, y6 und x9, wobei x für eine gerade und y für eine ungerade Ziffer steht. (Quelle: Wikipedia).
Falls die Zahl den obigen Anforderungen entspricht, wird mit:

if (Math.pow(Math.sqrt(Double.parseDouble(aaa)),2) == Double.parseDouble(aaa))

überprüft ob es wirklich eine Quadratzahl ist. Es wird folgendes berechnet: (number^(1/2))² == number
Leider rundet Math.sqrt, ansonsten würde man schon erkennen, ob es eine Quadratzahl ist, indem man schaut ob die Wurzel eine ganze Zahl ergibt. Da Math.sqrt und Math.pow nur Double unterstützen, hab ich das häßliche Double.parseDouble() benutzt.

Wäre super wenn jemand den Algorithmus verbessern könnte, denn ich glaube der ist noch ziemlich ineffizient

 

[Leroy42]

... und wofür braucht man sowas? :shock:

 

[Wildcard]

Ehrlich gesagt halte ich deine Optimierungen für Kontraproduktiv. Das Wurzelziehen sollte relativ effizient erfolgen und daher schneller sein als dein derzeitiger Ansatz.

 

[0001001]

... und wofür braucht man sowas? :shock:

hierfür z.B. http://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat

Ehrlich gesagt halte ich deine Optimierungen für Kontraproduktiv. Das Wurzelziehen sollte relativ effizient erfolgen und daher schneller sein als dein derzeitiger Ansatz.

Wieso? das ist doch nur ein simpler Vergleich der bestimmt schneller geht, als die Wurzel zu ziehen?! Dadurch werden sehr viele Zahlen von vornherein ausgeschlossen.

 

[SlaterB]

also bei mir ist
Math.sqrt(17) = 4.123105625617661
da läßt sich doch gut erkennen, dass das keine ganze Zahl ist,

bei dir kommt da 4.00000000 raus oder wie?

da bei mir sqrt nicht rundet funktioniert dein Algoritmus bei mir nicht
----------

die Fälle 'letzte Ziffern 00 und 25' hattest du vergessen

---------

wieso machts du einen String aus der Zahl, der danach auch noch zweimal(!) wieder nach Double gecastet wird?
ineffizienter gehts ja kaum noch,
zumal die Zahl doch immernoch als int verfügbar ist (number)

bei mir wurde es ~8x schneller, nachdem ich das entfernt hatte..
--------

wenn du im ersten if-Block auf gerade vorletzte Zahl prüfst,
wozu dann im zweiten if-Block nochmal auf ungerade prüfen?,
benutze einfach ein else, dann sparst du ein bisschen
(naja, hauptsächlich Code-Zeilen..)

------

die Berechnung der letzten Stellen in int ist aber tatsächlich langsamer als nur sqrt,
selbst wenn man nur eine Berechnung der letzten beiden Ziffern macht
und auf ein 100er-Array zurückgreift, reicht es nicht
(getestet mit Berechnung von 10 Mio Zahlen oder so)

berücksicht man noch mehr Stellen wirds irgendwann sicher besser, aber das Array immer größer,

denn vergleich man nur die Berechnung der letzten x Stellen mit modulo
mit der Wurzelberechnung, so ist das Stellen-Berechnen knapp schneller

mit Bit-Operationen und anderen Optimierungen machts vielleicht doch irgendwann Sinn,
allerdings kann auch beim sqrt noch viel eingespart werden,
2/3 der Zeit gehen dort (bei mir) für den Test drauf, ob die Wurzel nun eine ganze Zahl ist oder nicht

public class Test {

	static boolean[] secondlastsArray = new boolean[100];

	public static void main(String args[]) throws Exception {
		for (int i = 0; i < 100; i++) {
			int lastnumber = i % 10;
			int secondlastnumber = (i / 10) % 10;

			boolean b = false;
			if (secondlastnumber == 2
				|| secondlastnumber == 4
				|| secondlastnumber == 6
				|| secondlastnumber == 8
				|| secondlastnumber == 0) {
				if ((lastnumber != 1)
					&& (lastnumber != 4)
					&& (lastnumber != 9)) {
					b = true;
				}
			} else if (lastnumber != 6) {
				b = true;
			}

			if ((secondlastnumber == 2) && (lastnumber == 5)) {
				b = false;
			} else if ((secondlastnumber == 0) && (lastnumber == 0)) {
				b = false;
			}

			secondlastsArray[i] = b;
			//	p("i: " + i + " " + secondlastsArray[i]);
		}

		long time = System.currentTimeMillis();

		for (int i = 10; i < 10000000; i++) {
			//		for (int i = 10; i < 1000; i++) {
			//		for (int i = 121; i < 122; i++) {
			//		if (checkifsquarenumber2(i)) {
			//			p("i: " + i);
			//		}
			checkifsquarenumber2(i);

		}

		p("time: " + (System.currentTimeMillis() - time));
	}

	public static boolean checkifsquarenumber2(int number) {

		//int secondlasts = number % 100;
		//if (secondlastsArray[secondlasts]) {
		//	return false;
		//}

		double sqrt = Math.sqrt(number);
		return (sqrt - ((int) sqrt) < 0.000000000001);
	}

	public static void p(double i) {
		p("" + i);
	}

	public static void p(Object o) {
		System.out.println(((o == null) ? "null" : o));
	}
}