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 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.

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]);
}

 

En corto No. 1 – Imprimir el valor de un uint64_t con printf

En corto es una nueva serie de posts rápidos para cosas que no merecen escribir un post completo y detallado pero que pueden ser útiles. Los temas serán variados, desde programación, Linux, software y cualquier cosa que tenga en mente 😛 .

Comenzamos con cómo imprimir el valor de una variable uint64_t en C usando printf(). En primer lugar es necesario agregar el archivo de cabecera inttypes.h, además de stdint.h que se debe agregar para usar uint64_t:

#include <stdint.h>
#include <inttypes.h>

Ahora podemos imprimir el valor de una variable uint64_t con printf() de la siguiente manera:

uint64_t variable;
printf("%" PRIu64 "\n", variable);
printf("%" PRIx64 "\n", variable); // para imprimir en hexadecimal

Referencia completa aquí.

Tarea de programación: cola dinámica

Un visitante del sitio me pidió ayuda con su tarea de programación sobre una cola dinámica en lenguaje C. El programa debía tener la opción de desplegar el contenido de la cola además de permitir agregar y quitar elementos de la cola.

Este es el código con las correcciones necesarias para que funcione y corra en Linux; también debería correr en Windows para usuarios que no estén usando el Turbo C de los años  90s, aunque debería ser sencillo hacerlo funcionar con unas cuantas modificaciones mínimas.

Espero que este post sea de ayuda para los estudiantes que siempre buscan ayuda para este tipo de tareas de programación. Seguramente seguiré haciendo posts de este tipo de acuerdo a las solicitudes de tareas mas recurrentes :P.

// Tarea de programación - Cola dinámica
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct nodo {
    int valor;
    struct nodo *siguiente;
} nodo;

nodo *cola = NULL, *ultimo = NULL;

/*
 * Esta función agrega un nuevo elemento a la cola, recibe como
 * parámetro el valor que se agregará a la cola; los nuevos elementos
 * siempre se agregan al final.
 */
int agregar(int valor) {
    nodo *n = (nodo *)malloc(sizeof(nodo));
    n->valor = valor;
    n->siguiente = NULL;

    printf("Agregando el elemento %d a la cola...\n", valor);
    if (cola == NULL && ultimo == NULL) {
        cola = n;
        ultimo = n;
    }
    else {
        ultimo->siguiente = n;
        ultimo = n;
    }

    return 0;
}

/*
 * Esta función quita un elemento de la cola, no recibe ningún
 * parámetro porque en una cola siempre se quita el elemento que
 * está al inicio.
 */
int quitar() {
    if (cola == NULL && ultimo == NULL) {
        printf("La cola está vacía, no se puede quitar ningún elemento.\n");
        return 0;
    }
    else if (cola == ultimo) {
        int valor = cola->valor;
        free(cola);
        cola = NULL;
        ultimo = NULL;
        printf("Se ha quitado el elemento %d de la cola.\n", valor);
        printf("La cola ha quedado vacía.\n");
    }
    else {
        nodo *n = cola;
        cola = n->siguiente;
        printf("Se ha quitado el elemento %d de la cola.\n", n->valor);
        free(n);
    }
}

/*
 * Muestra la cola.
 */
void mostrar() {
    nodo *n = cola;
    if (n == NULL) {
        printf("La cola está vacía.\n");
        return;
    }

    printf("Mostrando la cola...\n");
    while (n != NULL) {
        printf("\t%d\n", n->valor);
        n = n->siguiente;
    }
}

int main() {
    printf("Este programa muestra el funcionamiento de una cola dinámica.\n");
    printf("- Presiona A para insertar un nuevo elemento a la cola.\n");
    printf("- Presiona Z para quitar un elemento de la cola.\n");
    printf("- Presiona P para mostrar la cola.\n");
    printf("- Presiona Q para salir.\n");

    char key;
    while ((key = toupper(getchar())) != 'Q') {
        switch (key) {
        case 'A':
            agregar(rand());
            break;
        case 'Z':
            quitar();
            break;
        case 'P':
            mostrar();
            break;
        }
    }
    return 0;
}