Aus wievielen Ziffern besteht meine Ganzzahl??

[Reinhard Kern]

Theoretisch müsste es schneller gehen, die Zahl nacheinander mit (Konstanten!) 10, 100, 1000... zu vergleichen, das ergibt auch so viele Berechnungen wie Stellen, aber in jeder Stufe nur eine Subtraktion statt einer Division. Am besten in Assembler als lineare Folge von Compare und Jump-Befehlen.

also

Delphi-Quellcode:

        .RADIX 10
        CMP     EAX,10
        JNB     Next1
        RET     1
Next1:  CMP     EAX,100
        JNB     Next2
        RET     2
Next2:

usw.

Gruss Reinhard

[s-off]

Zitat:

Zitat von sirius

Hast du von den Zeitwerten den Durchschnitt gebildet, hast du das Minimum genommen, wie hast du Zeit gemessen. Da kann dir einiges in die Quere kommen. Auch Krokos Variante dürfte fix sein (er sollte nur die abs(Ganzzahl) bilden)

Die Zeiten habe ich mit ProDelphi gemessen. Dieses berechnet Durchschnittswerte etc. automatisch.

Edit: @Reinhard Kern
Daran habe ich auch zuerst gedacht. Dadurch wäre ich aber nicht mehr dynamisch, da ich sämtliche Werte vorgeben muss, was zwar endlich, aus meiner Sicht aber dennoch unschön ist.

[Reinhard Kern]

Zitat:

Zitat von s-off

Edit: @Reinhard Kern
Daran habe ich auch zuerst gedacht. Dadurch wäre ich aber nicht mehr dynamisch, da ich sämtliche Werte vorgeben muss, was zwar endlich, aus meiner Sicht aber dennoch unschön ist.

Hallo, das ist meistens so: schnell ist nicht elegant. Mein Vorschlag ist eben gerade deshalb schnell, weil er Konstanten benutzt (also die Stufen vorher berechnet sind) und weil er die Schleife aufrollt - eine übliche Technik zur Geschwindigkeitserhöhung. Das Gegenteil sind rekursive Lösungen - elegant formuliert, aber langsam und mit indiskutabler Stack-Belastung.

Gruss Reinhard

[alzaimar]

[OT]

Zitat:

Zitat von Reinhard Kern

Das Gegenteil sind rekursive Lösungen - elegant formuliert, aber langsam und mit indiskutabler Stack-Belastung.

Ein Vorurteil aus der SWT-Antike. In der Tat sind rekursive Lösungen nur unwesentlich langsamer als ihr iteratives Pendant. Und eine sinnvolle rekursive Lösung (z.B. Quicksort oder Backtracking) belasten den Stack nur minimal: Die paar Bytes, die jedesmal auf den Stack geschoben werden, machen den Kohl nicht fett)
[/OT]

[s-off]

Danke für die Erläuterungen!

[3_of_8]

Um das ganze mal rein in Delphi zu formulieren:

Delphi-Quellcode:

function GetDecimalFigures(AValue: Integer): Integer;
const POWERSOFTEN: array[0..9] of Integer =
  (1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
  100000000, 1000000000);
var lo, hi, mid: Integer;
begin
  lo:=0;
  hi:=high(POWERSOFTEN);
  Result:=0;
  AValue:=abs(AValue);

  while Result=0 do
  begin
    mid:=lo+(hi-lo) div 2;
    if POWERSOFTEN[mid]<AValue then
      lo:=mid+1
    else if POWERSOFTEN[mid]>AValue then
      hi:=mid-1
    else begin
      Result:=mid+1;
    end;
    if lo>=hi then Result:=hi+1;
  end;
end;

Das ganze benutzt - wie vorher vorgeschlagen - ein Konstantenarray, dazu binäre Suche.

[grenzgaenger]

Zitat:

Zitat von Kroko1999

Delphi-Quellcode:

ZiffernCount := Int(Abs(ln(Ganzzahl))/ln(10));

[Edit]Formel verbessert

du weisst schon, dass du da immer verschiedene lösungen bekommst... ;-)

log 300 / log 10 --> 2.478 --> int 2
log 500 / log 10 --> 2.699 --> int 3

wie viele stellen hat denn nun die 3 stellige zahl? 2 oder 3... oder nach dem kollegen 3 oder 4??? :gruebel: :gruebel:

[grenzgaenger]

Zitat:

Zitat von 3_of_8

Um das ganze mal rein in Delphi zu formulieren:

Delphi-Quellcode:

function GetDecimalFigures(AValue: Integer): Integer;
const POWERSOFTEN: array[0..9] of Integer =
  (1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
  100000000, 1000000000);
var lo, hi, mid: Integer;
begin
  lo:=0;
  hi:=high(POWERSOFTEN);
  Result:=0;
  AValue:=abs(AValue);

  while Result=0 do
  begin
    mid:=lo+(hi-lo) div 2;
    if POWERSOFTEN[mid]<AValue then
      lo:=mid+1
    else if POWERSOFTEN[mid]>AValue then
      hi:=mid-1
    else begin
      Result:=mid+1;
    end;
    if lo>=hi then Result:=hi+1;
  end;
end;

Das ganze benutzt - wie vorher vorgeschlagen - ein Konstantenarray, dazu binäre Suche.

das ganze geht doch auch etwas eleganter ... :-)

Delphi-Quellcode:

function GetIntLength(const Zahl: integer; Count: integer): integer;
var
 tmp: integer;
begin
 tmp := zahl div 10;
 if tmp>0 then
  result := GetIntLength(tmp, count + 1)
 else 
  result := count + 1;
end;

[3_of_8]

Das ist vielleicht eleganter, aber auch langsamer, da es ein divs benutzt. ;)

[grenzgaenger]

hast recht, bei 100000 aufrufen einer 10 stelligen zahl stellt sich das wie folgt dar...

Zitat:

Rekursiv: 5569 Ticks
Interativ: 5387 Ticks

also, schon extrem langsamer ... :zwinker: