DIV and MOD

[sirius]

Ja meine ich...

Stringoperationen sind nicht die schnellsten, ... hmm schwer da ne Aussage zu treffen. Das müsste man testen.

[Khabarakh]

[OT]

Zitat:

Zitat von sirius

günstiger für die FPU wäre IMHO x^y = 2^(x*lb(a)).

Nachdem ich einmal so frei war, auf der rechten Seite deines Terms x durch y und a durch x zu ersetzen :mrgreen: (und natürlich den ld durch ln x / ln 2), blieb der Basis-2-Ansatz 5% hinter dem ersten zurück. Lassen wir den kürzeren Code gewinnen :zwinker: .
[/OT]

@dajuhsa: Vielleicht bin ich in der Minderheit, aber ich würde als 1. Ziffer jene am Weitesten rechts bezeichnen, da ihre Wertigkeit die niedrigste ist. Vor allem aber sparst du dir mit dieser Zählweise den IntToStr-Aufruf ;) (den man sowieso wieder durch einen eleganteren Logarithmus ersetzen könnte, aber das nur am Rande; denn in Punkto Performance ändert sich nichts).

[sirius]

Zitat:

Zitat von Khabarakh

Nachdem ich einmal so frei war, auf der rechten Seite deines Terms x durch y und a durch x zu ersetzen :mrgreen:

Nach 10 Uhr sollte man in meinem Alter keine Mathematik mehr machen :oops:

Zitat:

Zitat von Khabarakh

(und natürlich den ld durch ln x / ln 2)

Na, das war ja nicht der Sin (aus zwei Funktionen drei Funktionen machen). Das dauert natürlich länger. Es geht darum, dass in der Zeit, in der man einmal exp(x) rechnet, man bereits komplett a^b hätte rechnen können (siehe dein anderer Thread).

Trotzdem ist man wenn man 10^N (im Bereich integer) rechnet, mit einer For-Schleife oder besser noch mit einem vorbelegten array besser dran (wenn man schon abkürzen will)

[xZise]

Hi @ all,
ich habe mich auch mal mit dem Thema auseinader gesetzt und habe eine "IntLength"-Funktion entworfen, welche ohne strings die Länge eines Integers bestimmen kann.

Delphi-Quellcode:

function IntLength(AInt : Integer) : Integer;
begin
  Result := 0;
  while AInt > 0 do
  begin
    AInt := AInt div 10;
    inc(Result);
  end;
end;

Ich habe mal ein Test gemacht: Bei mir braucht die string-Variante für 900.001 Durchläufe ~ 255 ms. Die IntLength-Variante jetzt schon nur ~ 188 ms.
Vielleicht kennt ihr eine Möglichkeit den obigen Code zu optimieren ;) Vielleicht mit ASM? Da müsste ich aber passen :) da für mich ASM im FoW liegt xD
Zusätzlich hier meine ExtLength-Variante:

Delphi-Quellcode:

function ExtLength(AExt : Extended) : Integer;
begin
  Result := IntLength(Trunc(AExt));
end;

Sie berechnet leider nicht die Nachkommastellen, allerdings weiß ich nicht ob man die mitdazu rechnet.
Ich werde mir mal überlegen wie man das hinkriegen könnte.

[edit]Ich habe mir jetzt mal überlegt: Ich könnte die Vorkommastellen abschneiden und dann solange multiplizieren bis ich keine Nachkommastellen mehr habe.
Also habe ich das so gelöst:

Delphi-Quellcode:

{ Returns the length of a float (e.g. ExtLength(4365.87) = 6) }
function ExtLength(AExt : Extended) : Integer;
var
  ABuf : Extended;
begin
  Result := IntLength(Trunc(AExt));
  ABuf := AExt - Trunc(AExt);
  while Trunc(ABuf) < ABuf do
  begin
    ABuf := ABuf * 10;
    inc(result);
  end;
end;

