Este primer ejemplo de Mal Código hace gala de poco conocimiento matemático y de que la función ni siquiera se probo si funcionaba.
Partimos de una función existente RandUnsigned que devuelve un valor aleatorio [0, MAX_UNSIGNED_INT]. Tenemos que el valor devuelto ocupa 4 bytes. Si lo que queremos es una función que devuelva valores booleanos aleatorios, lo que no debemos hacer es lo siguiente:
Partimos de una función existente RandUnsigned que devuelve un valor aleatorio [0, MAX_UNSIGNED_INT]. Tenemos que el valor devuelto ocupa 4 bytes. Si lo que queremos es una función que devuelva valores booleanos aleatorios, lo que no debemos hacer es lo siguiente:
// return random true/false
bool RandomBool(){
// above midvalue
if (RandUnsigned() & 0xFFFF0000)
return false;
else
return true;
}
¿Porque es errónea la función?. Vamos a ver la probabilidad de que devuelva un valor false. Si partimos de que el número devuelto por RandUnsigned es aleatorio, podemos asegurar que un bit cualquiera dentro de este número tendrá la misma probabilidad de estar a uno como de estar a cero, 50% de probabilidad, p = 0,5.
¿Que probabilidad hay de que estén en el mismo estado dos bits cualesquiera? Pues aplicando un poco de matemática básicas, p = 0,5 * 0,5 = 0,25 = 0.5^2. Para que la función devuelva true se tiene que cumplir que los 16 bits más significativos estén a cero (por lo de la comparación con 0xFFFF0000), y la probabilidad de que esto ocurra es de p = 0.5^16 = 0,000015 aprox. Resumiendo, una probabilidad ínfima de obtener el valor true.
Y por esto opino que la función ni siquiera se probo. Por que si se hubiese probado, se habría obtenido pocas veces o ninguna el valor true.
Mi solución
¿Que probabilidad hay de que estén en el mismo estado dos bits cualesquiera? Pues aplicando un poco de matemática básicas, p = 0,5 * 0,5 = 0,25 = 0.5^2. Para que la función devuelva true se tiene que cumplir que los 16 bits más significativos estén a cero (por lo de la comparación con 0xFFFF0000), y la probabilidad de que esto ocurra es de p = 0.5^16 = 0,000015 aprox. Resumiendo, una probabilidad ínfima de obtener el valor true.
Y por esto opino que la función ni siquiera se probo. Por que si se hubiese probado, se habría obtenido pocas veces o ninguna el valor true.
Mi solución
Yo voy a hacer uso de la constante UINT_BITS que es el número de bits que ocupa una variable unsigned int. En nuestro caso este valor es 32.
// return random true/false
bool RandomBool(){
const unsigned int MID_VALUE = 1<<(UINT_BITS - 1);
// above midvalue
return (RandUnsigned() < MID_VALUE);
}
Básicamente la nueva función divide el rango de números en dos mitades iguales [0, MID_VALUE) y [MID_VALUE, MAX_UNSIGNED_INT] y devuelve false o true dependiendo en que mitad caiga el número devuelto por RandUnsigned.
Otra opción hubiese sido simplemente comprobar si un bit cualquiera del número aleatorio es uno o cero. Dependiendo de la máquina en la que se compile puede que se ganen unos pocos ticks de ejecución. Lo que es seguro es que las dos soluciones tenderán a dar los valores false y true con la misma probabilidad, 50% para cada uno, lo que es una gran ventaja respecto a la función original.
Otra opción hubiese sido simplemente comprobar si un bit cualquiera del número aleatorio es uno o cero. Dependiendo de la máquina en la que se compile puede que se ganen unos pocos ticks de ejecución. Lo que es seguro es que las dos soluciones tenderán a dar los valores false y true con la misma probabilidad, 50% para cada uno, lo que es una gran ventaja respecto a la función original.
2 comentarios:
Tienes razon en que la funcion esta mal, pero tu analisis es también algo rapido. La funcion casi siempre devuelve false y no true. Para que la condicion sea cierta el resultado ha de ser distinto de cero, es decir, que tiene que cumplir que alguno de los 16 bits mas significativos sea 1.
La probabilidad de eso es 1 menos las probabilidad de que los 16 MSb sean 0. A partir de ahi pues se sigue con tu plantemamiento.
Un codigo equivalente al tuyo es haciendo un and con 0x80000000, es decir, el bit mas significativo que indica si esta o no en la mitad superior de los numeros, pero tu forma es mas legible.
La verdad es uno de esos codigos que se hacen rapidos por que parece n obvios, y se hacen por inspiracion divina, y se nota que no esta testeado, aunque la inspiracion divina a veces es necesaria. Bueno todos tenemos estos errores, pero al final aprendemos tambien a testear.
El problema es que despues es dificil detectarlo por que en algo tan simple nadie tiende a pensar que falla, y a al ver el codigo se tiende a justificar el razonamiento de quien lo creo.
En fin si algo es simple tambien hay que probarlo ;)
Por último quiero comentar un tema que no concierne al tema de este blog mal codigo. Este tema es el de apariencia de aleatoriedad. El random de la libreria suele ser un GCL este tiene una distribucion uniforme, apariencia de aleatoriedad, debido de cierta forma a la cantidad de numeros distintos, pero son ciclicos completos. Esto nos asegura que nuestro codigo tambien genere una distribucion uniforme pero no nos asegura apariencia de aleatoriedad. Por ejemplo que despues de dos 0 sepamos que siempre viene un 1. Probablemente si solo tuvieramos en cuenta el ultimo bit, la probabilidad de sacar 1 despues de un 0 sea distinta de sacar 1 despues de un 0. Lo mejor es pasar distintos test, probando los distintos bits, y elegir el que de mejor apariencia de aleatoriedad. Otra opcion es hacer nuestro generador o buscar en internet. Todo depende de la importancia que le demos.
Tienes toda la razón acerca de la confusión entre true y false. Queda corregido el error en el blog.
Sirva esto ademas de ejemplo. Cuanto más simple sea el código más facíl de ver los errores. En la primera versión de la función el error es complicado de detectar.
Publicar un comentario