Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Irrationale Wurzeln
Gehe zu Seite Zurück  1, 2, 3
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Irrationale Wurzeln
 
Autor Nachricht
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 27 Aug 2005 - 19:04:14    Titel:

Hallo,

Ich habe es einmal gemacht wie du gesagt hast, und ziehe die Wurzel nur, wenn die Exponenten der Primfaktoren durch n geteilt werden können.

Aber wie macht es mein Taschenrechner (TI89 von Texas Instruments)? Egal wie gross die Zahl ist, auch wenn er zum faktorisieren 30sek braucht, die Entscheidung, ob er die Wurzel ziehen soll (wenn die Wurzel natürlich ist zieht er sie, sonst nicht) macht er innert kürzester Zeit.

Gruss, Marko
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 30 Aug 2005 - 19:16:21    Titel:

Hast Du die Möglichkeit deinen Code lauffähig auf einer Seite rauszustellen? Ich denke mal darüber nach, wenn ich Zeit habe. Das geht sicher (Beweis ist dein TR*). Schaue Dir mal, wenn es nicht all zu sehr Probleme macht, Artikel zur Primzahlenfaktorisiereung an.

* Versuche mal doch die Approximation von Wurzeln durch Reihen zu machen und dann zu prüfen, ob das ganzzahlige Ergebnis hoch 2 passt. Dürfte schnell gehen!
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 31 Aug 2005 - 06:36:40    Titel:

Hallo,

Sorry, aber lauffähigen Code kann ich hier schlecht hintun.

Die Primfaktorenzerlegung habe ich mir ein wenig durchgeschaut, und mich für die Rho-Pollard Methode entschieden, die ziemlich schnell geht und nicht so aufwändig ist wie das quadratische Sieb.

Ich kann dir statt lauffähigen Code aber auf Nachfrage beliebige Ausschnitte bieten (Primfaktorenzerlegung, Wurzel ziehen, ...).

Bei deiner Approximationsidee: Ich muss den Test erst dann machen, wenn ich mit der Iteration so weit bin, dass der Unterschied des letzten und des aktuellen Ergebnisses kleiner als 1 ist, richtig?

Auf einen Versuch kommts an, wobei ich bis jetzt gesehen habe, das Wurzeln ziehen nicht wirklich schnell geht, vor allem bei hohen n's Wink

Gruss & Vielen Dank, Marko
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 31 Aug 2005 - 07:24:21    Titel:

Zitat:
Ich muss den Test erst dann machen, wenn ich mit der Iteration so weit bin, dass der Unterschied des letzten und des aktuellen Ergebnisses kleiner als 1 ist, richtig?


So einfach würde ich es nicht machen. Zu jedem Approx-Verfahren gibt es eine Fehlerabschätzung, die sagt, ab welchem n man so und so genau sein kann. Wenn Du z.B. Wurzeln mit Newtonverfahren berechnest mit

x^n - p = 0

und den Startwert geschickt wählst, dann ist die Folge monoton fallend, und dann kannst Du einfach die Stellen vergleichen. Ich habe irgendwie im Hinterkopf, dass Newton dabei vor allem in den ersten Schritten so schnell ist, dass Du nur ein paar Iterationen machen brauchst.
DustPuppy
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 03.09.2005
Beiträge: 2

BeitragVerfasst am: 03 Sep 2005 - 21:59:17    Titel:

algebrafreak hat folgendes geschrieben:
Ich habe noch eine Idee. Approximationsverfahren haben doch eine Fehlerabschätzung. Du könntest mit rationalen Zahlen doch die Wurzel bis auf 1 Stelle genau appriximieren (z.B. mit Newtonverfahren). Dazu brauchst Du ganz wenig Schritte. Und dann probierst Du einfach ob die benachbarten ganzen Zahlen hoch n eben deine Zahl ergeben. Dann bist Du fertig.


Hallo

Ich bin hobby programmierer mit gerade einmal einen Grundschul abschluss. Also verlangt bitte nicht zuviel von mir. Aber ich stehe vor dem selben problem. Ich programmiere gerade einen rechner (der übrigens so ausgelegt ist das man daraus leicht eine interpretersprache machen kann).

Aber könntest du mir vielleicht einen link geben in den ich mich ein bisschien einarbeiten kann? Oder noch besser kannst du mir es erklären?

Ich hoffe ich verlange nicht zu viel.
mfg.
DustPuppy
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 03 Sep 2005 - 23:18:23    Titel:

Zitat:
Ich bin hobby programmierer mit gerade einmal einen Grundschul abschluss.


Das wird schwierig. Ich denke mit Erklärungen kann man da nicht viel anrichten, denn Grundschule reicht bei weitem nicht. Du solltest mal Newton-Verfahren nachschlagen, z.B. in einem Analysis-Buch (z.B. Forster Analysis I). Der Algorithmus für die n-te Wurzel aus p geht so:

f(x) = x^n - p
f'(x) = n x^{n-1}

a_0 = p
a_{k+1} = a_k - f(a_k)/(n (a_n)^{n-1})

Dann gibt es eine Fehlerabschätzung, die ich nicht auswendig kenne. Eine naive Lösung wäre eine Umwandlung in eine z.B. 3-stellige Dezimalzahl und anschliessender Vergleich der Glieder a_k und a_{k+1}. Wenn die sich nur an der letzten Stelle unterscheiden so sind die ganzen Zahlen floor(a_k), und floor(a_k)+-1 zu prüfen, ob die hoch n nicht p ergeben.

P.S. Ich habe mir das Verfahren einfach ausgedacht. Eine sicherlich bessere Lösung wäre die entsprechende Literatur zu konsultieren. Ich hoffe es kommt nicht dazu, dass irgend einer, der eine Bijektion zwischen meinem Klo und diesem Verfahren einführen möchte das als eine Bahnbrechende physikalische Erfindung ansieht Smile
DustPuppy
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 03.09.2005
Beiträge: 2

BeitragVerfasst am: 04 Sep 2005 - 16:03:12    Titel:

algebrafreak hat folgendes geschrieben:

f(x) = x^n - p
f'(x) = n x^{n-1}

a_0 = p
a_{k+1} = a_k - f(a_k)/(n (a_n)^{n-1})


Also die erste Zeile verstehe ich ganz. Die x achse schneidet also die kurve genau auf dem Ergebnis der Wurzel. Das 2te ist die erste ableitung der ersten Funktion (aber wozu?). Kannst du mir bitte den Rest ausführlicher erklären? Das was mich verwirrt ist woher aufeinmal das k herkommt.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Irrationale Wurzeln
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3
Seite 3 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum