Soy un programador experimentado, pero nuevo en C. Estoy tratando de aprender C para poder usar la biblioteca gmp para escribir programas rápidos con números enteros grandes; eventualmente tengo la intención de escribir las partes de rendimiento de mis programas en funciones C que se llaman a través de una interfaz de función externa desde otros lenguajes. Como vehículo para aprender tanto C como la biblioteca gmp, he escrito el programa de factorización de enteros pollard rho que se muestra a continuación (sí, sé que esta no es la mejor implementación posible de pollard rho, pero es simple, y en este momento solo quiere empezar). Mi programa se compila correctamente pero cuando se ejecuta muere con el mensaje "Fallo de segmentación". Supongo que eso significa que tengo mis punteros estropeados en alguna parte, pero no lo veo. Probablemente más de uno. ¿Alguien puede mirar mi programa y decirme en qué me he equivocado? ¿Y señalar algún problema de estilo o algo más que pueda mejorar? Muchas gracias Phil

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    if (! (new = malloc(sizeof(List))))
        return NULL;
    new->data = data;
    new->next = next;
    return new;
}

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    } else {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r);
}

void rho_factors(List *fs, mpz_t n)
{
    mpz_t f;
    mpz_init_set_ui(f, 0);

    while (! (mpz_probab_prime_p(n, 25)))
    {
        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    mpz_clear(f);
    insert_in_order(n, fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s\n", argv[1]);
        return 0;
    }

    printf("%s", argv[1]);
    rho_factors(fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }

    return 0;
}

EDIT1: Gracias a Daniel Fischer, he avanzado un poco y ya no tengo un error de segmentación. El código que se muestra a continuación imprime correctamente el factor 127 cuando se llama a rho_factor con n = 1234567, pero rho_factors devuelve una lista nula, por lo que todavía hay algún problema con rho_factors. Supongo que el problema es que no puedo seguir reinicializando la misma variable de la forma en que lo estoy haciendo, pero no sé la forma correcta de hacerlo. De alguna manera necesito hacer una copia de cada factor que encuentro, luego insertar esa copia en fs. Muchas gracias Phil

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    if (! (new = malloc(sizeof(List))))
        return NULL;
    new->data = data;
    new->next = next;
    return new;

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    } else {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r, NULL);
}

void rho_factors(List *fs, mpz_t n)
{
    while (! (mpz_probab_prime_p(n, 25)))
    {
        mpz_t f;
        mpz_init_set_ui(f, 0);

        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    insert_in_order(n, fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s is prime\n", argv[1]);
        return 0;
    }

    rho_factor(f, n, 1);
    printf("%s\n", mpz_get_str(NULL, 10, f));

    printf("%s", argv[1]);
    rho_factors(fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }

    return 0;
}

EDIT2: Entendido. Gracias a Daniel Fischer. La versión final se muestra a continuación.

/* rho.c -- pollard rho factorization
 * usage: rho n -- prints factors of n then exits
 * compile as gcc -lgmp -o rho rho.c */

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

typedef struct list {
    void *data;
    struct list *next;
} List;

List *insert(void *data, List *next)
{
    List *new;

    new = malloc(sizeof(List));
    new->data = data;
    new->next = next;
    return new;
}

List *insert_in_order(void *x, List *xs)
{
    if (xs == NULL || mpz_cmp(x, xs->data) < 0)
    {
        return insert(x, xs);
    }
    else
    {
        List *head = xs;
        while (xs->next != NULL && mpz_cmp(x, xs->next->data) < 0)
        {
            xs = xs->next;
        }
        xs->next = insert(x, xs->next);
        return head;
    }
}

void rho_factor(mpz_t f, mpz_t n, long long unsigned c)
{
    mpz_t t, h, d, r;

    mpz_init_set_ui(t, 2);
    mpz_init_set_ui(h, 2);
    mpz_init_set_ui(d, 1);
    mpz_init_set_ui(r, 0);

    while (mpz_cmp_si(d, 1) == 0)
    {
        mpz_mul(t, t, t);
        mpz_add_ui(t, t, c);
        mpz_mod(t, t, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_mul(h, h, h);
        mpz_add_ui(h, h, c);
        mpz_mod(h, h, n);

        mpz_sub(r, t, h);
        mpz_gcd(d, r, n);
    }

    if (mpz_cmp(d, n) == 0)
    {
        rho_factor(f, n, c+1);
    }
    else if (mpz_probab_prime_p(d, 25))
    {
        mpz_set(f, d);
    }
    else
    {
        rho_factor(f, d, c+1);
    }

    mpz_clears(t, h, d, r, NULL);
}

void rho_factors(List **fs, mpz_t n)
{
    while (! (mpz_probab_prime_p(n, 25)))
    {
        mpz_t *f = malloc(sizeof(*f));
        mpz_init_set_ui(*f, 0);

        rho_factor(*f, n, 1);
        *fs = insert_in_order(*f, *fs);
        mpz_divexact(n, n, *f);
    }

    *fs = insert_in_order(n, *fs);
}

int main(int argc, char *argv[])
{
    mpz_t f, n;
    mpz_init_set_ui(f, 0);
    List *fs = NULL;

    if (argc<2)
    {
        printf("usage: rho n\n");
        return 1;
    }

    mpz_init_set_str(n, argv[1], 10);

    if (mpz_probab_prime_p(n, 25))
    {
        printf("%s is prime\n", argv[1]);
        return 0;
    }

    printf("Factors of %s:", argv[1]);
    rho_factors(&fs, n);
    while (fs != NULL) {
        printf(" %s", mpz_get_str(NULL, 10, fs->data));
        fs = fs->next;
    }
    printf("\n");

    return 0;
}
c gmp
1
user448810 20 feb. 2012 a las 03:05
1
Depura tu programa con gdb. Es mucho más fácil corregir ese tipo de errores si sabe dónde ocurren.
 – 
Piotr Praszmo
20 feb. 2012 a las 03:29
Banthar: Todavía no he aprendido a usar gdb.
 – 
user448810
20 feb. 2012 a las 03:37
Recuperar el rastreo es bastante simple, simplemente ejecute esos comandos.
 – 
Piotr Praszmo
20 feb. 2012 a las 03:43
1
Estoy totalmente de acuerdo con Banthar: este es solo el primer problema con el que te encuentras, pero habrá muchos más. Vale la pena la inversión, muchas veces, para aprender a utilizar un buen depurador.
 – 
reuben
20 feb. 2012 a las 03:52
Pretendo. Pero no puedo aprender todo a la vez.
 – 
user448810
20 feb. 2012 a las 04:55

1 respuesta

La mejor respuesta

No puedes reutilizar un mpz_t como ese:

void rho_factors(List *fs, mpz_t n)
{
    mpz_t f;
    mpz_init_set_ui(f, 0);

    while (! (mpz_probab_prime_p(n, 25)))
    {
        rho_factor(f, n, 1);
        fs = insert_in_order(f, fs);
        mpz_divexact(n, n, f);
    }

    mpz_clear(f);
    insert_in_order(n, fs);
}

Cuando GMP reasigna el almacenamiento al que apunta a través de f, el almacenamiento anterior es free d. Eso puede suceder en el ciclo while, pero no necesariamente. Sin embargo, si no es así, todas las entradas de la lista apuntan al mismo número.

Pero después del ciclo, cuando mpz_clear(f), cada puntero data en la lista fs se ha convertido en un puntero salvaje, y cuando luego insert_in_order(n, fs), desreferencia previamente free d punteros. (Es muy probable que eso ya suceda durante alguna inserción en el ciclo while, pero aquí está garantizado).

Además, en rho_factor, debes llamar

mpz_clears(t, h, d, r, NULL);

La lista de argumentos para mpz_clears debe ser NULL - terminada.

Otros problemas:

  • Pasa un List *, por lo que los cambios realizados en fs en rho_factors no afectan el fs en main. Pase un List ** y elimine la referencia cuando sea apropiado, también olvidó asignar el valor devuelto del insert_in_order final.
  • La variable local f queda fuera de alcance al final del bloque, lo que conduce a la corrupción. malloc apunta a mpz_t para mantenerlos con vida.

    rho_factors void (Lista ** fs, mpz_t n) { mientras (! (mpz_probab_prime_p (n, 25))) { mpz_t * f = malloc (tamaño de (* f)); mpz_init_set_ui (* f, 0);

        rho_factor(*f, n, 1);
        *fs = insert_in_order(*f, *fs);
        mpz_divexact(n, n, *f);
    }
    
    *fs = insert_in_order(n, *fs);
    

    }

Y en main

List *fs = NULL;
/* snip */
rho_factors(&fs, n);

Deberías hacerlo. Finalmente (?), Tiene una falla en insert_in_order, la comparación en el ciclo while es al revés.

3
Daniel Fischer 20 feb. 2012 a las 05:23
Entonces, la respuesta es mover las dos líneas que crean e inicializan f desde la parte superior de la función hacia dentro del ciclo, usando así una nueva f cada vez, y eliminar el claro al final del ciclo. Hice eso, pero todavía tengo una falla de segmentación.
 – 
user448810
20 feb. 2012 a las 04:02
Sí, mpz_clears necesita una lista de argumentos terminada en NULL, lo pasé por alto.
 – 
Daniel Fischer
20 feb. 2012 a las 04:27
Progreso. Ya no se produce un error de segmentación y rho_factor funciona correctamente. Pero rho_factors todavía no lo hace. Consulte EDIT1 para obtener más detalles.
 – 
user448810
20 feb. 2012 a las 04:50