C++ Komma bei einer Gleitkommazahl finden

[ML89]

Hallo,

ich wende mich mal wieder an euch, weil ich eure Hilfe brauche.

Mein Problem:

Ich habe eine Gleitkommazahl als double vorliegen.

double x = 12,34;

Jetzt würde ich gerne wissen, wo das Komma steht. Hier an der dritten Stelle.
Ich weiß, dass C++ bei einer Float quasi durchitterieren kann.

Gedanklich stelle ich mir sowas vor:

(for int i = 0; i < Länge der Zahl x; i++)
{
    if (Zahl[i] == '.')
    {
         Anweisung_1
    }
    else
    {
         Anweisung_2
    }
}

So wie ich es skizziert habe, sieht es ja nach einer Konvertierung zu string aus. Gibt es da vielleiocht eine elegante Möglichkeit?

 

[Piktogramm]

Das Komma ist immer nach dem ganzzahligem Anteil einer Dezimalzahl.

Ansatz: Float zu Int -> Ganzzahl zu String -> Länge von String bestimmen

 

[kinglouy]

Da muss ein . hin und kein , übrigens.

 

[ML89]

Danke. Ich schaue mal, was sich machen lässt...

 

[nebulus]

In einer Schleife durch 10 Teilen, solange bis kein Rest mehr da ist. Schleifendurchläufe zählen.

 

[Kanibal]

Du kannst auch den Zehner-Logarithmus verwenden, das ist aber eventuell langsamer: https://glot.io/snippets/efqvioetl7

 

[nebulus]

Coole Webseite glot, kannte ich noch nicht

 

[ML89]

Ich habe es jetzt so gelöst:

public: static void Foo(double number)
{
	char string[digitsInUse + 1];
	dtostrf(number, 1, 3, string);
		
	int digit = 1;

	for(int i = 4; i >= 0; i--)
	{
		
		if (string[i] == '.')
		{
			string[i - 1] = (char)((int)string[i - 1] + 128);
		}
		else
		{
			WriteData(digit, (int)string[i]);
			digit++;
		}
	}
}

Da das Ganze auf einem Atmel laufen soll, habe ich nicht alle Bibliotheken zur Verfügung.

 

[VikingGe]

Du kannst auch den Zehner-Logarithmus verwenden, das ist aber eventuell langsamer

Wenn man das ganze jetzt noch mit Integern macht, ist das ganz sicher nicht langsamer:

template<typename T>
T intDigits(T n) {
  return n != 0
    ? 1 + intDigits(n / 10)
    : 0;
}

constexpr double eineZahl = 31.41592;
std::cout << intDigits(static_cast<int64_t>(eineZahl)) << std::endl;  // 2

Entspricht etwa dem Vorschlag von nebulus.

Umwege über Strings usw. nach Möglichkeit immer vermeiden, wenn Strings nicht explizit benötigt werden. Da sind Speicherallokationen etc. im Spiel, was für so eine Anwendung einfach völlig unnötig ist.



Edit: Die Vorschläge hier funktionieren natürlich alle nicht, wenn du negative Werte für Zahlen wie 0.025 erwartest, was dann etwa in der e-Notation stehen würde. Da muss man sich dann anderen Tricks behelfen, wie z.B. wirklich die Float-Zahl mit 10 zu multiplizieren.

 

[Kanibal]

Das ist aber nicht der Zehner-Logarithmus.

std::log10 operiert auf Gleitkommazahlen (siehe Doku) und muss deshalb auf einem Atmel Microcontroller (ohne FPU, tippe ich mal) durch mehrere Zyklen implementiert werden.

 

[Piktogramm]

Auf einem Atmel double zu nehmen, aber gleichzeitig nur 4 Stellen vor dem Komma vorsehen ist sowieso merkwürdig. Ich mag fast behaupten, selbst µC sind mittlerweile zu schnell um effizientes Programmieren zu erzwingen*.


*Ja das sage ich im Bewusstsein, dass mein erster Vorschlag hier übel Rechenzeit braucht

 

[VikingGe]

Das ist aber nicht der Zehner-Logarithmus.

Schön, es ist der Integer-Teil des Zehner-Logarithmus des Betrags des Integer-Teils der ursprünglichen Zahl. Mehr als das braucht und will der TE doch gar nicht.

