einfaches finden von Quadratzahlen

Übersicht

BlitzBasic

Allgemein

	Triton Betreff: einfaches finden von Quadratzahlen	So, Mai 14, 2006 17:30 Antworten mit Zitat
Folgendes Problem: wie finde ich einfach und vorallem schnell raus, wann eine Zahl eine Quadratzahl ist? Bsp: Ich habe folgende Zahlenliste: 49,77,91 Wobei 49 die einzige Quadratzahl ist. Wie finde ich nun heraus, dass es so ist? if wurzel(z)*wurzel(z)=z then quadz=1 (wobei wurzel(z) nur die ganzzahlige wurzel liefert) ist zu langsam. Überhaupt will ich nicht die wurzel berechnen müssen. Vorschläge?
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: einfaches finden von Quadratzahlen

So, Mai 14, 2006 17:30
Antworten mit Zitat

Folgendes Problem:

wie finde ich einfach und vorallem schnell raus, wann eine Zahl eine Quadratzahl ist?

Bsp: Ich habe folgende Zahlenliste: 49,77,91

Wobei 49 die einzige Quadratzahl ist. Wie finde ich nun heraus, dass es so ist?

if wurzel(z)*wurzel(z)=z then quadz=1 (wobei wurzel(z) nur die ganzzahlige wurzel liefert) ist zu langsam. Überhaupt will ich nicht die wurzel berechnen müssen.

Vorschläge? Smile

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Willi die Rübe	So, Mai 14, 2006 17:49 Antworten mit Zitat
Ich glaube nicht, dass es eine schnellere Variante gibt, aber du kannst ja vorher in einem Dimfeld alle Zahlen durchrattern und dann später einfach If Quad(49) = 1 then Print "Woohoo" Greetz
Ich habe keine Lösung, aber ich bewundere das Problem. Tehadon Q6600, MSI Neo2-FR, 4GB Ram, nVidia 7800 GTX At the Farewell Party visit: MySpace \| Homepage

Willi die Rübe

So, Mai 14, 2006 17:49
Antworten mit Zitat

Ich glaube nicht, dass es eine schnellere Variante gibt, aber du kannst ja vorher in einem Dimfeld alle Zahlen durchrattern und dann später einfach If Quad(49) = 1 then Print "Woohoo"

Greetz

Ich habe keine Lösung, aber ich bewundere das Problem.
Tehadon
Q6600, MSI Neo2-FR, 4GB Ram, nVidia 7800 GTX
At the Farewell Party visit: MySpace | Homepage

	SpionAtom	So, Mai 14, 2006 17:52 Antworten mit Zitat
http://www.lingen-ems.de/numero/quadrat.php Hiermit kannst du zuminest schonmal ausschließen...
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

SpionAtom

So, Mai 14, 2006 17:52
Antworten mit Zitat

http://www.lingen-ems.de/numero/quadrat.php

Hiermit kannst du zuminest schonmal ausschließen...

os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

	D2006 Administrator	So, Mai 14, 2006 18:06 Antworten mit Zitat
Interessantes Thema. Was ich fix im Netz gefunden habe: - Wenn die Zahl auf 2,3 oder 7 endet ( Mod 10 benutzen) ist es keine Quadratzahl. - Man summiert beginnend ab 1 alle ungeraden Zahlen. Stimmt die Summe irgendwann mit der zu prüfenden Zahl überein, haben wir einen Treffer. Abbruch natürlich dann, wenn die Summe größer ist als die Zahl. Mal eben aus dem Kopf zusammengecodet: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function IsSquare( zahl%) If zahl% < 1 Then Return 0 Local sum%, i% = 1 sum% = zahl% Mod 10 If sum% = 2 Or sum% = 3 Or sum% = 7 Then Return 0 sum% = 0 Repeat sum% = sum% + i% i% = i% + 2 If sum% = zahl% Then Return 1 Until sum% > zahl% Return 0 End Function Das Prüfen auf Richtigkeit, Geschwindigkeit und Optimierungspotential überlasse ich dir.
Intel Core i5 2500 \| 16 GB DDR3 RAM dualchannel \| ATI Radeon HD6870 (1024 MB RAM) \| Windows 7 Home Premium Intel Core 2 Duo 2.4 GHz \| 2 GB DDR3 RAM dualchannel \| Nvidia GeForce 9400M (256 MB shared RAM) \| Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz \| 3 GB DDR2 RAM dualchannel \| ATI Radeon HD3850 (1024 MB RAM) \| Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2

D2006

Administrator

So, Mai 14, 2006 18:06
Antworten mit Zitat

Interessantes Thema. Was ich fix im Netz gefunden habe:

- Wenn die Zahl auf 2,3 oder 7 endet ( Mod 10 benutzen) ist es keine Quadratzahl.

- Man summiert beginnend ab 1 alle ungeraden Zahlen. Stimmt die Summe irgendwann mit der zu prüfenden Zahl überein, haben wir einen Treffer. Abbruch natürlich dann, wenn die Summe größer ist als die Zahl.

Mal eben aus dem Kopf zusammengecodet:

BlitzBasic: [AUSKLAPPEN]


Function IsSquare( zahl%)

	If zahl% < 1 Then Return 0

	Local sum%, i% = 1

	sum% = zahl% Mod 10
	If sum% = 2 Or sum% = 3 Or sum% = 7 Then Return 0
	sum% = 0

	Repeat
		sum% = sum% + i%
		i% = i% + 2
		If sum% = zahl% Then Return 1
	Until sum% > zahl%
	Return 0

End Function

Das Prüfen auf Richtigkeit, Geschwindigkeit und Optimierungspotential überlasse ich dir. Smile

	SpionAtom	So, Mai 14, 2006 18:09 Antworten mit Zitat
Außer dem Endzifferkriterium gibt es ja noch andere Hinweise darauf, dass es sich [i]nicht[/] um eine Quadratzahl handelt. Zum Beispiel, dass wenn die zu prüfende Zahl kein Vielfaches von 4 ist (bei gerade Zahlen). Wenn alle diese Kriterien nicht greifen, kannst du ja immer noch die Wurzen ziehen, oder die ebengenannte Reihenentwicklung nutzen. Auf alle Fälle sparst du kostbare Rechenzeit...
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

SpionAtom

So, Mai 14, 2006 18:09
Antworten mit Zitat

Außer dem Endzifferkriterium gibt es ja noch andere Hinweise darauf, dass es sich [i]nicht[/] um eine Quadratzahl handelt. Zum Beispiel, dass wenn die zu prüfende Zahl kein Vielfaches von 4 ist (bei gerade Zahlen). Wenn alle diese Kriterien nicht greifen, kannst du ja immer noch die Wurzen ziehen, oder die ebengenannte Reihenentwicklung nutzen. Auf alle Fälle sparst du kostbare Rechenzeit...

os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

	Kryan	So, Mai 14, 2006 18:32 Antworten mit Zitat
Ist halt die Frage, ob Code: [AUSKLAPPEN] [EINKLAPPEN] If Sqr(z)Sqr(z)=z Then Return 1 oder Code:* [AUSKLAPPEN] [EINKLAPPEN] If zahl% < 1 Then Return 0 Local sum%, i% = 1 sum% = zahl% mod 10 If sum% = 2 Or sum% = 3 or sum% = 7 Then Return 0 sum% = 0 Repeat sum% = sum% + i% i% = i% + 2 If sum% = zahl% Then Return 1 Until sum% > zahl% kürzer ist. Ich würde zum ersten tangieren, denn im zweiten wird eine Repeat-Until-Schleife verwendet!!
Webspaceanbieter? Klick hier! Kultige Spieleschmiede? Klick hier!

Kryan

So, Mai 14, 2006 18:32
Antworten mit Zitat

Ist halt die Frage, ob

Code: [AUSKLAPPEN]

