Include - Dezimalzahlen (unlimitiert)

[STARGÅTE]

@CSHW89

Kein Problem, ich selber finde auch oft Beiträge, wo auch sowas gemacht wurde, in der einene oder anderen Variation.

"is ja meine Funktionen schneller"

Vielleicht:
Hier meine Aktuellen Daten, in MikroSekunden (10^-6 Sekunden) (also nicht Milli ^^)

Rechenzeit einer Operation mit zwei Zahlen
Zahlenlänge (Dezimalsystem) von Links nach Rechts : 100-Stellig; 1'000-Stellig; 10'000-Stellig
-----
Plus (Addition) : 1,37µs ; 10,2µs ; 99,5µs
Times (Multiplikation) : 12,6µs ; 1'015µs ; 100'900µs
-----
Intel Core 2 Duo , 2.2 GHz

Im übrigen war ich erstaunt, als ich in Mathematica getestet habe wie viel Speicher 10^100'000 frist: 41552 Bytes
bei mir sind es nur 16 Bytes, da ich Nullen am ende Kürze, dafür habe ich meine Magnitude.

[CSHW89]

Im übrigen war ich erstaunt, als ich in Mathematica getestet habe wie viel Speicher 10^100'000 frist: 41552 Bytes
bei mir sind es nur 16 Bytes, da ich Nullen am ende Kürze, dafür habe ich meine Magnitude.

Ich denke mal, das liegt daran, dass die Zahl nicht als Decimal-Zahl gespeichert wird, sondern als Dual-Zahl. Ich kanns jetzt nicht testen, aber versuchs mal mit 2^100'000 in Mathematica oder so.

lg kevin

[STARGÅTE]

Hier mal ein paar Vergleiche:
Links ich, Rechts Mathematica

2^100'000 :: 13'392 Bytes ; 12'528 Bytes
10^100'000 :: 16 Bytes ; 14'552 Bytes
16^100'000 :: 53'532 Bytes ; 50'032 Bytes

Scheinbar speichern die völlig anders ...

Aber es sieht danach aus, als würden sie die vollen LONG-Bits ausnutzen!
Ich mache ja schon bei 1'000'000'000 einen übertrag, obwohl noch etwas platz wäre ^^

[CSHW89]

so, hab mal jetzt n speedtest von den grundfunktionen gemacht. die methoden scheinen sich kaum was zu nehmen, bis auf DIVISION. aber schau mal selbst (angaben in ms, links meine, rechts deine Funktionen):

Code: Alles auswählen

Val: 0 - 79
Add: 0 - 0
Mul: 153 - 234
Div: 125 - 6078
Str: 78 - 78

Zur erklärung: hab einen String mit 20000 und einen mit 5000 ziffern genommen (damit auch die division ausgeführt wird). Bei der Division hab ich 'Precision' auf 0 gesetzt.

Hab mir mal die Division von dir kurz mal angeguckt. du arbeitest da mit strings. wahrscheinlich ist es deshalb so langsam. aber so, manoman. hät ich jetzt echt nicht so erwartet.

naja, hab also doch ein grund weiter zumachen . werd mal in den nächsten tagen, das was ich bisher hab, hier im forum reinstellen.
lg kevin

[STARGÅTE]

Jo die Division ist das Problem-Kind ^^

Dort habe ich in der Version hier hier zur Zeit online ist, am wenigsten Optimiert.

Dort arbeite ich halt wirklich noch mit der Schulmethode (schriftliches Dividieren)
das ist bei gleichgroßen Zahlen schneller

Aber mich wundert es sehr, wieso bei dir die Division schneller ist als die Multiplikation ...
Selbst bei Mathematica ist eine Division langsammer als eine gleichwertige Multiplikation...
Soll heißen *0.5 ist normalerweise immer schneller als /2 ...
Weil bei /2 entwerden "dividiert" wird, oder vorher 2^-1 berechnet wird ...