und muss deshalb auf einem Atmel Microcontroller (ohne FPU, tippe ich mal) durch mehrere Zyklen implementiert werden.

Ab davon, dass das auch keine x86-CPU in Hardware kann, gilt dasselbe für die Umwandlung in einen String. Bei der Float-Variante mit Komma suchen ist da richtig was los (ich hab mal ein Paper gelesen, wo verschiedene Methoden mit unterschiedlicher Genauigkeit vorgestellt wurden, und da waren für brauchbare Ergebnisse schon mehrere hundert Zeilen Code nötig), und die Integer-Variante enthält quasi zwangsläufig meinen Code von oben.

Je nach Implementierung der log10-Methode dürfte diese nebenbei konstante (wenn auch absolut gesehen realtiv hohe) Laufzeit haben, sowas wird ja gerne mal mit etwas Preprocessing, Approximationspolynomen und ein paar Newton-Iterationen zurechtgebastelt - habs aber nie getestet, nagelt mich jetzt nicht darauf fest.

Und wenn man es wirklich ernst meint, nimmt man die Integer-Variante, optimiert die Division weg (indem man erst mit 1 vergleicht und diese 1 dann so lange mit 10 multipliziert, bis da irgendwann mal was größeres herauskommt als die gegebene Zahl, und Wertebereichsüberschreitungen korrekt behandelt). Das ist nochmal um einen gewissen Faktor flotter als die Integer-Division.

 

[Ebrithil]

Edit: Die Vorschläge hier funktionieren natürlich alle nicht, wenn du negative Werte für Zahlen wie 0.025 erwartest, was dann etwa in der e-Notation stehen würde. Da muss man sich dann anderen Tricks behelfen, wie z.B. wirklich die Float-Zahl mit 10 zu multiplizieren.

Oder guckst einfach wenn Zahl < 0 dann Stelle ++ (für das Vorzeichen) und multiplizierst die Zahl mit -1, dann kannst du wieder durch 10 teilen bis du bei 0 ankommst.

 

[S.Kara]

Wenn es um Geschwindigkeit geht ist der Weg von nebulus sicherlich der Beste.

Beim Code von VikingGe bekommt man allerdings für Werte < 1 eine Null als Ergebnis, was falsch ist. Übergibt man Gleitkommawerte bekommt man genauso Müll raus.
Ein Template ist hier eigentlich nicht nötig, einfach als int lassen und wenn der Wertebereich nicht ausreicht nochmal als int64.

int _getDigitsHelp(int x)
{
	return x == 0? 0 : 1 + _getDigitsHelp(x / 10);
}

int getDigits(int x)
{
	return x == 0 ? 1 : _getDigitsHelp(x);
}

std::cout << getDigits(0) << std::endl;
std::cout << getDigits(5) << std::endl;
std::cout << getDigits(-123.456) << std::endl;

ergibt dann "1", "1", "3".

 

[The Ripper]

Wie wärs, wenn man einfach den Exponenten extrahiert?
Entweder mit einer Maske verunden und dann shiften oder Unions benutzen: http://stackoverflow.com/a/15685301

Wenn man das ganze jetzt noch mit Integern macht, ist das ganz sicher nicht langsamer:

Integerdivison ist oft sogar langsamer als Division mit double.
Rekursion ist jetzt auch nicht unbedingt performant.

 

[Piktogramm]

nebulus' Methode ist wirklich recht fix, mit double sind das auch nur 308 Durchläufe (oder deutlich weniger bei binärer Suche), auf modernen CPUs also ein Witz. Auf einem Atmel AVR hat ein Double nur 32bit und damit nur 38 mögliche Stellen vor dem Komma, geht also auch recht fix.

Was man beiden AVR µCs aber immer vermeiden sollte wenn möglich sind Gleitkommazahlen. Die AVRs haben keine FPU und brauchen für Floatingpointoperationen entsprechend lange. Grob liegt zwischen 32bit Integerdivision und der selben Operation mit 32bit Double Faktor 2 und das ist noch der aller beste Fall:
https://www.mikrocontroller.net/articles/ArithmetikBenchmark

 

[VikingGe]

Beim Code von VikingGe bekommt man allerdings für Werte < 1 eine Null als Ergebnis, was falsch ist.