Das Problem scheint zu sein, dass ABuf nicht genau eine Ganzzahl ist. Deshalb klemmt er sich da in eine Endlosschleife. (Wenn Trunc(ABuf) = 87 und ABuf 87 ist, beendet er nicht die Schleife)[/edit]

MfG
xZise

PS: string: ~437 ms; extLength: ~250 ms

[Khabarakh]

Die Länge der Nachkommastellen kannst du nicht wirklich ermitteln, da du dort bei so gut wie jedem Wert auf eine Periode stoßen wirst - schließlich untersuchst du die Zahl zur Basis 10, gespeichert wird sie aber zur Basis 2. Du müsstest die Zahl erst in einem sinnvollen Maße runden, genau so, wie es FloatToStr macht.

[edit]Du kannst ja noch den mathematischen Weg testen. Wird wohl irgendwo zwischen den beiden anderen Methoden liegen.

Delphi-Quellcode:

function IntLength(const aInt : Integer) : Integer;
begin
  Result := Ceil(Log10(aInt)); // bzw. Trunc(Ln(aInt) / Ln(10)) + 1
end;

[/edit]

[xZise]

Zitat:

Zitat von Khabarakh

Die Länge der Nachkommastellen kannst du nicht wirklich ermitteln, da du dort bei so gut wie jedem Wert auf eine Periode stoßen wirst - schließlich untersuchst du die Zahl zur Basis 10, gespeichert wird sie aber zur Basis 2. Du müsstest die Zahl erst in einem sinnvollen Maße runden, genau so, wie es FloatToStr macht.

[edit]Du kannst ja noch den mathematischen Weg testen. Wird wohl irgendwo zwischen den beiden anderen Methoden liegen.

Delphi-Quellcode:

function IntLength(const aInt : Integer) : Integer;
begin
  Result := Ceil(Log10(aInt)); // bzw. Trunc(Ln(aInt) / Ln(10)) + 1
end;

[/edit]

Naja... Die erste Variante braucht zwar weniger Zeit, aber auch die math-Unit, welche ja versucht wird zu verbannen ;)
Und das Ceil ist ja nichts anderes als "Trunc() + 1" oder?

Meine Frage ist, wo kann man den Logaritmus so optimieren (in richtung Log10) gegenüber ln? Weil an sich machen ja beide das gleiche (Also das bei Ceil() und Trunc()).

Und zu den Extended: Da müsste man sich also mit den Vorkammastellen zufriedengeben... Oder?

[edit]Ehm...
Trunc() + 1 ist bis zu 100 ms schneller als Ceil() o.O

Delphi-Quellcode:

function IntLength3(const aInt : Integer) : Integer;
begin
  Result := Trunc(Log10(aInt)) + 1; // bzw.  Trunc(Ln(aInt) / Ln(10)) + 1;
end;

Das ist der gewinner mit nur 79 ms um 900.000 berechnungen durchzuführen![/edit]

[edit]Wenn man nur die Log10()-Methode aus der math.pas kopiert funktionierts auch ohne uses. Aber ich glaube Borland sieht das nicht gerne oder? Vielleicht könnte man es legalisieren?[/edit]

[FAlter]

Hi,

Zitat:

Zitat von [user

xZise[/user]][edit]Wenn man nur die Log10()-Methode aus der math.pas kopiert funktionierts auch ohne uses. Aber ich glaube Borland sieht das nicht gerne oder? Vielleicht könnte man es legalisieren?[/edit]

Evtl. von FreePascal/Lazarus kopieren?

Mfg
FAlter

[Khabarakh]

Zitat:

Zitat von xZise

Meine Frage ist, wo kann man den Logaritmus so optimieren (in richtung Log10) gegenüber ln?

Hast du wirklich gemessen, dass Log10 schneller ist als Ln? Bei dem zweiten Ansatz kommt schließlich noch die Division hinzu.

Zitat:

Und zu den Extended: Da müsste man sich also mit den Vorkammastellen zufriedengeben... Oder?

Fällt dir ein Problem ein, das die Anzahl der Nachkommastellen benötigt? Mir jedenfalls nicht. Dass nur für die Vorkammastellen ein mathematischer Operator (eben log10) existiert, spricht auch dafür, dass das Ermitteln der "letzten Nachkommastelle" unwichtig ist.

Zitat:

Trunc() + 1 ist bis zu 100 ms schneller als Ceil() o.O

Jopp, in Ceil steckt noch ein wenig mehr Logik, als ich dachte. Weshalb es sogar falsche Ergebnisse liefert *g* . Trunc() + 1 ist also die schnellste und einzige richtige Lösung.

Zitat:

[edit]Wenn man nur die Log10()-Methode aus der math.pas kopiert funktionierts auch ohne uses. Aber ich glaube Borland sieht das nicht gerne oder? Vielleicht könnte man es legalisieren?[/edit]

Ich denke, diese 5 Zeilen Asm kann man als "offenes Geheimnis" bezeichnen ;) . Dürfte so auf der Schöpfungshöhe von RadToDeg liegen.

[xZise]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von xZise

Meine Frage ist, wo kann man den Logaritmus so optimieren (in richtung Log10) gegenüber ln?

Hast du wirklich gemessen, dass Log10 schneller ist als Ln? Bei dem zweiten Ansatz kommt schließlich noch die Division hinzu.

Naja. Kommt auf die sichtweise drauf an.
Ob log10 schneller als ln ist, weiß ich nicht.
Aber es gilt ja:

Code:

log10(X) = ln(X) / ln(10)

Also müsste man sagen: Das "ln"-Konstrukt ist langsamer als log10 liefert aber gleiche Ergebnisse. Und rein theoretisch müssten beide Operatioen gleich schnell ablaufen, da ich, um log10 zu simulieren, das "ln"-Konstrukt verwenden würde.
Aber den scheint nicht so zu sein, oder Borland hat den log10-Algorythmus optimiert, weil ja die... ehm Basis? ... immer gleich ist, und man irgendwo kürzen könnte.

Ich weiß aber nicht, ob sie auch einfach ein anderen Rechenweg verwenden.

Wegen Lazarus/OpenPascal: Ich besitze es nicht :) und kann deshalb auch keine aussage darüber machen.
Und nur deshalb das zu downloaden wäre etwas zu overkill :) Vielleicht gibt es jemand anderen, der den log10-Algorythmus posten kann. Ich könnte den in den Testprogramm integrieren.

MfG
xZise

[edit]omfg ... sry, aber es steht ja als Kommentar da:

Delphi-Quellcode:

{ Log.10(X) := Log.2(X) * Log.10(2) }

Meine, zwar noch auf math basieren, aber ggf. bald nicht mehr:

Delphi-Quellcode:

function Log10(const X : Extended) : Extended;
begin
  Result := Log2(X) * LogN(10, 2);
end;

[/edit]

[sirius]

Zitat:

Zitat von xZise

Code:

log10(X) = ln(X) / ln(10)

Und z.B. :mrgreen: :

Code:

ln(x)=log10(x) / log10(e)

Und nun? Das kann man immer weiter fortsetzen mit jeder beliebigen Basis

Es geht doch in dem Fall darum, was die FPU am schnellsten kann.

Du hast neben den 4 Grundrechenoperationen folgendes zur Verfügung:
- a * log2(b)
- (2^a) - 1 für -1 <= a <= +1
- a*2^(int(b))
Und natürlich noch runden, trigonometrische Funktionen und noch folgende Konstanten:
- pi
- log2(10)
- log2(e)
- log10(2)
- ln(2)

Edit: Demnach bekommt man log10 und log2 recht schnell hin und für alle anderen Basen braucht man die doppelte Zeit.
Edit: ln auch :mrgreen: