Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Irrationale Wurzeln
Gehe zu Seite Zurück  1, 2, 3  Weiter
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: 23 Jul 2005 - 15:53:32    Titel:

Ich ja noch nicht angefangen, ich mach mir Vorüberlegungen, und dazu bin ich hier.

Ich verstehe nicht ganz, wie du das mit der Faktorisierung meinst, kannst Du das bitte nochmals erklären?
Aber denkst Du, das ist eine gute Idee? Immerhin ist das Faktorisieren nicht grad das schnellste, und bei sehr grossen Zahlen (für die das Programm eigentlich gedacht ist) wird jede Potenzoperation dauern.

Meine eigentliche Frage war übrigens, um es nicht in vergessenheit geraten zu lassen: Wann soll ich die verlangte Wurzel ziehen, wann stehen lassen?

Danke für deine Mühen!
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 16:28:23    Titel:

Zitat:
Ich verstehe nicht ganz, wie du das mit der Faktorisierung meinst, kannst Du das bitte nochmals erklären?


Code:

>> factor(3564);

                                  2  4
                                 2  3  11


Ein Faktorisierungsalgorithmus ist für ein CAS zentral (neben der Arithmetik der ganzen Zahlen) und liefert zu einer Zahl eine liste von Paaren (Primzahl,Exponent). Wie oben ergibt

3564 = ((2,2),(3,4),(11,1)).

Wenn alle Exponenten durch deine Wurzelnummer teilbar sind, so besitzt die ganze Zahl eine n-te Wurzel, wie obiger Beweis zeigt.

Zitat:
Aber denkst Du, das ist eine gute Idee? Immerhin ist das Faktorisieren nicht grad das schnellste, und bei sehr grossen Zahlen (für die das Programm eigentlich gedacht ist) wird jede Potenzoperation dauern.


Ich denke, es ist keine gute Idee. Faktorisierung ist in NP und sollte somit bei Rechenoperationen nicht verwendet werden. Ich suche mal in meinem Zahlentheo. Skript nach einem besseren Wurzel-Test.

Es gibt da ein paar gute Zahlentheoretiker im Forum. Die könnten dazu auch was sicher sagen.

Zitat:
Meine eigentliche Frage war übrigens, um es nicht in vergessenheit geraten zu lassen: Wann soll ich die verlangte Wurzel ziehen, wann stehen lassen?


Dann wirst Du sicherlich schon auf das Problem "implizite vs. explizite Umformungen" gestoßen sein. Und meine Antwort ist: schwere Umformungen sollten keinesfalls implizit sein. Z.B. ist die Anwendung des Binomialsatzes auf

(1+x)^100000

eine schwere Umformung und sollte daher nicht implizit sein. Es gibt ja für Quadratzahlen einen Test, der widerlegt, dass eine Zahl eine Quadratzahl ist (Endung mit 2,3,7,8 sind keine), analog für die n-te Potenz. Außerdem kannst Du eine liste von Potenzzahlen anlegen z.B. bis 100000. Die ist ja nicht lang. Sollten beide dieser Tests versagen, so machst Du die Umformung explizit. D.h. der Nutzer muss einen Aufruf von Simplify tätigen, damit Du mit deinem Faktortest daher kommst.

Wie kommst Du eigentlich auf ein CAS in .NET? Ich programmiere gerade auch ein CAS. Es wäre mir aber nie in den Sinn gekommen eine so "hohe" Programmiersprache zu nehmen.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 23 Jul 2005 - 17:10:43    Titel:

Hi,

algebrafreak hat folgendes geschrieben:


Ein Faktorisierungsalgorithmus ist für ein CAS zentral (neben der Arithmetik der ganzen Zahlen) und liefert zu einer Zahl eine liste von Paaren (Primzahl,Exponent).


Danke, ich weiss was Faktorisieren ist Smile

Zitat:

Wenn alle Exponenten durch deine Wurzelnummer teilbar sind, so besitzt die ganze Zahl eine n-te Wurzel, wie obiger Beweis zeigt.


Hmm das kann ich noch nicht so ganz nachvollziehen. Kannst du mir noch ein konkretes Beispiel zeigen?

Zitat:

Ich suche mal in meinem
Zahlentheo. Skript nach einem besseren Wurzel-Test.


Vielen Dank.

Zitat:

Dann wirst Du sicherlich schon auf das Problem "implizite vs. explizite Umformungen" gestoßen sein. Und meine Antwort ist: schwere Umformungen sollten keinesfalls implizit sein.


Ja, nur bin ich noch nicht so weit, ich steck noch mit einem Fuss in der Arithmetik Razz

Zitat:

Es gibt ja für Quadratzahlen einen Test, der widerlegt, dass eine Zahl eine Quadratzahl ist (Endung mit 2,3,7,8 sind keine)


Ja, aber das nützt mir nicht viel, denn ich muss es ganz genau wissen.

Zitat:

Wie kommst Du eigentlich auf ein CAS in .NET? Ich programmiere gerade auch ein CAS. Es wäre mir aber nie in den Sinn gekommen eine so "hohe" Programmiersprache zu nehmen.


Das trifft sich gut, hast Du evt. Msn oder Icq? Dann können wir uns dort noch austauschen bzw. Du mir weitere Tips geben Wink

Zu .NET:
Also ich habe diese Umgebung gewählt, weil
- ich Objektorientiertheit sehr sehr schätze
- ich mich da grad am wohlsten fühl, denn ich habe lang nichts mehr in einer anderen Sprache gemacht
- Die Performance sich sehen lassen kann und ich mit seinem Defizit gegenüber Assembler leben kann Wink


Gruss[/quote]
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 17:55:12    Titel:

Zitat:
Hmm das kann ich noch nicht so ganz nachvollziehen. Kannst du mir noch ein konkretes Beispiel zeigen?


7007151645506250000 besitzt eine 4-te natürliche Wurzel. Das bekommt man so raus.

Code:

>> factor(7007151645506250000);

                                4  4  8  12
                               2  3  5  7


Da 4 | 4, 4 | 8 und 4 | 12. Daher gilt

7007151645506250000^(1/4) =
(2^4 3^4 5^8 7^12)^(1/4) =
2^(4/4) 3^(4/4) 5^(8/4) 7^(12/4) =
2 3 5^2 7^3 =
51450

Test Smile

Code:

>> 51450^4;

                            7007151645506250000


Zur Sprache. Normal schreibt man für CAS einen Interpreter, der lediglich die Schlüsselwörter versteht, ganze Zahlen addieren, dividieren mit Rest und multiplizieren kann und funktionen definieren kann. Ab dann arbeitet man nur in dieser Sprache. Ich habe eine Sprache entwickelt, die dynamische Bindung und Objektorientiertheit unterstützt. Ich bin da aber irgendwie noch dabei die Strukturenhierarchie objektorientiert zu modellieren. Das hat sich als äußerst nicht-trivial erwiesen Sad Denn solche Sachen, wie ein "Polynom in Z[x] über Q" stinkt fürchterlich nach Templates und will (noch) keine haben.

Ich habe kein Icq. Ich finde solche Fragen sollte man öffentlich ausdiskutieren, da je mehr Leute zusehen, desto schneller sind Fehler aufgedeckt.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 18:01:48    Titel:

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.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 23 Jul 2005 - 18:07:14    Titel:

Hi,

Danke, jetzt versteh ich das mit der Faktorisierung. Mal schauen inwiefern ich das nutzen kann.

Zitat:

Zur Sprache. Normal schreibt man für CAS einen Interpreter, der lediglich die Schlüsselwörter versteht, ganze Zahlen addieren, dividieren mit Rest und multiplizieren kann und funktionen definieren kann. Ab dann arbeitet man nur in dieser Sprache.


Du meinst also, ich müsse erst eine Sprache entwickeln (inklusive Funktions-, Schleifenerkennung und allem drum und dran? Shocked
Ist es dann nicht gleich noch viel langsamer?
Und wie soll ich dann z.B. einen Ausdruck umformen?

Zitat:

Ich habe kein Icq. Ich finde solche Fragen sollte man öffentlich ausdiskutieren, da je mehr Leute zusehen, desto schneller sind Fehler aufgedeckt.


Einige Fragen sollte man öffentlich Besprechen, aber ich schätze, dass ich auf diesem Gebiet als Anfänger mehr Fragen haben als interessant ist.

Gruss
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 18:17:22    Titel:

Zitat:
Ist es dann nicht gleich noch viel langsamer?


Der Vorteil ist, dass Du die Sprache sehr stark auf dein Modell optimieren kannst. Und es liegt bei Dir, wie viel Du da reinsteckst. Ich z.B. programmiere ein CAS "mit Antworten und Zwischenschritten". Für mich ist die Effizienz nur sekundär bzw. auf geringer Ebene wichtig.

Zitat:
Und wie soll ich dann z.B. einen Ausdruck umformen?


Naja. Es hängt eben von der Sprache ab. Ich habe z.B. als einzige Datenstruktur markierte Bäume. Jeder Ausdruck hat die Form

a(a1,...,an).

Und darauf sind generische Operationen, wie add,remove,assign usw. definiert. Der Vorteil liegt darin, dass das im Wesentlichen die Prädikaten-Logik-Sprache wiederspiegelt. Da schreibt man auch

*(a,^(x,3))

für ax^3. Und in meiner Sprache kann man nun jedem Operator eine Semantik (auch lokal) zurodnen, sodass was damit gemacht werden kann. Usw. usw.

Ich brüte schon seit einem halben Jahr an dem Konzept, obwohl ich seit 4 Jahren schon kommerzielle CAS programmiere.

Frage nur. Ich habe festgestellt, dass der Teufel im Detail liegt. Daher ist im Wesentlichen jedes auch noch so kleine Detail interessant.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 23 Jul 2005 - 19:20:26    Titel:

Hi,

Mein Verfahren läuft so:

Einen Ausdruck (z.B. 5.1*det([3;2;1])) parsen und in die umgekehrte polnische Notation verwandeln, damit es nachher einfach wird, ihn auszuwerten.

Beim Parsen wird jedem Operand gleich ein Datentyp zugeordnet (Nummer, Matrix, String, ...) damit man später bei der Auswertung richtig verzweigen kann. Ausserdem kann jeder Operand "Numerisch" oder "Symbolisch" sein und so gehandelt werden.

Die numerischen Operationen hab ich jetzt drin (abgesehen von den Potenzen...), und jetzt krieg ich es mit der Angst zu tun, denn jetzt kommen Umformungen auf mich zu.

Ehrlichgesagt weiss ich noch nicht so ganz wie ich das anstellen soll. Mein Vorgaben sind:
Ein Array für die linke Seite vom Operator
Ein Array für die rechte Seite vom Operator.
Im Array sind alle Elemente gespeichert die da so vorkommen.
Wenn man z.B. x/y/z*1/z eingibt, ist im linken Array folgendes zu finden:
x, /, y, /, z

Wenn du Anregungen oder Vorschläge hast, ich bin für alles offen.

Wegen der Sprache: Ich habe mir vorgestellt, dass ich eine 'kleine' Sprache mache, mit der man Funktionen schreiben kann, mehr nicht. Also generell nur: Variabeln zuweisen, Operationen/Funktionen ausführen, Schleife machen.


Gruss
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 20:06:13    Titel:

Zitat:
Wenn man z.B. x/y/z*1/z eingibt, ist im linken Array folgendes zu finden: x, /, y, /, z


Hmm. Ich komme nicht ganz drauf, wie es gemeint ist.

x/y/z*1/z = x/(y/z) * 1/z

da man bei gleichen Operatoren meistens rechtsassoziativ vorgeht. Demnach ist das ganze

x*z/(y*z)

und somit x/y, wenn man das semantisch betrachtet. Ansonsten müsste doch

x, /, (, y,/,z,),*,1,/,z

oder so stehen. Oder irre ich mich ?!
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 23 Jul 2005 - 20:08:15    Titel:

Ach noch was. Ich habe das ganz vergessen. Ich würde an deiner Stelle für den Anfang alle impliziten einfachen Umformungen vorerst stehen lassen. D.h. auch z.B. sqrt(4) nicht zu 2 umformen. Das kann man sowieso im Nachhinein machen.
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  Weiter
Seite 2 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