[b]TEST[/b] für int ob eine wurzel mit rest==0
-
ich möchte von einer ingeter-zahl nur wissen, ob es eine wurzel ohne rest gibt, gibt es dafür einen algorithmus?
es sind natürlich immer nur gerade zahlen und ich muss die wurzel garnicht wissen, ich muss nur wissen ob es eine gibt. sowas könnte ja schneller gehen als zu versuchen sie auszurechnen (was bei sehr großen zahlen auch entsprechend langsam ist).
mit http://de.wikipedia.org/wiki/Satz_von_Vieta afaik bzw http://de.wikipedia.org/wiki/Wurzelsatz_von_Vietá kann man bei int nicht viel anfangen, oder?
thx4help
rapso->greets();
-
ich kenne nur den weg, daß man die wurzel ausrechnet.
und natürlich vorher schauen, ob die endziffer 0, 1, 4, 9, 6 oder 5 ist. oder besser in nem größeren zahlensystem.
-
eine natürliche Zahl n ist ein Quadrat über den ganzen Zahlen, wenn sie in Z/kZ mit k>=n+1 ein Quadrat ist.
Wenn wir jetzt hätten: n ist Quadrat in Z/pZ und Z/qZ mit p,q teilerfremd, dann gibt uns das, daß es auch ein Quadrat in Z/pqZ ist.
Wir können also immer lokal testen in Z/p1Z bis Z/prZ und wissen dann, daß es in Z/p1*...*prZ ein Quadrat ist.(chin. Restsatz) Das machen wir so lange bis p1*...*pr>=n+1 ist. Dann wissen wir, daß es auch echt ein Quadrat ist.
Prüfen wir also in
2,3,5,7,11,13,17,19,23,29
Dann wissen wir, daß es bis
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6 469 693 230
ein Quadrat ist. Das genügt zumindest für ne 32Bit-Zahl. Und es sind immerhin nur 10 Tests.Allerdings muß man die Quadrate in den Gruppen finden, aber weil die klein sind kann man das mit ner Tabelle machen.
-
Ne, ganz so funktioniert es doch nicht.
Wenn dieses Verfahren sagt: ist keine Quadrat, dann isses auch keins. Aber der Rückweg stimmt noch nicht. Wenn er sagt es sei ein Quadrat, dann muß es das noch nicht sein.
Vielleicht kann man's zumindest als schnellen Vortest benutzen?
-
Bei den Zahlen 0 bis 1Mrd macht das Verfahren an 5016764 Stellen Fehler. Das sind etwa 0,5% der Fälle. Da muß man dann vielleicht noch teurer nachprüfen. Ist das vertretbar?
Auch quard... die Fälle wo's echt ne Quadratzahl ist muß auch noch dazu. Aber davon gibt's ja zum Glück nicht so viele!
Insgesamt also weitere Tests in 5048387 Fällen. Das sind immer noch etwa 0,5% der Fälle.
Vielleicht kann man aber die Tests so weit hochschrauben, daß der Fehler klein genug wird, daß er bei nem kompletten unsigned long nicht mehr ins Gewicht fällt?
-
http://www.diaware.de/html/wurzel.html
Ich würde das so weit machen bis entweder das Komma kommt oder bis man fertig ist.
-
rapso schrieb:
für n 3 bis ca sqrt(Zahl) .
Ne. Du mußt nur in Z/pZ testen mit p = 3 bis p=29 (nur die Primzahlen) dann reichst Du bis 2*3*...*29, das ist mehr als ne 32Bit-Zahl. Wenn Dir dieser Vortest sagt: Das Teil hat keine Wurzel, dann hat es auch keine. Nur wenn er ne Wurzel feststellt (sind im Bereich bis 1Mrd etwa 0,5% der Fälle, dann mußt Du noch mehr rechnen.
Vielleicht verrätst Du mal etwas mehr über die Zahlen bzw. die Plattforum auf der Du das machst?
-
ups, sorry rapso. Hab aus versehen Deinen Beitrag editiert.
-
Hallo rapso
ich möchte von einer ingeter-zahl nur wissen, ob es eine wurzel ohne rest gibt, gibt es dafür einen algorithmus?
[cpp] squaredbit = 0x040000000; result = 0; while ( squaredbit > 1 ) // Durchlauf für Vorkommastellen-------- { sr = result; // sr = ( squaredbit | result ); sr |= squaredbit; if ( x >= sr ) { x -= sr; result >>= 1; // 1 Bit >> schieben !!! result |= squaredbit; } else result >>= 1; // 1 Bit >> schieben !!! squaredbit >>= 2; // 2 Bits >> schieben !!! } if ( x > 0 ) ........dann keine Wurzel [/cpp]Voila, es ist angerichtet.
mfG
rudiS
-
mein ansatz wäre ein primfaktorzerlegung, denke mal da gibt es ein paar schnelle. wenn jeder primfaktor mit einer graden anzahl vorkommt ist es eine quadratzahl, wenn net, dann halt net...
.MamboKurt