Schneller ganzzahliger Logarithmus für Spezialfall

Question

Ich habe ganzzahlige Werte von 32-8191, die ich grob logarithmisch skalieren möchte. Wenn ich Base 2 verwende, könnte ich einfach die führenden Null-Bits zählen und sie in 8 Slots abbilden, aber das ist zu grobkörnig; Ich brauche 32 Steckplätze (und mehr wäre besser, aber ich brauche sie, um Bits in einem 32-Bit-Wert zuzuordnen), die für den Logarithmus auf eine Basis von ungefähr 1,18-1,20 kommt. Hat jemand ein paar Tricks, um diesen Wert oder eine vernünftige Annäherung sehr schnell zu berechnen?

Meine Intuition ist, den Bereich in 2 oder 3 Unterbereiche mit Bedingungen zu brechen, und verwenden Sie eine kleine Nachschlagetabelle für jeden, aber ich frage mich, ob es einen Trick gibt, mit Zähl-führenden Nullen zu tun und dann das Ergebnis zu verfeinern, zumal die Ergebnisse nicht exakt, sondern nur grob logarithmisch sein müssen.

Answer 1

Warum nicht die nächsten zwei Bits außer dem führenden Bit verwenden? Sie können die Nummer zuerst in die 8 Bin und die nächsten zwei Bits partitionieren, um jede Bin in vier zu teilen. In diesem Fall können Sie eine einfache Schiebeoperation verwenden, die sehr schnell ist.

Bearbeiten: Wenn Sie denken, mit dem Logarithmus ist eine praktikable Lösung. Hier ist der allgemeine Algorithmus:

Lassen Sie a die Basis des Logarithmus sein, und der Bereich ist (b_min, b_max) = (32,8191). Sie können die Base mit der Formel finden:

log(b_max/b_min)/log(a) = 32 bin 

, die Sie a~1.1892026 geben. Wenn Sie dieses a als Basis des Logarithmus verwenden, können Sie den Bereich (b_min, b_max) in (log_a(b_min), log_a(b_max)) = (20.0004,52.0004) abbilden.

Nun müssen Sie nur noch das gesamte Element um 20.0004 subtrahieren, um den Bereich (0,32) zu erhalten. Es garantiert, dass alle Elemente logarithmisch einheitlich sind. Fertig

Hinweis: Entweder kann ein Element aufgrund eines numerischen Fehlers aus dem Bereich fallen. Sie sollten es für den genauen Wert selbst berechnen.

Note2: log_a (b) = log (b)/log (a)

Answer 2

Suche in einer Tabelle ist eine Option, dass Tabelle ist nicht so groß. Wenn eine 8K-Tabelle zu groß ist und Sie eine Anweisung mit führenden Nullen zählen, können Sie eine Tabellensuche in den oberen paar Bits verwenden.

nbits = 32 - count_leading_zeros(v) # number of bits in number 
highbits = v >> (nbits - 4)   # top 4 bits. Top bit is always a 1. 
log_base_2 = nbits + table[highbits & 0x7] 

Die Tabelle, die Sie mit einer gewissen Annäherung der log_2 bevölkern

table[i] = approx(log_2(1 + i/8.0)) 

Wenn Sie in Integer-Arithmetik bleiben wollen, bequem mit einem Faktor, der die letzte Zeile multiplizieren.

Answer 3

Antwort Ich kam gerade in IEEE mit basierend auf 754 Floating-Point:

((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16 

Es bildet 32-8192 auf 0-31 grob logarithmisch (gleich wie hwlau Antwort).

Verbesserte Version (ausgeschnitten nutzlos bitweise und):

((union { float v; uint32_t r; }){ x }.r >> 21) - 528