If Sqr(z)*Sqr(z)=z Then Return 1

oder

Code: [AUSKLAPPEN]

If zahl% < 1 Then Return 0

Local sum%, i% = 1

sum% = zahl% mod 10
If sum% = 2 Or sum% = 3 or sum% = 7 Then Return 0
sum% = 0

Repeat
sum% = sum% + i%
i% = i% + 2
If sum% = zahl% Then Return 1
Until sum% > zahl%

kürzer ist. Ich würde zum ersten tangieren, denn im zweiten wird eine Repeat-Until-Schleife verwendet!!

Webspaceanbieter?
Klick hier!
Kultige Spieleschmiede?
Klick hier!

	D2006 Administrator	So, Mai 14, 2006 18:49 Antworten mit Zitat
Codelänge und Ausführungsgeschwindigkeit haben i.d.R. keine Zusammenhang. Ich habe nun selbst mal ein paar Speedtests gemacht. Raus bekommen habe ich, dass die Durchlaufdauer meiner Funktion (erwartungsgemäß) von der Größe der Zahl abhängt. Bis ungefähr 3000 ist meine Funktion schneller, danach ist die Wurzelmethode zu bevorzugen. Einen richtigen Geschwindigkeitsschub gibt es aber nicht. MfG D2006
Intel Core i5 2500 \| 16 GB DDR3 RAM dualchannel \| ATI Radeon HD6870 (1024 MB RAM) \| Windows 7 Home Premium Intel Core 2 Duo 2.4 GHz \| 2 GB DDR3 RAM dualchannel \| Nvidia GeForce 9400M (256 MB shared RAM) \| Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz \| 3 GB DDR2 RAM dualchannel \| ATI Radeon HD3850 (1024 MB RAM) \| Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2

D2006

Administrator

So, Mai 14, 2006 18:49
Antworten mit Zitat

Codelänge und Ausführungsgeschwindigkeit haben i.d.R. keine Zusammenhang.

Ich habe nun selbst mal ein paar Speedtests gemacht.
Raus bekommen habe ich, dass die Durchlaufdauer meiner Funktion (erwartungsgemäß) von der Größe der Zahl abhängt. Bis ungefähr 3000 ist meine Funktion schneller, danach ist die Wurzelmethode zu bevorzugen.

Einen richtigen Geschwindigkeitsschub gibt es aber nicht.

MfG
D2006

	Dante	So, Mai 14, 2006 20:25 Antworten mit Zitat
hmm dieses "If Sqr(z)Sqr(z)=z Then Return 1" dürfte meiner meinung so oder so nicht funzen. Da man aus jeder Zahl eine Wuzel ziehen kann und wenn man dann diese Wurzel mit sich selber multipliziert kommt die Ursprungszahl wieder raus! Das heißt er würde auch bei 35 sagen, dass es eine Quadrathzahl ist. oder irre ich mich??? Edit: Auf den Beitrag von Kryan bezogen* Ach und die Zeiten bei den Posts stimmen irgendwie auch net habe das net um 6:25pm gepostet sondern um 8:25pm MfG

Dante

So, Mai 14, 2006 20:25
Antworten mit Zitat

hmm dieses "If Sqr(z)*Sqr(z)=z Then Return 1"
dürfte meiner meinung so oder so nicht funzen.

Da man aus jeder Zahl eine Wuzel ziehen kann und wenn
man dann diese Wurzel mit sich selber multipliziert kommt
die Ursprungszahl wieder raus!

Das heißt er würde auch bei 35 sagen, dass es eine Quadrathzahl ist.
oder irre ich mich???

Edit: Auf den Beitrag von Kryan bezogen
Ach und die Zeiten bei den Posts stimmen irgendwie auch net Laughing

habe das net um 6:25pm gepostet sondern um 8:25pm Shocked

MfG

Zuletzt bearbeitet von Dante am So, Mai 14, 2006 20:40, insgesamt 4-mal bearbeitet

	D2006 Administrator	So, Mai 14, 2006 20:33 Antworten mit Zitat
