Tarea de programación C – Números primos

En un post anterior escribí el código para encontrar números primos en Java. A diferencia del código en aquel post, aquí he usado una representación digital de la criba o coladera de Eratóstenes. Usar una representación en memoria tiene la ventaja de que nos permite ahorrarnos muchos cálculos innecesarios que el anterior código hacía para comprobar si un número era primo. Además, gracias a que cualquier compilador moderno nos permite declarar arreglos o reservar bloques de memoria de tamaño arbitrario, es posible usar este código para encontrar fácilmente los números primos por debajo de 1,000,000,000 (o cualquier número en el rango del tipo de datos int).

#include 
#include 
#include 
#include 

#define LIMITE 100000000

uint8_t *criba;
int contador = 0;

int main() {
    criba = calloc(LIMITE, 1);
    assert(criba);
    for (int i = 2; i < LIMITE; i++) {
        if (criba[i] == 0) {
            contador++;
            printf("%d\n", i);
            uint64_t mul = i * 2;
            while (mul < LIMITE) {
                criba[mul] = 1;
                mul += i;
            }
        }
    }
    printf("Se encontraron %d números primos menores a %d.\n", contador, LIMITE);
}

El código anterior define LIMITE con un valor de 100,000,000 y en mi PC toma aproximadamente 4 segundos al programa para encontrar los números primos por debajo de ese valor. Si incremento el valor de LIMITE a 1,000,000,000 toma aproximadamente 40 segundos en mi PC, que sigue siendo más rápido que el tiempo que tomaba la versión anterior del código para un valor de 100,000,000. Nota que puede llegar a millones la cantidad de números primos para estos valores de LIMITE, por lo que recomiendo enviar la salida del programa a un archivo y no directamente a la terminal. Es decir, ejecuta el programa de la siguiente manera:

monstruosoft@debian:~/code$ ./primos > /dev/shm/primos.txt

En el archivo primos.txt se guardará la salida del programa, por ejemplo:

2
3
5
7
11
13
17
19
23
29
31
37
...
999999667
999999677
999999733
999999739
999999751
999999757
999999761
999999797
999999883
999999893
999999929
999999937
Se encontraron 50847534 números primos menores a 1000000000.

Nota también que aunque este código puede fácilmente reservar un bloque de memoria de 1 GB en C, el mismo código en Java siempre me daba errores de OutOfMemoryException. Incluso después de aumentar el tamaño de la memoria usada por la máquina virtual de Java, usar System.out.println() era extremadamente lento para intentar escribir varios millones de líneas de texto a un archivo, y un ArrayList con varios millones de números primos también causaba problemas al intentar usar el método toString() así que si conoces la forma de usar este código en Java deja un comentario.

 

Tarea de programación Java – Números primos

Una clásica tarea de programación es encontrar todos los números primos menores por debajo de una cantidad introducida por el usuario. El algoritmo más básico consiste en usar una versión digital de la criba de Eratóstenes que es bastante simple de escribir pero puede volverse muy lenta conforme se incrementa el la cantidad que introduce el usuario. El código en este post es básicamente el algoritmo la criba de Eratóstenes con unas cuantas optimizaciones. En mi PC es posible encontrar todos los números primos menores a 10,000,000 relativamente rápido usando este código. Para los números primos menores a 100,000,000 el código se tarda casi un minuto en mi PC. Para números mayores el tiempo se multiplicaría considerablemente.

El código para encontrar los números primos es el siguiente (lo siento, no pude lograr que wordpress formateara el código correctamente):

public static ArrayList<Integer> numerosPrimos(int max) {
    ArrayList<Integer> primos = new ArrayList<Integer>();
    primos.add(2);

    for (int i = 3; i < max; i++) {
        boolean es_primo = true;
        double limite = Math.ceil(Math.sqrt(i));
        for (int j = 0; j < primos.size(); j++) {
             if (i % primos.get(j) == 0) {
                 es_primo = false;
                 break;
             }
             if (primos.get(j) > limite) break;
        }
        if (es_primo) primos.add(i);
    }

    return primos;
}

 

He agregado este método a la clase TareasProgramacion en github. Se puede usar este método como en el siguiente ejemplo:

import java.util.*;
import org.monstruosoft.utils.*;

public class Prueba {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        System.err.print("Escribe el número máximo para la búsqueda de números primos: ");
        int max = s.nextInt();
        ArrayList primos = TareasProgramacion.numerosPrimos(max);
        for (Integer i: primos)
            System.out.println(i);
        System.out.println("Se encontraron " + primos.size() + " números primos menores a " + max + ".");
    }
}

Al ejecutar el programa obtenemos la siguiente salida:

monstruosoft@debian:~/code/monstruosoft/java-utils$ java Prueba 
Escribe el número máximo para la búsqueda de números primos: 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Se encontraron 25 números primos menores a 100.

Instalar Allegro 4 / Allegro 5

Recientemente el blog ha recibido algunas visitas de búsquedas relacionadas con Allegro (principalmente en su versión 4.x). En posts anteriores escribí la forma de compilar Allegro para Debian Jessie ya que la versión en el repositorio estable era muy antigua pero Debian Stretch ya tiene una versión más reciente en el repositorio estable así que, si eres usuario de Linux, la forma más sencilla de instalar Allegro es instalar los paquetes correspondientes desde el gestor de paquetes de tu distro.

Para Allegro 4 basta con instalar los paquetes liballegro4.4 y liballegro4-dev.  También se pueden instalar las librerías de soporte para Allegro 4 como liballeggl4.4, libguichan-allegro, libjpgalleg4.4, libloadpng4.4, liblogg4.4 y sus respectivos paquetes de desarrollo *-dev. Nota que también está en el repositorio el paquete libopenlayer que ofrece acelaración por hardware para Allegro 4 pero si quieres acelaración por hardware deberías optar mejor por Allegro 5.

Para instalar Allegro 5 debes instalar todos sus paquetes y addons: liballegro5.2, liballegro-acodec5.2, liballegro-audio5.2, liballegro-dialog5.2, liballegro-image5.2, liballegro-physfs5.2, liballegro-ttf5.2, liballegro-video5.2 y sus respectivos paquetes de desarrollo *-dev.

También puedes instalar la documentación instalando los paquetes allegro4-doc y allegro5-doc.

Ahora bien, si eres usuario de Windows, puedes compilar Allegro manualmente o puedes descargar las librerías precompiladas desde esta página. Nota que estos archivos contienen las librerías para compilar programas usando Allegro y también contienen los archivos DLL necesarios para ejecutar los programas de Allegro. Yo solía usar estas versiones cuando usaba Windows y el compilador MinGW. Notarás que estas librerías precompiladas de Allegro son un poco antiguas, con la versión 5.0.10 de Allegro 5 y se pueden instalar en versiones viejas de MinGW o MS Visual Studio. Para versiones más recientes de Allegro o para instalar en compiladores más recientes puedes usar las versiones precompiladas directo de la página de Allegro que incluye varias opciones para instalar las versiones más recientes de Allegro en compiladores recientes.

Tarea de programación C: El juego de la vida de Conway

El juego de la vida de Conway es una tarea clásica de cualquier curso de programación. El juego consiste en un conjunto de reglas sencillas que definen si las células en un tablero viven o mueren. Es interesante observar cómo estas sencillas reglas pueden formar patrones complejos.

conway

La versión del juego de la vida en este post fue escrita en C con Allegro 5 como un reto de programación de 24 horas y decidí usar un tablero de tamaño relativamente grande, una ventana de 800×600 pixeles donde cada pixel es una célula, ya que algunos patrones complejos son difíciles de observar si se elige un tablero muy pequeño.

Hay que tener en cuenta que, debido al límite de tiempo, sólo estaba enfocado en terminar el reto aunque el código no fuera muy eficiente, por lo que esta versión puede fácilmente llevarse el 100% del CPU. Tengo algunas ideas para optimizar el código, editaré este post cuando aplique los cambios.

Para compilar en Linux simplemente descarga el código desde github y compila usando cmake y make:

monstruosoft@debian:~/life$ mkdir build
monstruosoft@debian:~/life$ cd build
monstruosoft@debian:~/life/build$ cmake ..
monstruosoft@debian:~/life/build$ make

El programa también debe compilarse correctamente en Windows si tienes Allegro 5 instalado.

[EDIT:] He actualizado el código en github. Las optimizaciones que hice no ayudaron mucho a reducir el uso del CPU durante la simulación pero al menos se corrigió el uso del 100% del CPU cuando la simulación estaba inactiva.

Reto de la toja azul – monstrominos

monstrominos es mi propio proyecto para el Reto de la toja azul de monstrochan. Se trata de un clón de Tetris que cuenta con dos versiones, una usando Allegro 5 y otra usando ncurses que permite correr el juego desde la terminal. Las instrucciones para compilar en Linux están incluídas pero compilar la versión de Allegro 5 debe ser fácil en Windows. En el futuro espero poder agregar la opción de compilar en Windows usando CMake así como incluir más efectos, sistema de puntuación, previsualización de la siguiente pieza, etc..

monstro-1

Tarea de programación Java: convertir a números romanos

El código Java para esta tarea es prácticamente idéntico al código C del post anterior, sólo tenemos que ponerlo dentro de un método de una clase. En este caso podemos usar la clase TareasProgramación que ya hemos usado en posts anteriores.

public class TareasProgramacion {
    private static final String ROMANOS_UNIDADES[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    private static final String ROMANOS_DECENAS[]  = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    private static final String ROMANOS_CENTENAS[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    private static final String ROMANOS_MILES[]    = {"", "M", "MM", "MMM"};

    public static String cantidadNumerosRomanos(String s) {
        StringBuilder result = new StringBuilder();
        BigDecimal totalBigDecimal = new BigDecimal(s).setScale(2, BigDecimal.ROUND_DOWN);
        long parteEntera = totalBigDecimal.toBigInteger().longValue();

        if (parteEntera  3999)
            throw new IllegalArgumentException("El número a convertir debe estar entre 1 y 3999.");

        int m = (int)parteEntera / 1000, c = (int)(parteEntera % 1000) / 100, d = (int)(parteEntera % 100) / 10, un = (int)parteEntera % 10;
        result.append(ROMANOS_MILES[m]);
        result.append(ROMANOS_CENTENAS[c]);
        result.append(ROMANOS_DECENAS[d]);
        result.append(ROMANOS_UNIDADES[un]);

        return result.toString();
    }
}

Una ejecución de un programa de prueba para el código anterior luce como la siguiente:

Escribe un número entre 1 y 3999: 
12
XII
Escribe un número entre 1 y 3999: 
1999
MCMXCIX
Escribe un número entre 1 y 3999: 
2018
MMXVIII
Escribe un número entre 1 y 3999: 
3888
MMMDCCCLXXXVIII
Escribe un número entre 1 y 3999: 
3999
MMMCMXCIX

Para obtener el código completo visita el repositorio de github de monstruosoft.

Tarea de programación C: Cantidad a números romanos

Una clásica tarea de programación, convertir una cantidad a números romanos. Normalmente verás esta tarea soportar valores en el rango de 1 a 3999 por obvias razones. Esta es la versión en lenguaje C, la versión Java en el siguiente post.

// Tarea de programación - Números romanos
#include <stdio.h>
#include <stdlib.h>

const char *miles[]    = {"", "M", "MM", "MMM"};
const char *cientos[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const char *decenas[]  = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const char *unidades[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

int main() {
    int a;

    printf("Escribe un numero entre 1 y 3999: ");
    scanf("%d", &a);

    if (a < 1 || a > 3999) {
        printf("Debes escribir un número entre 1 y 3999.\n");
        exit(0);
    }

    int m = a / 1000, c = (a % 1000) / 100, d = (a % 100) / 10, un = a % 10;
    printf("El número %d se escribe así en números romanos: %s%s%s%s\n",
            a, miles[m], cientos[c], decenas[d], unidades[un]);
}

 

Tarea de programación Java: convertir números a texto

En este post escribiremos una clase de Java que nos permita convertir un número a su representación escrita en forma de texto. Existen algunas alternativas en español pero las que he revisado tienen límites muy pequeños como convertir sólo números entre 0 y 100, o tienen límites arbitrarios como 999,999,9991 sin ninguna razón aparente. Además, ya sabemos que me gusta hacer las cosas yo mismo 😛 . El código de este post puede convertir cualquier entero positivo de tipo int en el rango de 0 a 2,147,483,647 y, en teoría, cualquier número entero menor a 1,000,000,000,000 que debería ser suficiente en la mayoría de los casos 😛 :

Read More