Un dendlich lange Zahlen, mithilfe einer verketteten Liste...

Schönen Guten N' abend zusammen!

Ich hatte vor mithilfe einer ver ketteten Liste, un endlich lange Zahlen (jaja der Speicher begrenzt alles, ich weiß^^) darzustellen, bzw. die dafür nötigen Grundrechenarten zu implementieren (Operatorüberladung). Das alles schön in einer Klasse .

Meine (erstmal theoretische) Frage ist nun: Wie kann ich wohl die Grundrechenarten (+, -, * und / ... später vielicht noch Wurzel, logarithmus, sinus, consinus, tangens) möglichst effektiv, also laufzeit-effizient, implementieren ?

Könnt ihr mir das Tipps, Hinweise, Ansätze, etc. ... geben ?

Ich will auf gar keinen Fall irgendwas fertiges (oder wenn nur 'prinzip-erklärend'), sondern will das schon selbst machen :xmas1: .

Schonmal mal vielen Dank! und viele Grüße
Simon

Maxi

also erstma... nimm KEINe verkettete liste
is schruz. listen nimmt man, wenn man zB oft elemente in der mitte des containers löschen oder hinzufügen muss. und dann is ja bei den grundrechenarten eher nicht so

machs zB so:

class zahl
{
   std::vector<unsigned int> m_digits;
};

auf dieser klasse definierst und implementierst du dann die operatoren. du arbeistest dabei dann möglichst nich im dezimalsystem (also 10 mgl. pro stelle) sondern (weiß jetzt nich wie die zahl heißt), also jedenfalls soviele möglichkeiten pro stelle wie unsigned int gibt. damit kannst dann rechnen und übertrag und so musste natürlich beachten und dann machste noch ne funktion die dir dann diese zahl als string im dezimal, hexadezimal oder osnttwas-system zurückgibt. und noch ne funktion die eben nen string im dezimalsystem einliest und in sone zahl umwandelt. und schon kanns losgehen. naja, isn bisschen arbeit, aber geht.

.filmor

Zu den trigonometrischen Funktionen ist nur noch zu sagen, dass du aufgrund ihrer Periodik das ganze nur modulo (2*)Pi bzw. (2*)180° betrachten musst, also die cmath Funktionen benutzen kannst. Das macht aber Prinzipiell trotzdem nur dann Sinn, wenn du auch Kommazahlen implementierst.
Am besten verlagerst du die Wahl des Containers auf später und benutzt ein typedef.

Werner Salomon

Simon. schrieb:

Meine (erstmal theoretische) Frage ist nun: Wie kann ich wohl die Grundrechenarten (+, -, * und / ... später vielicht noch Wurzel, logarithmus, sinus, consinus, tangens) möglichst effektiv, also laufzeit-effizient, implementieren ?

Mein Güte, ich nehme an, Du weißt nicht wie man den sinus 'zu Fuß' programmierst, aber Du weist schon, dass es auf jeden Fall möglichst effizient sein muss. Warum habt Ihr es alle so eilig?

Fangen wir mal ganz klein an

#include <vector>
class Zahl
{
public:
    Zahl operator+=( const Zahl& b )
    {
        // hier den Code hinschreiben
        return *this;
    }
private:
    std::vector< int > m_digits;
}

.. weist Du wie man den operator+= implementiert?
Der Algorithmus ist genau der gleiche der auf der Grundschule gelehrt wird.

Gruß
Werner

Ok, danke erstmal für Eure Tipps!!!

Maxi schrieb:

du arbeistest dabei dann möglichst nich im dezimalsystem (also 10 mgl. pro stelle) sondern (weiß jetzt nich wie die zahl heißt), also jedenfalls soviele möglichkeiten pro stelle wie unsigned int gibt. damit kannst dann rechnen

Verstehe ehrlich nit ganz wie Du das genau meinst. Könntest Du mir das vielleicht noch etwas genauer erklären, bitte . Hört sich nämlich gut an! Glaub das isses.

Dank Dir schonmal .