Kannst du mir vllt kurz erklären wie es bei dir abläuft ... `?
Meins siehst du ja ...
- Erst werden alle 9 Vielfachen des Divisor errechnet
- Dann wird bestimmt welches Vielfache zuerst die Zahl überschreitet
- dann werden die Ziffern zusammen gesetzt.

Dort erklärt es sich auch warum es so viel langsammer ist, weil ich nicht 9er Packen habe, sonden immer 1er schritte gehe.

Das ist das ergebnis "zusammen baue" aus Strings ist aber nciht der Hauptgrund der Langsamkeit.

Am spannensten wäre es ob und wie du Power() mit gebrochenen und negativen Zahlen ermöglichst ...
Würdest du da wirklich auf die Darstellung:
a^b = Exp(a*Ln(b)) gehen und Exp() und Ln() als reihen entwickeln ?

[CSHW89]

also Exp() und Ln() wollt ich auf jeden fall mit reihenentwicklung lösen. bin auch grad dabei, exp() will ja nicht genau genug. scheint iwo doch noch in den grundfunktionen ein fehler zu sein. also ich denke, es liegt daran. bei Pow() bin mir noch nicht sicher, aber alles andere als Exp(a*Ln(b)) für a^b wäre denk ich doppeltgemoppelt.

so zum vergleich zwischen Mul und Div: ich denk, das kann man nicht vergleichen. bei der multiplikation ist ja das ergebnis viel größer als bei der division. wenn ich also bei der division nur bis zum komma rechne, muss ich effektiv weniger berechnen.

nun zu Div, naja ist mein geheimnis . nein, hm, muss sagen, ist auch nicht auf mein mist gewachsen. hab ich aus 'java.math.MutableBigInteger' die methode 'divide'. allerdings musste ich es etwas umschreiben, weil auch java die Longs komplett nutzt, nicht nur bis 1'000'000'000.
ist jetzt schwer zu erklären, kannst dir ja dann mein code ansehen, wenn ich ihn öffentlich mache. aber hier mal ne kurze idee dazu:

- Divisor norminieren (keine Nullen vorne)
- Die ersten zwei Longs vom Divident durch das erste Long vom Divisor teilen (geht ja mit quad). Ist eine wirklich gute annäherung. ist glaub ich nur maximal 1 oder 2 daneben, wenn halt der restliche Divisor zu groß ist. das kann man korrigieren, wenn man den Divident neu berechnet (also Divident - Divisor*x). wenn dort ne negative zahl rauskommt, addiert man einmal den Divisor zum Divident, und x ist um 1 kleiner.

lg kevin

[Josh]

ich weiß nicht, ob es allgemein was bringt, aber vieleicht sollte man auch ein paar sonderfälle wie z.b. die /7 regel (keine ahnung ob es da noch mehrere gibt) berücksichtigen.

[STARGÅTE]

Hm also auch bei Dividieren nutzt du schon ein näherungsverfahren ...

Das problem das ich gerade sehe ist.
Wenn ich wirklich echte Dezimal zahlen habe, könnte man eine Division von u.u. unendlich lange fortsetzen.
Klar irgendwann muss man abbrechen.
Das habe ich halt mit 'Precision' nud *Rest erledigt, sodass "nix verloren geht".

Ich habe nun das Schriftliche Dividieren genomen, weil ich dort zu 100% sicher sein wenn ich:
R = A * B rechne
und dann
R / B dividieren.
genau A rauskommt. Und zwar bei jedem A und B (also auch gebrochen) wirde die Division wirklich echt enden.
Sobalt ich aber ein näherungsverfahren verwenden, kommt immer eine ungenauigkeit rein, sodas die Division nicht mehr alleine abbricht, sonden immer "von mir" gestoppt werden muss, (abbruch der rekursion)



Das gleiche taucht bei Power() auf ...
Exp(a*Ln(b)) ist vermutlich die einzige Variante, welche man aber nur bei gebrochenen Exponenten nutzen sollte!

Das problem bei EXP(x) ist, dass in der Reihenentwicklung x selber lange mit sich selbst multipliziert werden muss.
Um dort eine gute näherung zu bekommt ...
Sonst bekommst du bei großen x-Werten Müll raus ... man darf da halt wirklich erst abbrechen, wenn die Fakultät im Nenner groß gegen über der Potenz im Zähler wird...


Ich glaube ich werde für mein Include anfagen müssen "Zweigleisig" zu arbeiten.
Also fast alle Operationen jeweils als genaues Verfehren anzubieten, oder als Näherungsverfahren.

Vorallem das Wurzelziehen, wo ich derzeit das Heronverfahren verweden, geht auch in die Kaputt, wenn der Wurzelexponen zu groß wird ...


An was ich beim Dividieren auch gedacht habe ist aus: (vereinfacht) 27 / 3 sowas zu machen: 27 * (1/3)
1/3 geht schnell zu berechnen, aber wenns halt n Periode hat, dann würde bei einer multiplikation nie wieder 27 rauskommen, sonden 26,999999999 ...

Naja, bin aufjedenfall schon gespannt dein Include zu sehen ...

@Josh

naja aber die 142857 Periode, taucht ja wirklich nur bei /7 auf
und wie oft dividiert man schon duch 7 ^^


EDIT:
Es muss überall heißen : a^b = EXP(b*Ln(a))
hatte mich verschrieben!