De algoritmos genéticos y entropía

Hoy presento una idea chorra como cualquier otra, pero que a mi personalmente me emocionó ver que funcionaba, es simplemente un conjunto de un intérprete y un programa que modifica un trozo de bytecode al azar, obviamente pensados para trabajar juntos.

La idea es usarlos para generar un algoritmo usando algo análogo a la evolución natural, aplicando un script (solo por comodidad) para que elija que rama del algoritmo debe ser la que prevalezca, el código con un ejemplo: [instructolang.zip] (el script usa un trozo de código que se puede encontrar aquí http://math.co.ro/C/entropy.c, aunque va incluido en el .zip).

Por ahora está muy limitado, solo realiza las operaciones de suma, resta, intercambio de variables y asignación, de todos modos no creo que pueda llegar a ser turing completo por cosas como el problema de parada, que sería necesario resolver para evitar bucles infinitos.

Un autómata celular para generar números pseudo-aleatorios

La idea no es la primera vez que se oye, creo que fue Wolfram quién lo propuso en su momento, pero el concepto no deja de ser curioso, y el otro día trasteando con Golly me encontre con que una pequeña variante del juego de la vida de Conway, con la diferencia de que una "célula" también puede "nacer" si tiene 4 vecinos (y no solo 3) llamado "3-4 life", que hace que patrones sencillos crezcan indefinidamente quedando el contenido en su interior algo aleatorio, esta es una simulación de las 250 primeras generaciones [http://videobin.org/+2be/2ly.html].

Improvisando un cifrado de flujo/generador de números aleatorios

A veces hay que hacer un pequeño sistema de cifrado para la ocasión que no tiene porque ser criptográficamente seguro, una chapuzilla vamos, veremos como improvisar uno.

Números pseudo-aleatorios con Pascal

La generación de números pseudo-aleatorios es una característica que la mayoría de lenguajes de programación implementa por defecto, pero Pascal estándar extendido es una excepción (el FreePascal no, ojo).

Esta historia viene porque hace tiempo necesitaba generar estos números para un programa en Pascal, y al no encontrar nada (aunque bueno... tampoco busqué mucho :P ) programé  algo. No es gran cosa, si se conocen los dos números anteriores y el momento en el que se inició el generador (con una precisión de microsegundos) se puede intentar descubrir cual será el siguiente, pero sirve para algo básico.

Para usarlo solo hay que importarlo y llamar a la función random usando el número "tope" como parámetro, por ejemplo, para generar un número del 0 al 100 (ambos incluidos):

---

aleatorio := random(100);

---

El código es este, se basa en el cifrado ARC4 (a.k.a RC4), y para descargar [random.pas]

---

module mod_random;

{
Copyright (C) Kenkeiras 2010

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by

    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program. If not, see <http://www.gnu.org/licenses/>.


Modulo de numeros aleatorios

    Contiene las funciones para generar numeros aleatorios

    - random

}


export mod_random=(random);

function random(top:integer):integer;
type
    tbyte=0..255;

var
    S: array [0..255] of tbyte;
    i,j: integer;

end;

{ procedure swap (var c1:tbyte;var c2:tbyte);
    Intercambia dos bytes
}
procedure swap (var a,b:tbyte);

    var
     temp:tbyte;
    begin
     temp:=b;
     b:=a;
     a:=temp;
    end;

{ procedure random_seed;

    Inicia la caja para generar los numeros pseudo-aleatorios

}
procedure random_seed;
    var
        t:timeStamp;
        str:string(255);
        n:integer;

    begin
        getTimeStamp(t);
        str:=time(t);

        for n:=0 to 255 do
            S[n]:=n;

        j:=0;
        for n:=0 to 255 do begin
            j:=(j+S[n]+ord(str[(n mod length(str))+1]))mod 256;
            swap(S[n],S[j]);
        end;

        i:=0;
        j:=0;
end;

{ function random_byte:tbyte;

    Precondicion: La caja esta iniciada
    Devuelve un byte pseudo-aleatorio

}
function random_byte:tbyte;
    begin
        i:=(i+1)mod 256;
        j:=(j+S[i])mod 256;

        swap(S[i],S[j]);
        random_byte:= S[(S[i]+S[j])mod 256];
    end;

{ function random(top:integer):integer;

    Precondicion: La caja esta iniciada
    Devuelve un numero (integer) pseudo-aleatorio con un valor maximo de 'top'

}

function random;
    var
        n,k:integer value 0;

    begin
        for n:=((top div 256)+1) downto 0 do
            k:=k+random_byte;

        random:=(k mod top)+1;
    end;

to begin do
    { Al iniciar el programa inicia la caja para poder generar numeros aleatorios }
    random_seed;

end.

---

Y eso es todo... hasta otra.