Performanter ja, cooler auch, aber einfacher sicher nicht.
Ja, unpassend zitiert, da hast du völlig Recht. Aber der Trick ist simpel:
unsigned digits( std::uint64_t v )
{
unsigned t = (64 - __builtin_clzll(v)) * 1233 >> 12; // (1)
return t + 1 - (v < pow10[t]); // (2)
}
Die Idee ist, dass ich den Zehnerlogarithmus auf den Logarithmus zur Basis Zwei reduziere, den ich sehr performant berechnen kann.
Der Zweierlogarithmus berechne ich mit der intrinsic __builtin_clzll (count leading zeros long long), welche die Anzahl der führenden Nullen in Binärnotation zurückgibt - und das ziehe ich von 64 ab, um den (um 1 erhöhten) Zweierlogarithmus zu bekommen.
Dann wird der Zweierlogarithmus in (1) mit einer Konstante multipliziert, und zwar log(2)log(10)\frac{log(2)}{log(10)}log(10)log(2), welche hier als 1233∗2−121233 * 2^{-12}1233∗2−12 gegeben ist. Allerdings ist das nicht immer präzise: Es muss in (2) noch getestet werden, ob v kleiner ist als die aktuelle Zehnerpotenz der der Logarithmus t entspricht, und wenn, wird natürlich 1 vom Ergebnis abgezogen (das ganze soll branch-less passieren!). Anschließend wird noch eins draufaddiert, weil nicht der Logarithmus, sondern die Anzahl der Stellen zurückgegeben werden soll.
Das ganze ließe sich auch so schreiben:
return t + (v >= pow10[t]); // (2)
Den Trick gibt es auch bei Bit Twiddling Hacks, von wo ich ihn ursprünglich habe.
Edit: Zur Erklärung der Konstante: Die wurde so gewählt dass sie einen möglichst kleinen Rundungsfehler enthält, und dabei nicht zu große Konstanten verwendet:
log10(2)∗28=77.064≈77log_{10}(2) * 2^{8} = 77.064 \approx 77log10(2)∗28=77.064≈77
log10(2)∗210=308.255≈308log_{10}(2) * 2^{10} = 308.255 \approx 308log10(2)∗210=308.255≈308
log10(2)∗212=1233.0189≈1233log_{10}(2) * 2^{12} = 1233.0189 \approx 1233log10(2)∗212=1233.0189≈1233
log10(2)∗214=4932.0754≈4932log_{10}(2) * 2^{14} = 4932.0754 \approx 4932log10(2)∗214=4932.0754≈4932
log10(2)∗216=19728.3≈19728log_{10}(2) * 2^{16} = 19728.3 \approx 19728log10(2)∗216=19728.3≈19728
Der kleinste Rundungsfehler liegt bei 2122^{12}212, welches auch nicht zu groß ist.
Edit²: Latex... muss öfter die Posts mal anschauen bevor ich absende.
