2011-01-29 10 views
8

Estaba leyendo un código utilizando enteros de longitud arbitraria utilizando el código de la biblioteca GNU Multi-Precision (GMP). El tipo para un entero MP es mpz_t como se define en el archivo de encabezado gmp.h.Algunas preguntas sobre una matriz de instancia única en typedef

Pero tengo algunas preguntas sobre la definición de nivel inferior de este tipo de biblioteca definida mpz_t. En el código de cabecera:

/* THIS IS FROM THE GNU MP LIBRARY gmp.h HEADER FILE */ 
typedef struct 
{ 
    /* SOME OTHER STUFF HERE */ 
} __mpz_struct; 

typedef __mpz_struct mpz_t[1]; 

Primera pregunta: ¿Tiene el asociado con el [1]__mpz_struct? En otras palabras, ¿el typedef define un tipo mpz_t como una matriz __mpz_struct con una aparición?

Segunda pregunta: ¿Por qué la matriz? (¿Y por qué solo una ocurrencia?) ¿Es este uno de esos struct hacks que he escuchado?

Tercera pregunta (quizás indirectamente con la segunda pregunta): La documentación GMP para la función mpz_init_set(mpz_t, unsigned long int) dice utilizarlo como el paso por valor solo, aunque uno asumir que esta función podría estar modificando su contenido dentro de la llamada a la función (y, por lo tanto, necesitaría pasar por la referencia) sintaxis. Consulte a mi código:

/* FROM MY CODE */ 
mpz_t fact_val;    /* declaration */ 
mpz_init_set_ui(fact_val, 1); /* Initialize fact_val */ 

¿La matriz de una sola ocurrencia permitir el paso por referencia automáticamente (debido a la ruptura de la semántica gama/puntero en C)? Admito libremente que estoy analizando demasiado esto, pero ciertamente me encantaría cualquier discusión sobre esto. ¡Gracias!

Respuesta

3

* Primera pregunta: ¿El [1] se asocia con la __mpz_struct? En otras palabras, ¿defina typedef un tipo mpz_t como una matriz __mpz_struct con una ocurrencia? *

Sí.

Segunda pregunta: ¿Por qué la matriz? (¿Y por qué solo una ocurrencia?) ¿Es este uno de esos struct hacks de los que he oído hablar?

Me late. No lo sé, pero una posibilidad es que el autor quería hacer un objeto que se pasó automáticamente por referencia, o, "sí", posiblemente el hack de estructura. Si alguna vez ves un objeto mpz_t como el último miembro de una estructura, entonces "casi con certeza" es la estructura hack. Una asignación parecida a

malloc(sizeof(struct whatever) + sizeof(mpz_t) * some_number)` 

sería un obsequio irrelevante.

¿La matriz de una sola aparición permite pasar por referencia automáticamente ...?

Aha, usted lo descubrió también. "Sí", una posible razón es simplificar el paso por referencia a expensas de referencias más complejas.

Supongo que otra posibilidad es que algo cambió en el modelo de datos o en el algoritmo, y el autor quería encontrar todas las referencias y cambiarlas de alguna manera. Un cambio en un tipo como este dejaría el programa con el mismo tipo de base pero con un error de salida de cada referencia no convertida.

+0

Curiosamente, el último elemento en la __mpz_struct es de hecho un puntero (a un mp_limb_t, que en sí mismo se escribe como unsigned long long int [what a mouthful!]). Eliminé los contenidos por el interés de la brevedad. – pr1268

4

Esto no parece ser un hack de estructura en el sentido descrito en C2. Parece que quieren mpz_t tener semántica de puntero (presumiblemente, quieren que la gente lo use como un puntero opaco). Considere la diferencia sintáctica entre los siguientes fragmentos:

struct __mpz_struct data[1]; 

(&data[0])->access = 1; 
gmp_func(data, ...); 

Y

mpz_t data; 

data->access = 1; 
gmp_func(data, ...); 

Debido C arrays decaimiento en punteros, esto también permite pase automático por referencia para el tipo mpz_t.

También le permite usar un tipo de puntero sin necesidad de malloc o free.

2

El motivo de esto proviene de la implementación de mpn. Específicamente, si estás matemáticamente inclinado, te darás cuenta de que N es el conjunto de números naturales (1,2,3,4 ...), mientras que Z es el conjunto de números enteros (..., - 2, -1,0 , 1,2, ...).

La implementación de una biblioteca bignum para Z es equivalente a hacerlo para N y teniendo en cuenta algunas reglas especiales para operaciones de signo, es decir, hacer un seguimiento de si necesita hacer una suma o una resta y cuál es el resultado.

Ahora, en cuanto a cómo se implementa una biblioteca bignum ... aquí está una línea para darle una pista:

typedef unsigned int  mp_limb_t; 
typedef mp_limb_t *  mp_ptr; 

Y ahora vamos a ver a una firma de función que opera en ese:

__GMP_DECLSPEC mp_limb_t mpn_add __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr,mp_size_t)); 

Básicamente, de lo que se trata es de que una "extremidad" es un campo entero que representa los bits de un número y el número entero se representa como una gran matriz. La parte inteligente es que gmp hace todo esto de una manera muy eficiente y bien optimizada.

De todos modos, volviendo a la discusión. Básicamente, la única forma de pasar matrices en C es, como saben, pasar punteros a esas matrices que efectivamente permite pasar por referencia. Ahora, para realizar un seguimiento de lo que está sucediendo, se definen dos tipos, un mp_ptr que es una matriz de mp_limb_t lo suficientemente grande como para almacenar su número, y mp_srcptr que es una versión constante de eso, por lo que no puede alterar accidentalmente los bits de los bignums fuente sobre lo que estás operando. La idea básica es que la mayoría de las funciones siguen este patrón:

func(ptr output, src in1, src in2) 

etc Por lo tanto, sospecho mpz_* funciones siguen esta convención simplemente para ser consistente y es porque así es como piensan los autores.

Versión corta: debido a la forma en que debe implementar una lib de bignum, es necesario.

+1

Bueno, tenía más curiosidad acerca del lenguaje/la sintaxis específica en lugar de la técnica de esta implementación, pero todavía me gusta su respuesta. +1. ¡Gracias! PD También he leído detenidamente el código fuente de la calculadora de precisión arbitraria de la línea de comandos GNU bc para ver cómo hacen grandes números programáticamente, así que esto no me resulta demasiado extraño. – pr1268

+0

@ pr1268 Hice algunos experimentos breves en mpir (una bifurcación del gmp) que nunca confié, que es porqué sé un poco sobre él, sólo pensé que lo compartiría de todos modos para la información agregada. –

Cuestiones relacionadas