Ja, stimmt - aber die Lösung ist, wie man an deinem Code sieht, trivial.
Irgendwie hatte ich bei dem Beitrag aber auch nicht genug Koffein in mir oder sowas, der ist etwas daneben gegangen.

Wie wärs, wenn man einfach den Exponenten extrahiert?

Das wäre aber der Zweierexponent, nicht der Zehnerexponent. So wie ich das verstehe, braucht er letzteren, und da hilft uns der Zweierexponent ohne Mantisse relativ wenig weiter.

Integerdivision ist oft sogar langsamer als Division mit double

Integer-Division mit Konstanten kann in vielen Fällen einfach wegoptimiert werden (Tail Recursion sowieso). Hier mal der Clang-Output für den Code von S.Kara auf x86:

getDigits(int):                          # @getDigits(int)
        mov     eax, 1
        test    edi, edi
        je      .LBB0_3
        xor     eax, eax
.LBB0_2:                                # %tailrecurse.i
        movsxd  rcx, edi
        imul    rdi, rcx, 1717986919
        mov     rdx, rdi
        shr     rdx, 63
        sar     rdi, 34
        add     edi, edx
        inc     eax
        add     ecx, 9
        cmp     ecx, 18
        ja      .LBB0_2
.LBB0_3:                                # %_getDigitsHelp(int) [clone .exit]
        ret

Keine zeitaufwändige Division, keine Rekursion, nur eine Schleife mit etwas einfacher Integer-Arithmetik. Und wenn einem das immer noch zu langsam ist, weil der Chip z.B. keine schnelle Multiplikation unterstützt, dann geht man eben den Weg über Multiplikation mit 10 und Vergleiche:

int32_t _getDigitsHelper(int32_t x, int32_t exp, int32_t n) {
  return x >= exp
    ? _getDigitsHelper(x, exp * 10, n + 1)
    : n;
}

int32_t getDigits(int32_t x) {
  // Limits sind hier typenabhängig - irgendwie doof
  return (x > -1'000'000'000 && x < 1'000'000'000)
    ? _getDigitsHelper(x, 10, 1)
    : 10;
}

Multiplikation mit 10 ist dasselbe wie

n <<= 1;
n = n + (n << 2);

Ausgabe:

getDigits(int):                          # @getDigits(int)
        lea     ecx, [rdi + 999999999]
        mov     eax, 10
        cmp     ecx, 1999999998
        ja      .LBB0_4
        mov     eax, 1
        cmp     edi, 10
        jl      .LBB0_4
        mov     ecx, 10
.LBB0_3:                                # %tailrecurse.i
        add     ecx, ecx
        lea     ecx, [rcx + 4*rcx]
        inc     eax
        cmp     ecx, edi
        jle     .LBB0_3
.LBB0_4:                                # %_getDigitsHelper(int, int, int) [clone .exit]
        ret

 

[maxwell-cs]

Mein Vorschlag ist nicht ganz ernst gemeint, was die tatsächliche Anwendung beim Threadersteller angeht, sondern versucht eher, die Operation so schnell wie möglich zu implementieren, falls der Exponent nicht zu gross wird: Wenn die Zahl als Floating-Point-Zahl vorliegt, kann der abgerundete 2er-Logarithmus sehr schnell extrahiert werden.

Da 2 signifikant kleiner als 10 ist, laesst sich daraus für die meisten Zahlen schon der abgerundete 10er-Logarithmus bestimmen: 2-3, 4-7, 16-31, 32-63 liegen z.B. alle in jeweils einem 10er-Logarithmus-Intervall (0, 0, 1, 1).
Für alle anderen Bereiche gibt es höchstens zwei Möglichkeiten für den abgerundeten 10er-Logarithmus: Der Bereich 8-15 zerfällt in 8-9 und 10-16, ebenso 64-127 un 64-99 und 100-127. Offensichtlich sind das die einzigen beiden Möglichkeiten, es können nicht drei oder mehr Werte für den 10er-Logarithmus in Frage kommen.
Man kann also eine Lookup-Table für die zu erwartete Range an 2er-Exponenten (für die meisten Anwendungen sollten -256 bis 256 z.B. vollkommen ausreichen) aufbauen, in der man für eine gegebene Zahl dann nachschaut: Entweder ist der abgerundete 10er-Logarithmus schon klar ist oder eben nach höchstens einem Vergleich mit einer 10er-Potenz.