Hat er auch nicht behauptet. Lies nochmal seinen Beitrag durch. Außerdem spielt das nicht die Rolle, die Wurzel ist ja so und so zu vermeiden.
Intel Core i5 2500 \| 16 GB DDR3 RAM dualchannel \| ATI Radeon HD6870 (1024 MB RAM) \| Windows 7 Home Premium Intel Core 2 Duo 2.4 GHz \| 2 GB DDR3 RAM dualchannel \| Nvidia GeForce 9400M (256 MB shared RAM) \| Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz \| 3 GB DDR2 RAM dualchannel \| ATI Radeon HD3850 (1024 MB RAM) \| Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2

D2006

Administrator

So, Mai 14, 2006 20:33
Antworten mit Zitat

Hat er auch nicht behauptet. Lies nochmal seinen Beitrag durch. Außerdem spielt das nicht die Rolle, die Wurzel ist ja so und so zu vermeiden.

	Triton	So, Mai 14, 2006 23:26 Antworten mit Zitat
naja, es geht nicht um kleine, sondern eben um sehr große Zahlen (>2^31). Da kann es mitunter schon länger dauern ne Wurzel zu ziehen und dann wieder zu Quadrieren. Ich brauche das für eine kleine Primzahl-funktion die für beliebig große Zahlen verwendbar ist. Dort kann ich keinen Array nutzen um vorhandene Primzahlen (als mögliche Teiler) zu speichern (da dies u.U mehr und größere sein können, als BB es verkraftet), wenn ich aber nur die Zahlen nutze die bei folgendem Muster schwarz sind, geht es trotzdem noch ziemlich schnell ohne Primzahlen schon im Speicher haben zu müssen: Die meisten schwarzen Zahlen sind Primzahlen, einige andere sind aber noch Quadratzahlen (z.B 49) und solche mit größeren Primteilern (wenn man die Liste weiterführt z.B 77). Wenn ich nun noch die Quadratzahlen einfach rausfiltern kann, so habe ich eine gute Liste von möglichen Teilern fürs Probedividieren. Zitat: hmm dieses "If Sqr(z)Sqr(z)=z Then Return 1" dürfte meiner meinung so oder so nicht funzen. Da man aus jeder Zahl eine Wuzel ziehen kann und wenn man dann diese Wurzel mit sich selber multipliziert kommt die Ursprungszahl wieder raus! Ich schrob doch wurzel(z). Eine solche Funktion ermittelt nur die ganzzahlige Wurzel einer Zahl, was viel schneller ist als mit Nachkommastellen. Wenn ich nun wissen will, ob die Ursprungszahl ne Quadratzahl war, muss ich das wieder quadrieren und schauen ob die Ergebnisse übereinstimmen. Zitat: habe das net um 6:25pm gepostet sondern um 8:25pm Änder in deinem Profil deine Forenzeitverschiebung. -- @d2006: zu einem ersten Geschwindigkeitstest: Code:* [AUSKLAPPEN] [EINKLAPPEN] t = MilliSecs() For oft = 1 To 1000 Print issquare(961124004) ;wz%=Int(Sqr(961124004)) ;If wzwz=961124004 Then Print "1" Next Print MilliSecs()-t+" ms" WaitKey Function IsSquare( zahl%) If zahl% < 1 Then Return 0 Local sum%, i% = 1 sum% = zahl% Mod 10 If sum% = 2 Or sum% = 3 Or sum% = 7 Then Return 0 sum% = 0 Repeat sum% = sum% + i% i% = i% + 2 If sum% = zahl% Then Return 1 Until sum% > zahl% Return 0 End Function Bei mir ist deine Funktion langsamer. Aber das ist nur ein erster Test, vielleicht gibts ncoh genug Optimierungspotential, damits schneller wird. edit-- Code:* [AUSKLAPPEN] [EINKLAPPEN] For oft = 1 To 100000 ;a=issquare(961124004) wz%=Int(Sqr(961124004)) If wz*wz=961124004 Then a=1 Next Wenn man das Print entfernt und nur ne Variable auf True setzt, wird der Unterschied sehr deutlich. hmm..
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

So, Mai 14, 2006 23:26
Antworten mit Zitat

naja, es geht nicht um kleine, sondern eben um sehr große Zahlen
(>2^31). Da kann es mitunter schon länger dauern ne Wurzel zu ziehen und dann wieder zu Quadrieren.

Ich brauche das für eine kleine Primzahl-funktion die für beliebig große Zahlen verwendbar ist. Dort kann ich keinen Array nutzen um vorhandene Primzahlen (als mögliche Teiler)
zu speichern (da dies u.U mehr und größere sein können, als BB es verkraftet),
wenn ich aber nur die Zahlen nutze die bei folgendem Muster schwarz sind,
geht es trotzdem noch ziemlich schnell ohne Primzahlen schon im Speicher haben zu müssen:

user posted image

Die meisten schwarzen Zahlen sind Primzahlen, einige andere sind aber noch Quadratzahlen (z.B 49) und solche mit größeren Primteilern (wenn man die Liste weiterführt z.B 77).

Wenn ich nun noch die Quadratzahlen einfach rausfiltern kann, so habe ich eine
gute Liste von möglichen Teilern fürs Probedividieren.

Zitat:

Ich schrob doch wurzel(z).
Eine solche Funktion ermittelt nur die ganzzahlige Wurzel
einer Zahl, was viel schneller ist als mit Nachkommastellen.
Wenn ich nun wissen will, ob die Ursprungszahl ne Quadratzahl
war, muss ich das wieder quadrieren und schauen ob die Ergebnisse übereinstimmen.

Zitat:

habe das net um 6:25pm gepostet sondern um 8:25pm

Änder in deinem Profil deine Forenzeitverschiebung. Wink

--
@d2006: zu einem ersten Geschwindigkeitstest:

Code: [AUSKLAPPEN]

t = MilliSecs()
For oft = 1 To 1000
Print issquare(961124004)
;wz%=Int(Sqr(961124004))
;If wz*wz=961124004 Then Print "1"
Next
Print MilliSecs()-t+" ms"
WaitKey

Function IsSquare( zahl%)

If zahl% < 1 Then Return 0

Local sum%, i% = 1

sum% = zahl% Mod 10
If sum% = 2 Or sum% = 3 Or sum% = 7 Then Return 0
sum% = 0

Repeat
sum% = sum% + i%
i% = i% + 2
If sum% = zahl% Then Return 1
Until sum% > zahl%
Return 0

End Function

Bei mir ist deine Funktion langsamer. Aber das ist nur ein erster
Test, vielleicht gibts ncoh genug Optimierungspotential, damits schneller wird.

edit--
Code: [AUSKLAPPEN]

For oft = 1 To 100000
;a=issquare(961124004)
wz%=Int(Sqr(961124004))
If wz*wz=961124004 Then a=1
Next

Wenn man das Print entfernt und nur ne Variable auf True setzt, wird der Unterschied sehr deutlich. hmm.. Neutral

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	TheShadow Moderator	Di, Mai 16, 2006 18:25 Antworten mit Zitat
2^31 ist eine Zahl die doch recht überschaubar klein ist. Da wirst du einfach gar nix schnelleres finden können als SQR Was hast du nun vor. Willst du Zahl auf Primzahl prüfen? Und dann beliebig groß? Na dann...
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Di, Mai 16, 2006 18:25
Antworten mit Zitat

2^31 ist eine Zahl die doch recht überschaubar klein ist. Da wirst du einfach gar nix schnelleres finden können als SQR

Was hast du nun vor. Willst du Zahl auf Primzahl prüfen? Und dann beliebig groß? Na dann...

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

einfaches finden von Quadratzahlen

Betreff: einfaches finden von Quadratzahlen