Logaritmo de entero rápido para el caso especial

Tengo valores enteros que van desde 32-8191 que quiero asignar a una escala aproximadamente logarítmica. Si estuviera usando la base 2, solo podría contar los bits cero iniciales y asignarlos a 8 ranuras, pero esto es demasiado detallado; Necesito 32 máquinas tragamonedas (y más sería mejor, pero necesito que se mapeen en bits en un valor de 32 bits), que sale a una base de aproximadamente 1.18-1.20 para el logaritmo. ¿Alguien tiene algunos trucos para calcular este valor, o una aproximación razonable, muy rápido?Logaritmo de entero rápido para el caso especial

Mi intuición es dividir el rango en 2 o 3 subrangos con condicionales, y usar una pequeña tabla de búsqueda para cada uno, pero me pregunto si hay algún truco que pueda hacer con los ceros de recuento y luego refinar el resultado, especialmente porque los resultados no tienen que ser exactos, sino simplemente logarítmicos.

Fuente

2010-12-11 R..

¿Por qué no utilizar los dos bits siguientes además del bit inicial? Primero puede dividir el número en el 8 bin, y los siguientes dos bits para dividir cada bin en cuatro. En este caso, puede usar una operación de cambio simple que es muy rápida.

Editar: Si crees que usar el logaritmo es una solución viable. Aquí está el algoritmo general:

Sea a la base del logaritmo, y el rango es (b_min, b_max) = (32,8191). Puede encontrar la base usando la fórmula:

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

que le dan a~1.1892026. Si usa esto como la base del logaritmo, puede asignar el rango (b_min, b_max) al (log_a(b_min), log_a(b_max)) = (20.0004,52.0004).

Ahora solo resta restar el elemento all por 20.0004 para obtener el rango (0,32). Garantiza que todos los elementos son logarítmicamente uniformes. Hecho

Nota: O un elemento puede quedar fuera de rango debido a un error numérico. Debe calcularlo usted mismo por el valor exacto.

Nota 2: log_a (b) = log (b)/log (a)

Fuente

2010-12-11 04:52:39 unsym

que he visto algo que hacer antes de (dlmalloc viene a la mente), pero no sé si me gusta lo lejos que se desvía de logarítmica .Tal vez no es tan malo sin embargo. –

Me pregunto si puedo usar el punto flotante para ensamblar esos bits muy bien para mí ... –

Búsqueda en una tabla es una opción, que mesa no es tan grande. Si una tabla de 8K es demasiado grande y tiene una instrucción de contar ceros a la izquierda, puede usar una búsqueda de tabla en los primeros bits.

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]

La tabla rellena con alguna aproximación de log_2

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

Si desea permanecer en la aritmética de enteros, multiplicar la última línea por un factor conveniente.

Fuente

2010-12-11 04:53:29

La tabla 8k es demasiado grande, pero una tabla con 8-32 entradas no estaría mal. Sin embargo, me gusta la simplicidad de la solución de hwlau. –

Creo que nuestras soluciones son efectivamente idénticas (la mía usa los siguientes 3 bits, pero eso es configurable). –

respuesta Acabo de llegar con sede en IEEE 754 de punto flotante:

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

Al trazar 32-8192 0-31 en más o menos de forma logarítmica (igual que la respuesta de hwlau).

Versión mejorada (cortadas a nivel de bits inútil e):

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

Fuente

2010-12-11 05:13:46

¿Cómo se cambia la escala a otra cantidad de contenedor? – unsym

Reescalar .......? –

Logaritmo de entero rápido para el caso especial

Respuesta

Cuestiones relacionadas