Mathematische Funktionen einfügen

  • Guten Tag!


    Benutzt man die Sufu zu dem o.g. Thema, so kann man zwar ein paar wenige Infos erlangen, jedoch fehlt hierfür ein Tutorial oder ähnliches. Meine konkrete Frage: Wie kann ich einen mathematischen Zsmhg (z.B. 3x³+2x²+7 o.Ä.) in die Rom einfügen und in Scripten/Routinen benutzen? Soweit ich es verstanden habe, müssten die Grundkonstrukte der meisten Funktionen (kubisch, exponential...) als BIOS Funktionen hinterlegt sein, stimmt das? Danke für Eure Hilfe!

  • Ich glaube, ich verstehe nicht so ganz, was du meinst, aber je nachdem was du modellieren willst, lässt sich das doch auch einfach mit arithmetischen Grundfuntkionen bauen. Das geht natürlich nicht mehr, wenn du irgendwelche komplizierten Terme hast, die kann man auf so einer Hardware wie dem GBA höchstens aproximieren.


    Die Funktion oben lässt sich z.B. recht einfach darstellen:


    Code
    1. u32 f(u32 x){
    2. return 3*x*x*x + 2*x*x + 7;
    3. }

    Bzw. das macht ein moderner C Compiler (Mit höchster Optimierung) daraus:


    Hier wird das Argument (x) in r0 übergeben und anschließend die Funktion in relativ wenigen Opcodes berechnet. (Kannst ja mal versuchen, nachzuvollziehen, wieso das funktioniert)


    Schwieriger wird es für Funktionen wie sin(x) oder z.B. natürliche Exponentialfunktion oder den natürlichen Logarithmus, Wie man sowas effizient berechnet, damit beschäftigt sich u.a. die Numerik, ein Teilgebiet der Mathematik.


    Ich hoffe damit kannst du was anfangen :)


    ~Sturmvogel


    Let the old ways live and prosper in the hearts of our young


  • Zunächst danke für die Hilfe! Leider ergibt sich, wenn ich versuche den Code nachzuvollziehen nicht das gewünschte Ergebnis... Daher würde ich mir wünschen dass du mich korrigierst:

    (So wie ich es verstehe unter der Annahme r0=x)

    Code
    1. r2=x
    2. r3=2x
    3. r3=2x+x=3x
    4. r1=3x+2
    5. r3=3x+2
    6. r3=(3x+2)²=9x²+12x+4
    7. r0=x*(9x²+12x+4)=9x³+12x²+4x
    8. r0=9x³+12x²+4x+7
    9. bx lr

    Ich schätze mal, dass man Vorgehen da falsch ist... Das Suffix S aktualisiert so wie ich das verstanden habe nur die benutzten Register oder? Weiterhin hat mich verwundert, dass der mul-Befehl nur 2 Argumente hatte, weshalb ich annahm, dass das Zielregister dasselbe ist wie das erstgenannte (sprich: mul r1,r2 würde bedeuten: r1=r1*r2)

    Sorry für mein Unverständnis?(

  • Hi, also zuerst, tut die Funktion von Sbird schon, was sie soll:

    Wenn du aber Polynome implementieren willst, wirst du sehr schnell auf Probleme stoßen. Terme von höherem Grad wachsen sehr sehr schnell (also alles über Grad 3 wird dir durch die Decke schießen und damit für 32-bit Integer nicht mehr greifbar). In dem Fall solltest du auf floats zurückgreifen. Für Polynome gibt es zur effizienten Berechnung außerdem das Horner-Schema (siehe Wikipedia).


    Für exp, sin, etc. gibt es im GBA-BIOS nur bedingt support: Das heißt, nur der Arcustangens ist implementiert (als Funktion, die auf fixed point 32-bit Werten mit 16-bit Integer und 16-bit fractional arbeitet. Für die fehlenden Funktionen würde ich auch von den meisten Reihendarstellungen abraten, da sie langsam konverigeren und v.a. Taylor-Reihen auch Terme mit hohem Grad einführen (die das gleiche Problem haben, wie bereits zuvor beschrieben).


    Ich kann dir sagen, wie ich es gelöst habe, und bin damit eigentlich recht zufrieden:

    Für trigonometrische Funktionen (sin, cos, tan) habe ich sogenannte Lookup-Tables (kurz LUT) verwendet, wo für bestimmte Eingaben die Ausgabe einfach hinterlegt ist. Für Eingaben, die nicht in der Tabelle vorhanden sind, kann man einfach zwischen den beiden Werten interpolieren (also einfach eine Gerade durchlegen und das ausrechnen). So verhindert man integer-overflows bei der Taylor-Darstellung der trig-Funktionen.


    Logarithmus arbeitet mit Potenzgesetzten, sodass die Eingabe zuerst ins Interval [1;2] transformiert wird. Danach wird in diesem Fall die logarithmus-Funktion mit einem Polynom fünften Grades approximiert. Auch hier sind die Funktionswerte sehr gut. Meine Implementierung findest du hier. Wenn du bessere Lösungen findest, scheu dich nicht, sie vorzuschlagen.

  • Falls man 64 Bit Ergebnisse braucht, kann man auch ins ARM Instruction Set wechseln und dort nen SMULL machen. Addieren auf das 64 Bit Ergebnis selbst geht auch noch (untere 32 Bits addieren, danach obere 32 Bits mit Übertrag addieren). Im ARM Instruktionsset gibts für beides zusammen auch die Instruktion SMLAL. Falls du C programmierst, kannst du auch einfach int64_t verwenden.


    Wenn du das danach in dein Skript integrieren willst musst du halt die Parameter irgendwie über vars übergeben bzw abrufen. Hängt dann aber natürlich ab, was du genau mit dem Ergebnis vorhast.

    PS: Falls du mal einfache Sachen in C coden willst, dir aber keinen Compiler aufsetzen willst, kannst du dashier verwenden: https://godbolt.org/
    Da einfach beim Compiler "arm gcc X.Y (none)" auswählen und als Parameter "-O2 -mthumb".

    Du möchtest mich mal treffen? Dann sag hallo und besuche mich an der FAU in Erlangen.

    Einmal editiert, zuletzt von ipatix ()

  • Eine lookup-table hält die Werte einer Funktion für bestimmte Eingaben. Eine einfache LUT für Sinus wäre:

    Code
    1. float sin_lut[4] = {0.0, 1.0, 0.0, -1.0}; // Hält Werte für Eingaben 0, pi/2, pi, 3pi/2

    Wenn ich jetzt die Sinusfunktion implementieren will, kann ich einfach linear zwischen zwei Funktionswerten interpolieren.

    Code
    1. float sin(float x) {
    2.     // Es wird angenommen, dass 0 <= x < 2pi
    3.     int lut_idx = (int) (4 * x / (2 * pi)); // Finde den letzten Index, der <= x ist
    4.     float y0 = sin_lut[lut_idx]; // Wert der Sinusfunktion am letzten Index <= x
    5.     float y1 = sin_lut[(lut_idx + 1) % 4]; // Wert der Sinusfunktion am ersten Index > x (Nutze modulo 4, weil der Sinus zyklisch ist)
    6.     float dy = y1 - y0;
    7.     float dx = 2 * pi / 4;
    8.     float a = dy / dx;
    9.     return y0 + a * (x - x0);
    10. }    

    Bildlich passiert folgendes (Achtung, schreckliche Grafik folgt):




    Blau der Graph der Sinusfunktion. Vier sogenannte Stützstellen werden verwendet (bei 0, pi/2, pi und 3pi/2). Zwischen den Stützstellen legen wir Geraden, um die Sinusfunktion zu approximieren. Wenn wir jetzt sin(x) ausrechen wollen, müssen wir:

    a) Die richtige gerade finden (die Stützstellen, zwischen denen x liegt (x0 und x1).

    b) Dann rechnen wir die Geradensteigung aus (y1 - y0) / (x1 - x0) = a

    c) Wir benutzen die Geradengleichung y = mx + t, um sin(x) abzuschätzen (wichtig ist, das x jetzt relativ zu x0 liegt, also verschoben werden muss)
    -> sin(x) ~= y0 + (x - x0) * a


    Wichtige Punkte, die zu beachten sind:

    1. Wie finden wir allgemein heraus, was x0 und x1 sind (im Hinblick auf indizes in der LUT)?

    Idx_x0 = #Stützstellen * x / Größe_des_Intervals
    idx_x1 = idx_x0 + 1


    2. dx = x1-x0 = Größe_des_Intervals / #Stützstellen ist konstant


    3. Je mehr Stützstellen man verwendet, desto genauer wird die Approximation. Ich verwende z.B. 512 Stützstellen. Wie man im Bild sieht, ist die Gerade nicht unbedingt die genauste Approximation.


    4. Es gibt weitaus bessere Verfahren zur Interpolation (so heißt das ganze Verfahren), z.B. kubische Splines. Da wird zwischen die Stützstellen keine Gerade, sondern ein kubisches Polynom dritten Grades gelegt und zwar so, dass an den Stützstellen selbst, zwei aneinandergrenzende Teilfunktionen auch die gleiche Ableitung haben (der Graph also nicht solche Knicke wie im linearen Beispiel macht). Man sollte sich allerdings immer fragen, inwieweit so etwas im Kontext eines PKMN-Games wirklich sinnvoll und notwendig ist (die kubischen Splines sind deutlich aufwändiger zu implementieren).

  • Ja das vorgehen bei einer Interpolation (und Spline-Interpolation) hatten wir auch im Unterricht (natürlich in einem anderen Zsmhg:D). Dabei war das ganze selbstverständlich rein mathematisch betrachtet und nicht im Kontext von Routinen oder ähnlichem (Matheunterricht halt). Muss denn zwingend interpoliert werden, um die LUT nutzbar zu machen? Oder kann ich auch einfach eine funktionsgelöste Tabelle entwerfen die jedem x-Wert einen y-Wert zuordnet (ohne dabei zB in etwa kubisch zu verlaufen)? Sprich jeweils zwei Wertepaare (am bestem mit Brüchen) die quasi solange abgesucht werden, bis das entsprechende gefunden wurde? Woher ist zB in deinem ersten Code klar, dass die angegebenen Funktionswerte zu der Eingabe 0, pi/2 etc. gehören?

    P.S. Vielen Dank für deine Mühe, der Abschnitt war sehr gut erklärt!

  • Naja, je größer die LUT, desto weniger machbar wird das Verfahren, einfach die Tabelle abzusuchen. Ich weiß nicht, ob dir Komplexitätstheorie etwas sagt, aber in dem Fall hätte die Sinusfunktion lineare Laufzeit (O(n)), d.h. der Rechenaufwand steigt linear mit der Größe der LUT. Wenn du dagegen den Index in der LUT "berechnest", geht es viel schneller (konstante Laufzeit, unabhängig von der LUT-Größe -> O(1)).


    Jeden Wert in eine Tabelle packen ist auch sehr schlecht machbar, nachdem es unendlich viele rationale / reelle Zahlen zwischen [0;2pi) gibt.

    Den Index eines x-Werts in der LUT kannst du ja auch sehr leicht ausrechnen. x * #Elemente in der LUT / | LUT Intervall |. Und stückweise lineare Interpolation liefert dabei schon sehr gute Ergebnisse. Wenn du sehr genau sein möchtest, nimmst du halt z.B. 2048 Stützstellen her.


    Für die Sinusfunktion gibt es außerdem noch einen Trick: Selbst im Intervall [0;2pi) braucht man nicht alle Stützen, da man die Sinusfunktion durch Spiegelung erhalten kann, wenn man nur das Interval [0;pi/2) interpoliert. Das habe beispielsweise ich so implementiert. Ich interpoliere sin(x) im Interval [0;pi/2) und benutze dann horizontale/vertikale Spiegelung, um auch das Interval [pi/2;2pi) abzudecken.

    Den Kosinus kannst du dann auch über die Identität cos(x) = sin(x - pi/2) implementieren. Den Tangens über tan(x) = sin(x)/cos(x) = sin(x) / (sin x - pi/2).

  • Du musst nicht interpolieren, vergrößerst dabei aber den Fehler enorm, v.a. in Relation auf die Größe deiner Tabelle. Außerdem ist eine lineare Interpolation selbst auf dem GBA in annehmbarer Zeit durchgeführt. Probleme bekommst du vermutlich mit der floating point Arithmetik, die ist auf einem so alten Prozessor sehr teuer, weil es dafür keine Hardware gibt.


    Was ich nicht ganz verstanden habe ist, was du mit "jedem Wert" meinst, denn der Sinus ist für alle reellen Zahlen definiert, selbst wenn du nur das Intervall [0;pi] betrachtest, woraus du den Sinus vollständig beschreiben kannst, brauchst du eine unendlich große Tabelle. Theoretisch könntest du eine Tabelle für alle nach IEEE float/double definierten Zahlen in dem Intervall erstellen, aber das ist selbst auf moderner Hardware Irrsinn, weil die Genauigkeit selbst einfacher Methoden wie linearer Interpolation mehr als hinreichend sind, um die meisten Aufgaben zu bewältigen. Selbst eine LUT mit "nearest neighbor" interpolation (Also eine links/rechtsstetige Treppe) wird vermutlich, sofern groß genug, ausreichen, wenn du das nicht gerade brauchst um analytisch exakte Ausdrücke darzustellen.


    ~Sturmvogel


    Let the old ways live and prosper in the hearts of our young


  • Leider hilft die Sinusfunktion mir in meinem konkreten Fall (glaube ich) nicht. Hab mit meinem GTR/CAS mal verschiedene Funktionstypen durchgespielt, die meine gesuchten Wertepaaren am besten approximieren und die beste Darstellung bietet: f(x)= -7,5E-7*x^3+4,7E-5*x^2+1,2E-2*x+0,73

    Leider ist die Funktion mit vielen Nachkomma stellen gesegnet und ich bin mir nicht scher, ob das im Spiel richtig verarbeitet wird. Kann man eine solche Funktion auch mit einem C-Compiler in eine Routine umwandeln? [Wenn ja wie?]

    Oder bietet sich hier auch mehr eine Interpolation an?

  • Um das ganze mal zu konkretisieren, was willst du denn erreichen? Das da oben ist ein ziemlich krummes Polynom mit einer Maximumsstelle bei ~ 100, also irgendwas mit Levelkurven?


    Im Endeffekt kannst du das natürlich approximieren, LUTs verwenden, etc. Gerade wenn es nur um Werte für die ersten, natürlichen Inputs geht, wird die LUT nicht einmal groß werden, und du brauchst theoretisch gar nichts mehr interpolieren, weil du ja alle Werte darstellen kannst.


    Wenn es doch um irgendwas anderes geht, und du auch rationale/reelle Eingabewerte hast, kannst du immer noch anfangen, linear zu interpolieren, wobei hier vermutlich kubische Splines wirklich bessere Werte liefern könnten. (Nicht, dass das notwendig wäre, je nach Anwendungsfall)


    ~Sturmvogel


    Edit: Wenn es wirklich um EXP Kurven geht, kannst du ja auch einfach mal versuchen, ein paar Fixpunkte zu setzen und dann dazwischen eine Funktion zu interpolieren^^


    Let the old ways live and prosper in the hearts of our young


  • Das Ganze soll als Multiplikator fungieren :) Mit welchem Programm kann ich denn (entsprechend deiner ersten Antwort) eine Funktion in eine Routine umwandeln? Und was bedeutet in dem Zsmhg das u32? Ich glaube nämlich wenn das mit meiner Funktion gehen würde wäre das der Weg, der mir am genehmsten ist...

  • Hey, also zuallererst, das was Wodka und Ich hier schreiben, ist C Code, also Programmcode. Der kann von einem C Compiler nach Assembly kompiliert werden. Nachdem du ARM/Thumb Code erzeugen willst, brauchst du einen ARM C Compiler, beispielsweise arm-gcc. Eine Version dieses Compilers ist in Devkit Pro vorhanden: https://github.com/devkitPro/installer/releases


    Zum "ausprobieren", was der Compiler mit deinem C Code tut, kannst du einen Compiler Explorer, z.B. Godbolt verwenden: https://godbolt.org/z/jMrO6R


    u32 ist der (selbst definierte) Datentyp. Es hat sich in der RH Szene eingebürgert, u32/u16/u8 für unsigned integer, short, byte zu verwenden, bzw. s32, s16, s8 für die Typen mit Vorzeichen, in dem godbolt example oben siehst du diese Definitionen auch. Das ist im Endeffekt alles Kram aus der C Syntax. Im Normalfall würden solche Definitionen dann in einer eigenen Datei stehen, und als Header inkludiert.


    Es gibt auch ein Tutorial, wenn man sich damit ein wenig mehr beschäftigen möchte: Programmieren für den GBA (Auch wenn du, zumindest für den Anfang, vllt nicht unbedingt ein Makefile verwenden willst, wie in dem Tutorial erklärt)


    ~Sturmvogel


    Let the old ways live and prosper in the hearts of our young