@Werner Salomon:
OMG, na klar weiß ich das, darum gehts doch gar nicht... . Es geht mehr darum, WIE ich diese Zahlen organiersiere...das alles iterativ mit Schleifen druchzugehen (damit ist jetzt aber nicht gemeint: rekursiv ist besser , in diesem Fall ) könnte bei wirklich laaaangen Zahlen^^ und komplexeren Berechnungen (sin, ...) oder verketteten gleichungen ja doch seine Zeit dauern...

Werner Salomon

Simon. schrieb:

OMG, na klar weiß ich das, darum gehts doch gar nicht... . Es geht mehr darum, WIE ich diese Zahlen organiersiere...das alles iterativ mit Schleifen druchzugehen (damit ist jetzt aber nicht gemeint: rekursiv ist besser , in diesem Fall ) könnte bei wirklich laaaangen Zahlen^^ und komplexeren Berechnungen (sin, ...) oder verketteten gleichungen ja doch seine Zeit dauern...

Ja, um das 'iterativ' mit Schleifen wirst Du wohl nicht herumkommen. Und das dauert dann bei 'wirklich laaangen' Zahlen dann auch länger.

Die Suche nach möglichst großen Primzahlen erfordert nicht umsonst massive Rechenpower.

Bei der Verwendung von std::vector< int > kann man pro Element auch Zahlen in größeren Bereichen hernehmen - z.B.: 0 bis sqrt( MAXINT ) oder so; statt der Zahlen 0 bis 9. Dann bleibt zwar die Komplexität gleich, aber absolut geht es schneller.

Bei der Multiplikation weiß ich, dass es einen Algorithnus gibt, der schneller ist als 'schriftlich multiplizieren', aber ich hab' leider vergessen wie der heißt

Gruß
Werner

PS.: heißt OMG Objekt Management Group oder "Oh mein Gott"?

@Werner Salomon: lol, ne heißt Oh mein gott^^, aber danke für deine erklärungen!
Kannst Du villeicht noch rausfinden, wie dieser Algo für die Multiplikation heißt? -Wär nett!- Oder weißt Du vielleicht, wo ich noch weitere Infos dazu finde ?

@Maxi:
Kannst Du mir das noch erläutern ? please :

Simon. schrieb:

Ok, danke erstmal für Eure Tipps!!!

Maxi schrieb:

du arbeistest dabei dann möglichst nich im dezimalsystem (also 10 mgl. pro stelle) sondern (weiß jetzt nich wie die zahl heißt), also jedenfalls soviele möglichkeiten pro stelle wie unsigned int gibt. damit kannst dann rechnen

Verstehe ehrlich nit ganz wie Du das genau meinst. Könntest Du mir das vielleicht noch etwas genauer erklären, bitte . Hört sich nämlich gut an! Glaub das isses.

Dank Dir schonmal .

*push*

Maxi

naja, weiß nich was ich da noch erklären soll. ein bisschen nachdenken musst du ja selber, du willst es ja schlieslich auch selber machen.
Also:
Dezimalsystem: Jede stelle hat 10 Möglichkeiten -> mit n stellen kann man zahl von 0 bis 10^n - 1 darstellen.
Hexadzimalsystem: jede stelle 16 möglichkeiten -> 16^n - 1 zahlen bei n stellen
"maxint"-system: jed estelle 2^32 möglichkeiten (bei 32-bit int),

anstatt dass du im dezimalsystem rechnest, rechnest du eben in dem letzten system. ERegeln bleiben ja die selben mit übertrag und so

Werner Salomon

Simon. schrieb:

@Werner Salomon: lol, ne heißt Oh mein gott^^, aber danke für deine erklärungen!
Kannst Du villeicht noch rausfinden, wie dieser Algo für die Multiplikation heißt? -Wär nett!- Oder weißt Du vielleicht, wo ich noch weitere Infos dazu finde ?

Tut mir leid, ich hab's nicht wiedergefunden. Aber vielleicht fragst Du mal in der de.sci.mathematik nach. Ich kann mir gut vorstellen, dass Dir da geholfen wird.

Gruß
Werner