Acotar 7 bits (0-127) a un rango dado (0-99)


#1

Buenas! No sabía en qué subforo colocar esta pregunta, así que la meto aquí que es el más general. Voy a explicar todo el caso, pero la idea de la pregunta es muhco más básica.

Estoy programando un LFSR para generar números pseudoaleatorios en una FPGA (aunque da igual la plataforma). El problema es que este generador debe devolver números en un rango dado, por ejemplo, de 0 a 99.
Mi LFSR es de 16 bits (aunque, de nuevo, da igual), y he pensado que tomando 7 bits cualquiera tendría un rango cercano al deseado (0-127), ya que un subconjunto de un conjunto de bits aleatorios debería seguir siendo aleatorio.

El problema es cómo acotar el rango obtenido (0-127) al deseado (0-99). La división es una operación muy complicada de implementar, y no es una opción.
Así que, ¿a alguien se le ocurre alguna manera de acotar el resultado sin perder aleatoriedad? Le estoy dando vueltas pero no se me ocurre una buena solución.

He pensado en, si obtengo un resultado por encima del máximo, volver a generar otro número hasta que caiga en el rango, pero esto implicaría una pérdida de ciclos de reloj que no sé si me puedo permitir.

A ver si me podéis echar una mano.
Gracias y un saludo!


#2

el problema de los números psudoaleatorios es que si manipulas el resultado, dejan de ser aleatorios, por otro lado la generación mediante LFSR siempre será un múltiplo de 2. Es cierto lo que dices, si puedes permitirte perder algunos ciclos hasta que el número generado esté dentro de tu rango está bien, pero por el hecho de ser aleatorios no sabrás nunca realmente cuanto ciclos extra te tomará. Creo que puede haber varias soluciones:

  1. Como realmente tienes pocos números, puedes hacer una tabla de lookup sencilla.
  2. Si tu número es mayor que 99, puedes utiliza únicamente los primeros 6 bits (resutado 0-63).
  3. Si el número es mayor que 99, puedes desplazar todos los bits hacia la derecha (division entre 2).

te garantizo aleatoriedad con el primer caso, con los otros no estoy tan seguro.


#3

Gracias por responder! De todas formas ya encontré una solución que funcionaba, para salir del paso por lo menos. Simplemente cogía 7 bits del LFSR y comprobaba que estuviera dentro del rango. Si lo estaba, conectaba el valor a la salida, y si no, esperaba un ciclo de reloj para la siguiente comprobación. Como necesitaba una salida cada bastantes ciclos de reloj, el resultado practicamente siempre sería diferente (y si no, no importaba, el programa lo detectaría).
Pensé en las dos últimas opciones que mencionas, pero eso daría como resultado que la mayoría de los números estuvieran por debajo de 64. Y la primera… creo que nunca he manejado una tabla de lookup, y de todos modos tampoco había que llegar a la perfección.
Así que todo bien. Muchas gracias de nuevo por tus respuestas.

Un saludo!