Anzahl der Ziffern eines int-Wertes ermitteln

DirkB schrieb:

[Klugscheiss]
Das ist aber nicht portabel, denn wer weiß schon wie groß ein int (danach wurde ja gefragt) auf dem jeweiligem System ist.
[\Klugscheiss]

Naja, dann kann man das zumindest mit Multiplikationen machen - die sind idR schneller zu haben:

unsigned stellen(unsigned x) {
  unsigned n = 2;
  unsigned f = 10;

  if(x < 10) return 1;
  /* Overflow vermeiden */
  x /= 10;

  while(f <= x) {
    f *= 10;
    ++n;
  }

  return n;
}

Damit kriege ich gegenüber der Divisionsschleife einen Geschwindigkeitsgewinn von knapp 50%.

Ab 64-Bit-Integern lohnt es sich auch, Abkürzungen zu nehmen. Beispielsweise kriege ich mit

#include <limits.h>

unsigned stellen(unsigned x) {
  static unsigned const SQ_LIMIT = UINT_MAX >> (sizeof(unsigned) * CHAR_BIT / 2);
  unsigned n = 1;
  unsigned factor = 10;
  unsigned t = factor;

  if(x < 10) return 1;
  /* Overflow vermeiden */
  x /= 10;

  while(t <= SQ_LIMIT && (t = factor * factor) <= x) {
    factor = t;
    n <<= 1;
  }

  while(factor <= x) {
    ++n;
    factor *= 10;
  }

  return n + 1;
}

und gleichverteilter Stellenanzahl einen Geschwindigkeitsgewinn von etwa 25% gegenüber der einfachen Multiplikationsschleife oben. Merke, dass es sich dabei um gleichverteilte Stellenanzahl handelt, nicht um gleichverteilte Eingabewerte. Bei gleichverteilten Eingabewerten bis 2⁶⁴ ist mehr zu erwarten. Von der Laufzeitkomplexität her (gemessen an der Breite der Integer) ist da prinzipiell noch mehr zu holen; ich denke da etwa an

unsigned stellen(unsigned x) {
  static unsigned const SQ_LIMIT = UINT_MAX >> (sizeof(unsigned) * CHAR_BIT / 2);
  unsigned n = 1;
  unsigned factor = 10;
  unsigned t = factor;
  unsigned y;

  if(x < 10) return 1;
  /* Overflow vermeiden */
  y = x / 10;

  while(t <= SQ_LIMIT && (t = factor * factor) <= y) {
    factor = t;
    n <<= 1;
  }

  return stellen(x / factor) + n;
}

Allerdings wird es wohl noch eine Weile dauern, bis Integer so breit sind, dass sich die Rekursion amortisiert.

cooky451 schrieb:

Das düfte wohl so ziemlich die schlechteste Methode sein

Was gefällt dir nicht daran?

Aber wie wärs damit?

#include <stdio.h>

unsigned num_length (int n)
{
    if (n < 10)
        return 1;
    return 1 + num_length (n/10);
}

int main (void)
{
    printf ("%d\n", num_length (1234));
}

cooky451

Schon interessant, dass heutige Compiler immer noch so schlecht sind, dass sogar eine Multiplikation schneller als eine Division ist.

Z schrieb:

Was gefällt dir nicht daran?

Es ist blöd. Und Rekursion mag ich auch nicht :p

volkard

cooky451 schrieb:

Schon interessant, dass heutige Compiler immer noch so schlecht sind, dass sogar eine Multiplikation schneller als eine Division ist.

Der Prozessor kann schneller multiplizieren als dividieren. Was soll da ein schauer Compiler gleichmachen? Er kann nur ein wenig entschärfen durch Multiplikation gefolgt von shift und evtl einem bedingten Bit statt der Division, wenn die Division entschieden langsamer auf dem Prozessor ist. Das machen sie schon lange.

Was soll die CPU auch machen?

Nehmt euch ein Blatt Papier:
3 * 7 = ?
3 / 7 = ?

Okay, der Mathe-Coprozessor könnte aus der Multiplkation eine Addition bauen und aus der Division eine Subtraktion. Da sollten die Zeiten dann fast gleich sein.

MfG f.-th.

volkard

f.-th. schrieb:

Was soll die CPU auch machen?

Nehmt euch ein Blatt Papier:
3 * 7 = ?
3 / 7 = ?

Okay, der Mathe-Coprozessor könnte aus der Multiplkation eine Addition bauen und aus der Division eine Subtraktion. Da sollten die Zeiten dann fast gleich sein.

MfG f.-th.

Sei 0<=x<100 und ich stelle mir einen Prozessor vor, der das kleine 100x100 mit seinem MUL-Befehl schnell schafft.
Statt

y=x/7; //teure Division

schreibe ich

y=x*14; //y würde in zwei Registern liegen
y+=15; 
if(x>55) y+=15;
y/=100; //keine Division, nur shift

oder

y=(x*14+x*3/10)/100

oder sowas.
Da die 7 zur Compilezeit feststeht, kann auch der Compiler so einen Trick herausknobeln. Mein Trick sieht noch nicht hübsch aus, das geht bestimmt noch besser.

http://www.codeproject.com/KB/cs/FindMulShift.aspx?display=Mobile

http://sourceforge.net/projects/kdiv/

Man kann schon davon ausgehen, dass der Compiler bei zur Compilezeit bekanntem Divisor keine Division in der Hardware macht, sondern sie durch Multiplikationen und Bitshifts ersetzt. Trotzdem ist die Berechnung natürlich langsamer als eine einfache Multiplikation.

SeppJ

seldon schrieb:

Man kann schon davon ausgehen, dass der Compiler bei zur Compilezeit bekanntem Divisor keine Division in der Hardware macht, sondern sie durch Multiplikationen und Bitshifts ersetzt. Trotzdem ist die Berechnung natürlich langsamer als eine einfache Multiplikation.

Davon würde ich nicht ausgehen.

Kennst du einen Compiler, der das nicht macht?