● はじめに
GNU MP Library のコピーライトの年号を見ると、1991 年から 2002 年までほとんど切れ目なく続いており、現在は
Free Software Foundation, Inc. が保有しています。
「multiple precision」をなんと訳すか、やはり迷います。 無難もであり、一面を言い当てている「任意長」と訳すことにします。
まずは mpz_t つまり 任意長整数型を中心として説明しますが、途中で他の型の話も出てきます。
任意長数値データタイプの実現には malloc(), realloc(), free() を使用しています。 MP 変数が使用するメモリーのサイズは可変で、必要に応じてメモリー領域を確保します。
これを管理しているのが typedef struct の MP_INT (mpz_t[1]) です。 (整数型の場合)
MP 変数の値は "limb" 単位でメモリーに格納されています。 Limb のサイズは 32bit または 64bit です。 (あとで実地に調べます)
MP_INT のメンバー _mp_alloc, _mp_sie, _mp_d は MP 変数を管理するために使います。
MP 変数を関数の引数として使うと call-by-reference (アドレス渡し) になります。 関数内で MP 変数の値を変えると、呼び出した側での変数の値も変わります。
GMP は reentrant and thread-safe ですが、例外も多いので注意が必要です。
● mpz_t 任意長整数の宣言と初期化
まず例を示します。
void foo(void)
{
int i;
mpz_t n; /* 任意長整数の宣言 */
mpz_init(n); /* 初期化 */
for (i = 1; i <= 100; i++) {
mpz_mul(n, ...);
mpz_fdiv_q(n, ...);
...
}
mpz_clear(n); /* メモリー解放 */
}
任意長整数の宣言は、コンパイラーが MP_INT (mpz_t[1]) のためのスペースを確保するために必要です。 これは MP
変数を管理するための領域であって、MP 変数の値それ自身は別にアロケートしたメモリー領域に置かれます。
初期化は malloc() で MP 変数の値を格納するスペースを確保し、MP_INT (mpz_t[1]) のメンバーを初期化します。
あらかじめ予想される最大のスペースをアロケートするように指定することもできます。
mpz_clear() は mpz_init() でアロケートしたメモリーを解放します。 頻繁に mpz_init(), mpz_clear()
を行うと、処理時間が増大してしまいます。
・ void mpz_init (mpz_t integer)
初期化を行い、値を 0 にセットします。
・ void mpz_init2 (mpz_t integer, unsigned long n)
初期化時に変数の値を格納する n ビット分のメモリースペースをアロケートし、値を 0 にセットします。 n は初期のメモリースペースを指定する値であって、必要であれば自動アロケーターが領域を拡張します。
・ void mpz_clear (mpz_t integer)
確保していたメモリーを解放します。
・ void mpz_realloc2 (mpz_t integer, unsigned long n)
メモリースペースを n ビットに変更します。 一般に変数値は保存されますが、もしスペースが不足した場合は 0 にセットされます。
自動アロケーターが頻繁に動作してほしくない場合に使います。 確保したメモリー領域をヒープに戻したい場合にも利用できます。
・ void mpz_array_init (mpz_t integer_array[], size_t array_size, mp_size_t
fixed_num_bits)
固定長整数アレーを初期化します。 (中略) 自動アロケーターは働きません。 領域を解放する方法はありません。 mpz_clear() を使ってはなりません！
・ void * _mpz_realloc (mpz_t integer, mp_size_t new_alloc)
mpz_realloc2 と類似ですが、メモリースペースを limb の数で指定します。
● mpz_t 代入
"rop" は result operand の略でしょう。 ソースの型に対応した関数があります。
・ void mpz_set (mpz_t rop, mpz_t op)
・ void mpz_set_ui (mpz_t rop, unsigned long int op)
・ void mpz_set_si (mpz_t rop, signed long int op)
・ void mpz_set_d (mpz_t rop, double op)
・ void mpz_set_q (mpz_t rop, mpq_t op)
・ void mpz_set_f (mpz_t rop, mpf_t op)
mpz_set_d, mpz_set_q および mpz_set_f は op の値を切り捨てて整数化します。
・ int mpz_set_str (mpz_t rop, char *str, int base)
base が 0 の場合、*str の先頭文字列によって変換の基数を決定します。 文字列がその基数にとって妥当であれば 0を、そうでなければ
-1 を返します。
・ void mpz_swap (mpz_t rop1, mpz_t rop2)
変数値を交換します。
★ 初期化と代入を同時に行う関数もあります。
● 変換関数
・ unsigned long int mpz_get_ui (mpz_t op)
・ signed long int mpz_get_si (mpz_t op)
通常の整数型に変換します。 mpz_fits_ulong_p, mpz_fits_slong_p 参照。
・ double mpz_get_d (mpz_t op)
浮動小数 double 型に変換します。(範囲外の場合の記載なし)
・ double mpz_get_d_2exp (signed long int *exp, mpz_t op)
結果は関数戻り値 d と exp です。 d * 2**exp == op である近似値 d と exp を返します。ここで"**" はべき乗演算子です。
d は 0.5 <= abs(d) < 1 の範囲です。
・ char * mpz_get_str (char *str, int base, mpz_t op)
op を基数 base の NULL 終端文字列に変換します。 (2 <= base <= 36)
str が NULL の場合、文字列は現在の allocation function (Custom Allocation 参照)
によってアロケートされた領域に置かれます。
str が NULL でない場合、mpz_sizeinbase(op, base) + 2 の領域を用意しておかねばなりません。 "+2"
は負号と NULL のために必要です。
関数戻り値は、アロケートされたメモリーアドレスもしくは str の値です。
・ mp_limb_t mpz_getlimbn (mpz_t op, mp_size_t n)
番号 n の limb の値を返します。 op の符号は無視されます。 最下位 limb の番号は 0 です。 nが範囲外の場合は 0を返します。
mpz_size(mpz_top) を使うと、op が使用している limb の数がわかります。
● mpz_t 加減算および乗算
void mpz_add (mpz_t rop, mpz_t op1, mpz_t op2)
void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
Set rop toop1 + op2.
void mpz_sub (mpz_t rop, mpz_t op1, mpz_t op2)
void mpz_sub_ui(mpz_t rop, mpz_t op1, unsigned long int op2)
void mpz_ui_sub (mpz_t rop,unsigned long int op1, mpz_t op2)
Set rop to op1 - op2.
void mpz_mul (mpz_trop, mpz_t op1, mpz_t op2)
void mpz_mul_si (mpz_t rop, mpz_t op1, long intop2)
void mpz_mul_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
Set ropto op1 times op2.
void mpz_addmul (mpz_t rop, mpz_t op1, mpz_t op2)
voidmpz_addmul_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
Set rop to rop+ op1 times op2.
void mpz_submul (mpz_t rop, mpz_t op1, mpz_t op2)
void mpz_submul_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
Set rop to rop - op1 times op2.
void mpz_mul_2exp (mpz_t rop, mpz_t op1, unsigned long int op2)
Set rop to op1 times 2 raised to op2.
This operation can also be definedas a left shift by op2 bits.
void mpz_neg (mpz_t rop, mpz_t op)
Set rop to -op.
void mpz_abs (mpz_t rop, mpz_t op)
Set rop to the absolute value of op.
● mpz_t 除算
void mpz_cdiv_q (mpz_t q, mpz_t n, mpz_t d)
void mpz_cdiv_r (mpz_t r, mpz_t n, mpz_t d)
void mpz_cdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
unsigned long int mpz_cdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
unsigned long int mpz_cdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_cdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_cdiv_ui (mpz_t n, unsigned long int d)
void mpz_cdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b)
void mpz_cdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b)
void mpz_fdiv_q (mpz_t q, mpz_t n, mpz_t d)
void mpz_fdiv_r (mpz_t r, mpz_t n, mpz_t d)
void mpz_fdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
unsigned long int mpz_fdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
unsigned long int mpz_fdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_fdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_fdiv_ui (mpz_t n, unsigned long int d)
void mpz_fdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b)
void mpz_fdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b)
void mpz_tdiv_q (mpz_t q, mpz_t n, mpz_t d)
void mpz_tdiv_r (mpz_t r, mpz_t n, mpz_t d)
void mpz_tdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
unsigned long int mpz_tdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
unsigned long int mpz_tdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_tdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
unsigned long int mpz_tdiv_ui (mpz_t n, unsigned long int d)
void mpz_tdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int b)
void mpz_tdiv_r_2exp (mpz_t r, mpz_t n, unsigned long int b)
Divide n by d, forming a quotient q and/or remainder r. For the 2exp functions,
d=2^b. The rounding is in three styles, each suiting different applications.
* cdiv rounds q up towards +infinity, and r will have the opposite sign to d.
The c stands for "ceil".
* fdiv rounds q down towards -infinity, and r will have the same sign as d.
The f stands for "floor".
* tdiv rounds q towards zero, and r will have the same sign as n.
The t stands for "truncate".
In all cases q and r will satisfy n=q*d+r, and r will satisfy 0<=abs(r)<abs(d).
(中略)
void mpz_mod (mpz_t r, mpz_t n, mpz_t d)
unsigned long int mpz_mod_ui (mpz_t r, mpz_t n, unsigned long int d)
Set r to n mod d. The sign of the divisor is ignored; the result is always non-negative.
mpz_mod_ui is identical to mpz_fdiv_r_ui above, returning the remainder as well
as setting r. See mpz_fdiv_ui above if only the return value is wanted.
void mpz_divexact (mpz_t q, mpz_t n, mpz_t d)
void mpz_divexact_ui (mpz_t q, mpz_t n, unsigned long d)
Set q to n/d. These functions produce correct results only when it is known
in advance that d divides n.
These routines are much faster than the other division functions,
and are the best choice when exact division is known to occur,
for example reducing a rational to lowest terms.
int mpz_divisible_p (mpz_t n, mpz_t d)
int mpz_divisible_ui_p (mpz_t n, unsigned long int d)
int mpz_divisible_2exp_p (mpz_t n, unsigned long int b)
Return non-zero if n is exactly divisible by d, or in the case of
mpz_divisible_2exp_p by 2^b.
int mpz_congruent_p (mpz_t n, mpz_t c, mpz_t d)
int mpz_congruent_ui_p (mpz_t n, unsigned long int c, unsigned long int d)
int mpz_congruent_2exp_p (mpz_t n, mpz_t c, unsigned long int b)
Return non-zero if n is congruent to c modulo d, or in the case of
mpz_congruent_2exp_p modulo 2^b.