メインページ   モジュール   データ構造   ファイル一覧   データフィールド   グローバル  

算術演算
[多倍長整数]


モジュール

下位関数群

マクロ定義

#define ymp_div(quotient, self, other)   ymp_divmod((quotient), NULL, (self), (other))
 多倍長整数の整除. より詳しく...

#define ymp_mod(remainder, self, other)   ymp_divmod(NULL, (remainder), (self), (other))
 多倍長整数の剰余計算. より詳しく...

#define ymp_div_digit(quotient, self, other)   (void)ymp_divmod_digit((quotient), (self), (other))
 多倍長整数のdigit_tによる整除. より詳しく...

#define ymp_mod_digit(self, other)   ymp_divmod_digit(NULL, (self), (other))
 多倍長整数のdigit_tによる剰余計算. より詳しく...

#define ymp_is_divisible(self, other)   ymp_div_if_divisible(NULL, (self), (other))
 多倍長整数が割り切れるかを判定. より詳しく...

#define ymp_is_divisible_digit(self, other)   ymp_div_if_divisible_digit(NULL, (self), (other))
 多倍長整数がdigit_tで割り切れるかを判定. より詳しく...


関数

void ymp_do_add (mp_ref_t result, mp_cref_t self, mp_cref_t other, int is_add)
 加減算を実行する。. より詳しく...

void ymp_do_add_digit (mp_ref_t result, mp_cref_t self, digit_t other, int is_add)
 digit_tとの加減算を実行する。. より詳しく...

void ymp_add (mp_ref_t result, mp_cref_t self, mp_cref_t other)
 多倍長整数の加算. より詳しく...

void ymp_sub (mp_ref_t result, mp_cref_t self, mp_cref_t other)
 多倍長整数の減算. より詳しく...

void ymp_add_digit (mp_ref_t result, mp_cref_t self, digit_t val)
 多倍長整数にdigit_tを足す. より詳しく...

void ymp_sub_digit (mp_ref_t result, mp_cref_t self, digit_t val)
 多倍長整数からdigit_tを引く. より詳しく...

void ymp_neg (mp_ref_t result, mp_cref_t orig)
 多倍長整数の符号反転. より詳しく...

void ymp_divmod (mp_ref_t quotient, mp_ref_t remainder, mp_cref_t self, mp_cref_t other)
 多倍長整数の除算. より詳しく...

digit_t ymp_divmod_digit (mp_ref_t quotient, mp_cref_t self, digit_t other)
 多倍長整数の、digit_tによる除算. より詳しく...

int ymp_div_if_divisible (mp_ref_t quotient, mp_cref_t self, mp_cref_t other)
 多倍長整数を、もし可能なら割る. より詳しく...

int ymp_div_if_divisible_digit (mp_ref_t quotient, mp_cref_t self, digit_t other)
 多倍長整数をdigit_tで、もし可能なら割る. より詳しく...

void ymp_mul (mp_ref_t result, mp_cref_t self, mp_cref_t other)
 多倍長整数同士を掛ける. より詳しく...

void ymp_modmul (mp_ref_t result, mp_cref_t self, mp_cref_t other, mp_cref_t modulus)
 多倍長整数の積の剰余を求める. より詳しく...

void ymp_modmul_2exp (mp_ref_t result, mp_cref_t self, mp_cref_t other, size_t pow)
 多倍長自然数の積の、2の冪による剰余を求める. より詳しく...

void ymp_mul_digit (mp_ref_t result, mp_cref_t self, digit_t other)
 多倍長整数にdigit_tを掛ける. より詳しく...

void ymp_pow (mp_ref_t result, mp_cref_t self, size_t pow)
 多倍長整数の冪 (冪指数はsize_t). より詳しく...

void ymp_modpow_z (mp_ref_t result, mp_cref_t self, mp_cref_t modulus, size_t pow)
 多倍長整数の冪の剰余を求める(冪指数はsize_t). より詳しく...

void ymp_modpow_2exp_z (mp_ref_t result, mp_cref_t self, size_t emod, size_t pow)
 多倍長整数の冪の、2の冪による剰余を求める(冪指数はsize_t). より詳しく...

void ymp_modpow (mp_ref_t result, mp_cref_t self, mp_cref_t modulus, mp_cref_t pow)
 多倍長整数の冪の剰余を求める(冪指数は多倍長). より詳しく...

void ymp_mul_2exp (mp_ref_t result, mp_cref_t self, size_t pow)
 多倍長整数を2の冪乗倍する. より詳しく...

void ymp_div_2exp (mp_ref_t result, mp_cref_t self, size_t pow)
 多倍長整数を2の冪乗で割る. より詳しく...

void ymp_mod_2exp (mp_ref_t result, mp_cref_t self, size_t pow)
 多倍長整数を2の冪乗で割った剰余. より詳しく...

void ymp_iroot (mp_ref_t result, mp_cref_t self, size_t pow)
 多倍長整数の冪乗根の整数部分. より詳しく...

マクロ定義の解説

#define ymp_div (  quotient,
self,
other    )     ymp_divmod((quotient), NULL, (self), (other))
 

多倍長整数の整除.

引数:
quotient  商を格納するstruct multiprecへのポインタ。
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
quotient, self, otherは初期化済のこと
覚え書き:
quotient, self, otherは一致しても良い
事後条件:
余りがある場合は、商は0に近いほうをとる
  • i.e. <quotient> = sign(<self>) * floor( |<self>| / |<other>| )
  • i.e. 剰余は<self>と同符号

multiprec.h の 458 行で定義されています。

呼出 ymp_iroot.

#define ymp_mod (  remainder,
self,
other    )     ymp_divmod(NULL, (remainder), (self), (other))
 

多倍長整数の剰余計算.

引数:
remainder  剰余を格納するstruct multiprecへのポインタ。
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
remainder, self, otherは初期化済のこと
覚え書き:
remainder, self, otherは一致しても良い
事後条件:
剰余は<self>と同符号

multiprec.h の 470 行で定義されています。

呼出 ymp_binary_sunzi, と ymp_modinv.

#define ymp_div_digit (  quotient,
self,
other    )     (void)ymp_divmod_digit((quotient), (self), (other))
 

多倍長整数のdigit_tによる整除.

引数:
quotient  商を格納するstruct multiprecへのポインタ。
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
quotient, self, otherは初期化済のこと
覚え書き:
quotient, self, otherは一致しても良い
事後条件:
商は剰余が非負になるように計算される

multiprec.h の 482 行で定義されています。

#define ymp_mod_digit (  self,
other    )     ymp_divmod_digit(NULL, (self), (other))
 

多倍長整数のdigit_tによる剰余計算.

引数:
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
self, otherは初期化済のこと
覚え書き:
self, otherは一致しても良い
戻り値:
計算された剰余
事後条件:
剰余rは 0 <= r < |<other>|

multiprec.h の 494 行で定義されています。

#define ymp_is_divisible (  self,
other    )     ymp_div_if_divisible(NULL, (self), (other))
 

多倍長整数が割り切れるかを判定.

引数:
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
self, otherは初期化済のこと
otherの表す多倍長整数値は0でないこと。0の場合、ymp_fatalを呼ぶ。
戻り値:
1  selfがotherで割り切れた場合
0  selfがotherで割り切れない場合

multiprec.h の 512 行で定義されています。

#define ymp_is_divisible_digit (  self,
other    )     ymp_div_if_divisible_digit(NULL, (self), (other))
 

多倍長整数がdigit_tで割り切れるかを判定.

引数:
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数(digit_t)
事前条件:
selfは初期化済のこと
otherは0でないこと。0の場合、ymp_fatalを呼ぶ。
戻り値:
1  selfがotherで割り切れた場合
0  selfがotherで割り切れない場合

multiprec.h の 524 行で定義されています。

関数の解説

void ymp_do_add (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other,
int    is_add
)  [inline, static]
 

加減算を実行する。.

is_addが非0のとき
  • resultの符号を、selfの符号にする。
  • resultの絶対値を、selfの絶対値とotherの絶対値の和にする
is_addが0のとき
  • resultの符号を、selfとotherのうち絶対値の大きいほうの符号にする
  • resultの絶対値を、selfの絶対値とotherの絶対値の差にする
事前条件:
result, self, otherは初期化済のこと
覚え書き:
result, self, otherが一致してもよい

addsub.c の 127 行で定義されています。

参照 multiprec::digits, mp_cref_t, positive_sign, multiprec::sign, multiprec::used, ymp_addabs, ymp_reserve, と ymp_subabs.

呼出 ymp_add, と ymp_sub. 

00128 {
00129   if (self->used > other->used)
00130     {
00131       if (is_add)
00132         {
00133           ymp_reserve(result, self->used+1);
00134           result->used
00135             = ymp_addabs(result->digits, self->digits, other->digits,
00136                          self->used, other->used);
00137           result->sign = self->sign;
00138         }
00139       else
00140         {
00141           ymp_reserve(result, self->used);
00142           result->used
00143             = ymp_subabs(result->digits, self->digits, other->digits,
00144                          self->used, other->used);
00145           result->sign = self->sign;
00146         }
00147       return;
00148     }
00149   else if (self->used < other->used)
00150     {
00151       if (is_add)
00152         {
00153           ymp_reserve(result, other->used+1);
00154           result->used
00155             = ymp_addabs(result->digits, other->digits, self->digits,
00156                          other->used, self->used);
00157           result->sign = self->sign;
00158         }
00159       else
00160         {
00161           ymp_reserve(result, other->used);
00162           result->used
00163             = ymp_subabs(result->digits, other->digits, self->digits,
00164                          other->used, self->used);
00165           result->sign = !self->sign;
00166         }
00167       return;
00168     }
00169 
00170 
00171 
00172   /* self->used == other->used */
00173 
00174   if (is_add)
00175     {
00176       ymp_reserve(result, self->used+1);
00177       result->used
00178         = ymp_addabs(result->digits, self->digits, other->digits,
00179                      self->used, other->used);
00180       result->sign = self->sign;
00181     }
00182   else 
00183     {
00184       size_t i = self->used;
00185       while (i-- > 0)
00186         {
00187           if ( self->digits[i] > other->digits[i])
00188             {
00189               ymp_reserve(result, ++i);
00190               result->used
00191                 = ymp_subabs(result->digits, self->digits, other->digits,
00192                              i, i);
00193               result->sign = self->sign;
00194               return;
00195             }
00196           else if (self->digits[i] < other->digits[i])
00197             {
00198               ymp_reserve(result, ++i);
00199               result->used
00200                 = ymp_subabs(result->digits, other->digits, self->digits,
00201                              i, i);
00202               result->sign = !self->sign;
00203               return;
00204             }
00205         }
00206       result->sign = positive_sign;
00207       result->used = 0;
00208     }
00209 }

void ymp_do_add_digit (  mp_ref_t    result,
mp_cref_t    self,
digit_t    other,
int    is_add
)  [inline, static]
 

digit_tとの加減算を実行する。.

is_addが非0のとき
  • resultの符号を、selfの符号にする。
  • resultの絶対値を、selfの絶対値とotherの絶対値の和にする
is_addが0のとき
  • resultの符号を、selfとotherのうち絶対値の大きいほうの符号にする
  • resultの絶対値を、selfの絶対値とotherの絶対値の差にする
事前条件:
result, selfは初期化済のこと
覚え書き:
self, resultが一致してもよい

addsub.c の 228 行で定義されています。

参照 digit_t, multiprec::digits, double_digit_t, HIGH_DIGIT, LOW_DIGIT, mp_cref_t, multiprec::sign, multiprec::used, ymp_addabs, ymp_reserve, と ymp_subabs.

呼出 ymp_add_digit, と ymp_sub_digit. 

00229 {
00230   switch (self->used)
00231     {
00232     case 0:
00233       ymp_reserve(result, 1);
00234       result->sign = self->sign;
00235       result->used = 1;
00236       result->digits[0] = other;
00237       return;
00238 
00239     case 1:
00240       if (is_add)
00241         {
00242           double_digit_t tmp;
00243 
00244           ymp_reserve(result, 2);
00245           result->sign = self->sign;
00246           result->used = 1;
00247 
00248           tmp = other;
00249           tmp += self->digits[0];
00250 
00251           result->digits[0] = LOW_DIGIT(tmp);
00252           if ( (tmp = HIGH_DIGIT(tmp)) )
00253             {
00254               self->digits[1] = LOW_DIGIT(tmp);
00255               ++result->used;
00256             }
00257           return;
00258         }
00259       else
00260         {
00261           ymp_reserve(result, 1);
00262           result->used = 1;
00263           if (self->digits[0] > other)
00264             {
00265               result->sign = self->sign;
00266               result->digits[0] = self->digits[0] - other;
00267             }
00268           else
00269             {
00270               result->sign = !self->sign;
00271               self->digits[0] = other - self->digits[0];
00272             }
00273           return;
00274         }
00275     default:
00276       if (is_add)
00277         {
00278           ymp_reserve(result, self->used+1);
00279           result->used 
00280             = ymp_addabs(result->digits, self->digits, &other, self->used, 1);
00281           result->sign = self->sign;
00282           return;
00283         }
00284       else
00285         {
00286           ymp_reserve(result, self->used+1);
00287           result->used
00288             = ymp_subabs(result->digits, self->digits, &other, self->used, 1);
00289           result->sign = self->sign;
00290           return;
00291         }
00292     }
00293 }

void ymp_add (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other
) 
 

多倍長整数の加算.

<result>に<self> + <other>を格納する

引数:
self  足される数を表すstruct multiprecへのポインタ
other  足す数を表すstruct multiprecへのポインタ
result  結果を格納するstruct multiprecへのポインタ
事前条件:
result, self, otherは初期化済のこと
覚え書き:
result, self, otherが一致してもよい

addsub.c の 309 行で定義されています。

参照 mp_cref_t, multiprec::sign, と ymp_do_add. 

00310 {
00311   ymp_do_add(result, self, other, self->sign==other->sign);
00312 }

void ymp_sub (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other
) 
 

多倍長整数の減算.

<result>に<self> - <other>を格納する

引数:
self  引かれる数を表すstruct multiprecへのポインタ
other  引く数を表すstruct multiprecへのポインタ
result  結果を格納するstruct multiprecへのポインタ
事前条件:
result, self, otherは初期化済のこと
覚え書き:
result, self, otherが一致してもよい

addsub.c の 324 行で定義されています。

参照 mp_cref_t, multiprec::sign, と ymp_do_add. 

00325 {
00326   ymp_do_add(result, self, other, self->sign!=other->sign);
00327 }

void ymp_add_digit (  mp_ref_t    result,
mp_cref_t    self,
digit_t    val
) 
 

多倍長整数にdigit_tを足す.

引数:
result  和を格納するstruct multiprecへのポインタ
self  足される数を表すstruct multiprecへのポインタ
val  足す数
事前条件:
result, selfは初期化済のこと

addsub.c の 339 行で定義されています。

参照 digit_t, mp_cref_t, positive_sign, multiprec::sign, と ymp_do_add_digit. 

00340 {
00341   ymp_do_add_digit(result, self, val, self->sign==positive_sign);
00342 }

void ymp_sub_digit (  mp_ref_t    result,
mp_cref_t    self,
digit_t    val
) 
 

多倍長整数からdigit_tを引く.

引数:
result  差を格納するstruct multiprecへのポインタ
self  引かれる数を表すstruct multiprecへのポインタ
val  引く数
事前条件:
result, selfは初期化済のこと

addsub.c の 352 行で定義されています。

参照 digit_t, mp_cref_t, positive_sign, multiprec::sign, と ymp_do_add_digit. 

00353 {
00354   ymp_do_add_digit(result, self, val, self->sign!=positive_sign);
00355 }

void ymp_neg (  mp_ref_t    result,
mp_cref_t    orig
) 
 

多倍長整数の符号反転.

<result> := -<self>

引数:
result  結果を格納するstruct multiprecへのポインタ
orig  元の数を格納しているstruct multiprecへのポインタ
事前条件:
result, origは初期化済のこと

addsub.c の 366 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, と ymp_reserve. 

00367 {
00368   result->sign = !orig->sign;
00369   if (result != orig)
00370     {
00371       ymp_reserve(result, orig->used);
00372       result->used = orig->used;
00373       memcpy(result->digits, orig->digits, sizeof(digit_t)*orig->used);
00374     }
00375 }

void ymp_divmod (  mp_ref_t    quotient,
mp_ref_t    remainder,
mp_cref_t    self,
mp_cref_t    other
) 
 

多倍長整数の除算.

引数:
quotient  商を格納するstruct multiprecへのポインタ 商が不要ならNULLを指定する
remainder  剰余を格納するstruct multiprecへのポインタ 剰余が不要ならNULLを指定する
self  割られる数を表すstruct multiprecへのポインタ
other  割る数を表すstruct multiprecへのポインタ
事前条件:
selfとotherおよび、もしNULLでないならquotientやremainderは、 初期化済のこと
otherの表す多倍長整数値は0でないこと。0の場合、ymp_fatalを呼ぶ。
quotient!=remainder. 等しい場合は動作は不定
事後条件:
商は floor(<self> / <other>)であり、<self>と同符号
剰余rは0 <= |r| < |<other>|で、<self>ど同符号

div.c の 262 行で定義されています。

参照 multiprec::digits, mp_cref_t, mp_sign_t, multiprec::sign, multiprec::used, ymp_assign, ymp_divmodabs, ymp_fatal, ymp_is_zero, と ymp_reserve. 

00264 {
00265   enum mp_sign_t rem_sign;
00266   size_t rem_used;
00267 
00268   /* 0除算を弾く */
00269   if (ymp_is_zero(other))
00270     {
00271       ymp_fatal("0による除算");
00272       return;
00273     }
00274 
00275   /* 明らかに (被除数) < (除数) と分かる場合:
00276      商は0、剰余は被除数に等しい */
00277   if (self->used < other->used)
00278     {
00279       if (quotient) quotient->used = 0;
00280       if (self != remainder && remainder) ymp_assign(remainder, self);
00281       return;
00282     }
00283 
00284   /* 商・剰余の格納に十分な領域を確保 */
00285   if (quotient) ymp_reserve(quotient, self->used-other->used+1);
00286   if (remainder) ymp_reserve(remainder, other->used);
00287 
00288   /* 絶対値同士の除算を行う */
00289   rem_sign = self->sign;
00290   rem_used = ymp_divmodabs(quotient?quotient->digits:NULL, 
00291                            remainder?remainder->digits:NULL, 
00292                            self->digits, other->digits,
00293                            self->used, other->used);
00294   
00295   /*
00296    *  remainder==selfまたはremainder==otherのときにも
00297    *  商のの符号と桁数の調整に影響を与えないように、
00298    *  剰余の符号と桁数は直ぐには書き込まない
00299    */
00300 
00301   if (quotient)
00302     {
00303       /* 商の符号と桁数の調整 */
00304       quotient->sign = self->sign != other->sign;
00305       quotient->used = self->used - other->used + 1;
00306       if (!quotient->digits[quotient->used-1]) --quotient->used;
00307     }
00308 
00309   if (remainder)
00310     {
00311       /* 剰余の符号と桁数を書き込む */
00312       remainder->sign = rem_sign;
00313       remainder->used = rem_used;
00314     }
00315 }

digit_t ymp_divmod_digit (  mp_ref_t    quotient,
mp_cref_t    self,
digit_t    other
) 
 

多倍長整数の、digit_tによる除算.

引数:
quotient  商を格納するstruct multiprecへのポインタ 商が不要ならNULLを指定する
self  割られる数を表すstruct multiprecへのポインタ
other  割る数
事前条件:
selfおよび、もしNULLでないならquotientは、初期化済のこと
戻り値:
剰余
事後条件:
商は floor(<self> / <other>)であり、<self>と同符号
剰余rは0 <= r < other
覚え書き:
rhsが0の場合、ymp_fatalを呼ぶ。
quotient, selfは一致しても良い

div.c の 333 行で定義されています。

参照 digit_t, multiprec::digits, multiprec::len, mp_cref_t, multiprec::sign, multiprec::used, ymp_addabs, ymp_divmodabs_digit, ymp_fatal, と ymp_reserve. 

00334 {
00335   digit_t rem; /* 剰余の絶対値 */
00336 
00337   /* 0除算を弾く */
00338   if (other == 0)
00339     {
00340       ymp_fatal("0による除算");
00341       return 0;
00342     }
00343 
00344   /* 被除数が0の場合、商と剰余も0 */
00345   if (self->used == 0)
00346     {
00347       if (quotient) quotient->used = 0;
00348       return 0;
00349     }
00350 
00351   /* 商を格納するのに十分な領域を確保 */
00352   if (quotient) ymp_reserve(quotient, self->used);
00353 
00354   /* 絶対値の除算を行う */
00355   rem = ymp_divmodabs_digit(quotient?quotient->digits:NULL,
00356                             self->digits,
00357                             other,
00358                             self->used);
00359 
00360   /* 桁数と符号の設定 */
00361   if (quotient)
00362     {
00363       if (quotient->digits[quotient->used-1]) --quotient->used;
00364       quotient->sign = self->sign;
00365     }
00366 
00367   if (self->sign && rem)
00368     {
00369       /* 剰余が正になるように調整 */
00370       if (quotient)
00371         {
00372           quotient->used = ymp_addabs(quotient->digits, quotient->digits, 
00373                                       &other, quotient->len, 1);
00374         }
00375       return other - rem;
00376     }
00377   else
00378     {
00379       return rem;
00380     }
00381 }

int ymp_div_if_divisible (  mp_ref_t    quotient,
mp_cref_t    self,
mp_cref_t    other
) 
 

多倍長整数を、もし可能なら割る.

selfがotherで割れるかどうか調べ、もし割り切れるなら商をquotientに代入する 割り切れないときはquotientは変化しない

引数:
quotient  商を格納するためのstruct multiprecへのポインタ。 商が不用ならNULLを指定する
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数を表すstruct multiprecへのポインタ。
事前条件:
self, otherおよび、もしNULLでないならquotientは、初期化済のこと
otherの表す多倍長整数値は0でないこと。0の場合、ymp_fatalを呼ぶ。
戻り値:
1  selfがotherで割り切れた場合
0  selfがotherで割り切れない場合
事後条件:
もし格納されたなら、商は floor(<self> / <other>)であり、<self>と同符号

div.c の 399 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_divmodabs, ymp_fatal, ymp_is_zero, ymp_reserve, と YMP_TEMP_ALLOCATE. 

00400 {
00401   size_t rem_used; /* 剰余の桁数 */
00402   digit_t *quot_buf=NULL, *rem_buf=NULL; /* 商・剰余の一時格納用 */
00403 
00404   /* 0除算を弾く */
00405   if (ymp_is_zero(other))
00406     {
00407       ymp_fatal("0による除算");
00408       return 2;
00409     }
00410 
00411   /* 明らかな場合 */
00412   if (self->used < other->used)
00413     {
00414       if (ymp_is_zero(self))
00415         {
00416           if (quotient) quotient->used = 0;
00417           return 1;
00418         }
00419       else
00420         {
00421           return 0;
00422         }
00423     }
00424 
00425   /* 格納領域を確保 */
00426   if (quotient) YMP_TEMP_ALLOCATE(quot_buf, digit_t, self->used-other->used+1);
00427   YMP_TEMP_ALLOCATE(rem_buf, digit_t, other->used);
00428 
00429   /* 絶対値の除算を実行 */
00430   rem_used = ymp_divmodabs(quot_buf, rem_buf, self->digits, other->digits,
00431                            self->used, other->used);
00432 
00433   /* 剰余が0なら (そのときrem_usedは必ず0) */
00434   if (rem_used==0)
00435     {
00436       if (quotient)
00437         {
00438           /* *quotientに商のデータをコピー */
00439           size_t quot_used;
00440           quotient->sign = self->sign != other->sign;
00441           
00442           quot_used = self->used - other->used + 1;
00443           if (!quot_buf[quot_used-1]) --quot_used;
00444           quotient->used = quot_used;
00445           ymp_reserve(quotient, quot_used);
00446           memcpy(quotient->digits, quot_buf, quot_used);
00447         }
00448       return 1;
00449     }
00450   else
00451     {
00452       return 0;
00453     }
00454 }

int ymp_div_if_divisible_digit (  mp_ref_t    quotient,
mp_cref_t    self,
digit_t    other
) 
 

多倍長整数をdigit_tで、もし可能なら割る.

selfがotherで割れるかどうか調べ、もし割り切れるなら商をquotientに代入する 割り切れないときはquotientは変化しない

引数:
quotient  商を格納するためのstruct multiprecへのポインタ。 商が不用ならNULLを指定する
self  割られる数を表すstruct multiprecへのポインタ。
other  割る数
事前条件:
selfおよび、もしNULLでないならquotientは、初期化済のこと
otherは0でないこと。0の場合、ymp_fatalを呼ぶ。
戻り値:
1  selfがotherで割り切れた場合
0  selfがotherで割り切れない場合
事後条件:
もし格納されたなら、商は floor(<self> / <other>)であり、<self>と同符号

div.c の 474 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_divmodabs_digit, ymp_fatal, ymp_is_zero, ymp_reserve, と YMP_TEMP_ALLOCATE. 

00475 {
00476   digit_t rem;
00477   digit_t *quot_buf=NULL;
00478 
00479   /* 0除算を弾く */
00480   if (other == 0)
00481     {
00482       ymp_fatal("0による除算");
00483       return 2;
00484     }
00485 
00486   /* 明らかな場合 */
00487   if (ymp_is_zero(self))
00488     {
00489       if (quotient) quotient->used = 0;
00490       return 1;
00491     }
00492 
00493   /* 格納領域を確保 */
00494   if (quotient) YMP_TEMP_ALLOCATE(quot_buf, digit_t, self->used);
00495 
00496   /* 絶対値の除算を実行 */
00497   rem = ymp_divmodabs_digit(quot_buf, self->digits, other, self->used);
00498 
00499   /* 剰余が0なら */
00500   if (rem == 0)
00501     {
00502       if (quotient)
00503         {
00504           /* *quotientに商のデータをコピー */
00505           size_t quot_used;
00506           quotient->sign = self->sign;
00507           
00508           quot_used = self->used;
00509           if (!quot_buf[quot_used-1]) --quot_used;
00510           quotient->used = quot_used;
00511           ymp_reserve(quotient, quot_used);
00512           memcpy(quotient->digits, quot_buf, quot_used);
00513         }
00514       return 1;
00515     }
00516   else
00517     {
00518       return 0;
00519     }
00520 }

void ymp_mul (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other
) 
 

多倍長整数同士を掛ける.

引数:
result  積を格納するstruct multiprecヘのポインタ
self  掛けられる数を表すstruct multiprecへのポインタ
other  掛ける数を表すstruct multiprecへのポインタ
事前条件:
result, self, otherは初期化済のこと
覚え書き:
result, self, otherは一致しても良い

mul.c の 237 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_mulabs, ymp_reserve, と YMP_TEMP_ALLOCATE. 

00238 {
00239   digit_t *self_digits = self->digits;
00240   digit_t *other_digits = other->digits;
00241   if (result == self)
00242     {
00243       YMP_TEMP_ALLOCATE(self_digits, digit_t, self->used);
00244       memcpy(self_digits, self->digits, sizeof(digit_t)*self->used);
00245     }
00246   if (result == other)
00247     {
00248       YMP_TEMP_ALLOCATE(other_digits, digit_t, self->used);
00249       memcpy(other_digits, other->digits, sizeof(digit_t)*self->used);
00250     }
00251 
00252   ymp_reserve(result, self->used+other->used);
00253   result->used = ymp_mulabs(result->digits, self_digits, other_digits,
00254                             self->used, other->used);
00255 
00256   result->sign = self->sign != other->sign;
00257 }

void ymp_modmul (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other,
mp_cref_t    modulus
) 
 

多倍長整数の積の剰余を求める.

<result> := <self> * <other> % <modulus>

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  掛けられる数を表すstruct multiprecへのポインタ
other  掛ける数を表すstruct multiprecへのポインタ
modulus  法を表すstruct multiprecへのポインタ
事前条件:
result, self, other, modulusは初期化済のこと
覚え書き:
result, self, other, modulusは一致しても良い
事後条件:
結果<result>は、<self>*<other>と同符号で 絶対値は 0 <= |<result>| < |<modulus>|

mul.c の 275 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_modmulabs, ymp_reserve, と YMP_TEMP_ALLOCATE. 

00276 {
00277   digit_t *self_digits = self->digits;
00278   digit_t *other_digits = other->digits;
00279 
00280   if (result == self)
00281     {
00282       YMP_TEMP_ALLOCATE(self_digits, digit_t, self->used);
00283       memcpy(self_digits, self->digits, sizeof(digit_t)*self->used);
00284     }
00285   if (result == other)
00286     {
00287       YMP_TEMP_ALLOCATE(other_digits, digit_t, self->used);
00288       memcpy(other_digits, other->digits, sizeof(digit_t)*self->used);
00289     }
00290 
00291   ymp_reserve(result, modulus->used);
00292 
00293   result->used = ymp_modmulabs(result->digits, 
00294                                self_digits, other->digits, modulus->digits,
00295                                self->used, other->used, modulus->used);
00296 
00297   result->sign = self->sign != other->sign;
00298 }

void ymp_modmul_2exp (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    other,
size_t    pow
) 
 

多倍長自然数の積の、2の冪による剰余を求める.

<result> := <self> * <other> % (2**pow)

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  掛けられる数を表すstruct multiprecへのポインタ
other  掛ける数を表すstruct multiprecへのポインタ
pow  法の冪指数
事前条件:
result, self, otherは初期化済のこと
覚え書き:
result, self, otherは一致しても良い
事後条件:
結果<result>は、<self>*<other>と同符号で 絶対値は 0 <= |<result>| < 2**pow

mul.c の 315 行で定義されています。

参照 DIGIT_BIT, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_modmulabs_2exp, と ymp_reserve. 

00316 {
00317   ymp_reserve(result, pow/DIGIT_BIT + 1);
00318 
00319   result->used = ymp_modmulabs_2exp(result->digits, 
00320                                     self->digits, other->digits,
00321                                     pow, self->used, other->used);
00322 
00323   result->sign = self->sign != other->sign;
00324 }

void ymp_mul_digit (  mp_ref_t    result,
mp_cref_t    self,
digit_t    other
) 
 

多倍長整数にdigit_tを掛ける.

引数:
result  積を格納するstruct multiprecヘのポインタ
self  掛けられる数を表すstruct multiprecへのポインタ
other  掛ける数
事前条件:
result, selfは初期化済のこと
覚え書き:
result, selfは一致しても良い

mul.c の 337 行で定義されています。

参照 digit_t, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_mulabs_digit, と ymp_reserve. 

00338 {
00339   ymp_reserve(result, self->used+1);
00340   result->used = ymp_mulabs_digit(result->digits, 
00341                                   self->digits, other, self->used);
00342   result->sign = self->sign;
00343 }

void ymp_pow (  mp_ref_t    result,
mp_cref_t    self,
size_t    pow
) 
 

多倍長整数の冪 (冪指数はsize_t).

<result> := <self>**<pow>

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  底を表すstruct multiprecへのポインタ
pow  冪指数
事前条件:
result, selfは初期化済のこと
覚え書き:
result, selfは一致しても良い

mul.c の 647 行で定義されています。

参照 multiprec::digits, MAX, mp_cref_t, multiprec::sign, multiprec::used, ymp_powabs, と ymp_reserve. 

00648 {
00649   /* 結果の格納領域を確保 */
00650   ymp_reserve(result, self->used*MAX(pow, 1));
00651 
00652   result->sign = self->sign && (pow & 0x01);
00653   result->used = ymp_powabs(result->digits, self->digits, self->used, pow);
00654 }

void ymp_modpow_z (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    modulus,
size_t    pow
) 
 

多倍長整数の冪の剰余を求める(冪指数はsize_t).

<result> := <self>**<pow> % <modulus>

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  底を表すstruct multiprecへのポインタ
modulus  法を表すstruct multiprecへのポインタ
pow  冪指数
事前条件:
result, self, modulusは初期化済のこと
覚え書き:
result, self, modulusは一致しても良い
事後条件:
結果<result>は、<self> ** powと同符号で 絶対値は 0 <= |<result>| < |<modulus>|

mul.c の 670 行で定義されています。

参照 multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_modpowabs_z, と ymp_reserve. 

00671 {
00672   /* 十分な格納領域を確保 */
00673   ymp_reserve(result, modulus->used);
00674 
00675   result->sign = self->sign && (pow & 0x01);
00676   result->used = ymp_modpowabs_z(result->digits, self->digits, modulus->digits,
00677                                  self->used, modulus->used, pow);
00678 }

void ymp_modpow_2exp_z (  mp_ref_t    result,
mp_cref_t    self,
size_t    emod,
size_t    pow
) 
 

多倍長整数の冪の、2の冪による剰余を求める(冪指数はsize_t).

<result> := <self>**<pow> % (2**emod)

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  底を表すstruct multiprecへのポインタ
emod  法の冪指数
pow  冪指数
事前条件:
result, selfは初期化済のこと
覚え書き:
result, selfは一致しても良い
事後条件:
結果<result>は、<self> ** powと同符号で 絶対値は 0 <= |<result>| < |2**emod|

mul.c の 695 行で定義されています。

参照 DIGIT_BIT, multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_modpowabs_2exp_z, と ymp_reserve. 

00696 {
00697   /* 十分な格納領域を確保 */
00698   ymp_reserve(result, emod / DIGIT_BIT + 1);
00699 
00700   result->sign = self->sign && (pow & 0x01);
00701   result->used = ymp_modpowabs_2exp_z(result->digits, self->digits,
00702                                       self->used, emod, pow);
00703 }

void ymp_modpow (  mp_ref_t    result,
mp_cref_t    self,
mp_cref_t    modulus,
mp_cref_t    pow
) 
 

多倍長整数の冪の剰余を求める(冪指数は多倍長).

<result> := <self>**<pow> % <modulus>

引数:
result  結果を格納するstruct multiprecヘのポインタ
self  底を表すstruct multiprecへのポインタ
modulus  法を表すstruct multiprecへのポインタ
pow  冪指数を表すstruct multiprecへのポインタ
事前条件:
result, self, modulus, powは初期化済のこと
覚え書き:
result, self, modulus, powは一致しても良い

mul.c の 718 行で定義されています。

参照 multiprec::digits, mp_cref_t, multiprec::sign, multiprec::used, ymp_modpowabs, と ymp_reserve. 

00719 {
00720   /* 十分な格納領域を確保 */
00721   ymp_reserve(result, modulus->used);
00722 
00723   result->sign = self->sign && (pow->used != 0 || (pow->digits[0] & 0x01));
00724   result->used = ymp_modpowabs(result->digits, 
00725                                self->digits, modulus->digits, pow->digits,
00726                                self->used, modulus->used, pow->used);
00727 }

void ymp_mul_2exp (  mp_ref_t    result,
mp_cref_t    self,
size_t    pow
) 
 

多倍長整数を2の冪乗倍する.

<self>に2のpow乗を掛けた積をresultに格納する。

引数:
result  積を格納するstruct multiprecへのポインタ
self  元の数を表すstruct multiprecへのポインタ
pow  冪指数
覚え書き:
selfとresultは一致してもよい

shift.c の 169 行で定義されています。 

00170 {
00171   result->sign = self->sign;
00172   ymp_reserve(result, self->used+pow/DIGIT_BIT+1);
00173   result->used = ymp_lshiftabs(result->digits, self->digits, self->used, pow);
00174 }

void ymp_div_2exp (  mp_ref_t    result,
mp_cref_t    self,
size_t    pow
) 
 

多倍長整数を2の冪乗で割る.

<self>を2のpow乗で割った商をresultに格納する。

引数:
result  商を格納するstruct multiprecへのポインタ
self  元の数を表すstruct multiprecへのポインタ
pow  冪指数
覚え書き:
selfとresultは一致してもよい
割り切れない場合は、0に近い方を商としてとる。
  • i.e. <result> = sign(<self>) * floor( |<self>/2**pow| ) である。
  • i.e. 剰余は<self>と同符号

shift.c の 189 行で定義されています。 

00190 {
00191   size_t n_shift_digits = pow/DIGIT_BIT;
00192 
00193   if (self->used > n_shift_digits)
00194     {
00195       result->sign = self->sign;
00196       ymp_reserve(result, self->used - n_shift_digits);
00197       result->used
00198         = ymp_rshiftabs(result->digits, self->digits, self->used, pow);
00199     }
00200   else
00201     {
00202       result->used = 0;
00203     }
00204 }

void ymp_mod_2exp (  mp_ref_t    result,
mp_cref_t    self,
size_t    pow
) 
 

多倍長整数を2の冪乗で割った剰余.

<self>を2のpow乗で割った剰余をresultに格納する。

引数:
result  剰余を格納するstruct multiprecへのポインタ
self  元の数を表すstruct multiprecへのポインタ
pow  冪指数
覚え書き:
selfとresultは一致してもよい
事後条件:
0 <= |r| < 2**pow であり、rは<self>と同符号

shift.c の 217 行で定義されています。 

00218 {
00219   size_t n_digits = pow / DIGIT_BIT;
00220   ymp_reserve(result, n_digits>self->used ? self->used : n_digits);
00221   result->sign = self->sign;
00222   result->used = ymp_modabs_2exp(result->digits, self->digits, self->used, pow);
00223 }

void ymp_iroot (  mp_ref_t    result,
mp_cref_t    self,
size_t    n
) 
 

多倍長整数の冪乗根の整数部分.

result := floor( <self> ** (1/n) )

引数:
result  結果を格納するstruct multiprecへのポインタ
self  元の数を表すstruct multiprecへのポインタ
n  冪指数
事前条件:
nが偶数ならば、selfは非負であること。 そうでないときはymp_fatalが呼ばれる。
nは0でないこと. そうでないとき、結果は不定

root.c の 16 行で定義されています。 

00017 {
00018   /* Newton法による */
00019 
00020   size_t i;
00021   size_t ilog2, bit_len;
00022   struct multiprec x, x_prev; /* 近似途中の値を保持 */
00023   struct multiprec tmp;       /* 計算上の一時領域   */
00024   struct multiprec self_copy;
00025 
00026   if (!self->sign)
00027     { /* 非負ならば良い */
00028       result->sign = positive_sign;
00029     }
00030   else
00031     { /* そうでないとき */
00032       /* 偶数乗根はエラー */
00033       if ( (n & 0x01) == 0) ymp_fatal("負数の偶数乗根");
00034 
00035       /* 結果の符号が確定 */
00036       result->sign = self->sign;
00037 
00038       /* 以下、-<self> >= 0 の絶対値を算出すれば良い */
00039       memcpy(&self_copy, self, sizeof(struct multiprec));
00040       self_copy.sign = positive_sign;
00041       self = &self_copy;
00042     }
00043 
00044   /* bit長により、初期値を大まかに決定 */
00045   /* (初期値) >= (収束値) を保証して収束が遅くなるのを防止する */
00046   /* ilog2 := { 2**k > |<self>|なる最小のk } */
00047   ilog2 = ymp_ilog2(self); ++ilog2;
00048 
00049   bit_len = ilog2 / n;
00050   if (bit_len == 0)
00051     {
00052       if (ymp_is_zero(self)) ymp_assign_abs_digit(result, 0);
00053       else                   ymp_assign_abs_digit(result, 1);
00054       return;
00055     }
00056   if (ilog2 % n) ++bit_len;
00057 
00058   ymp_alloca_initialize(&x, self->used * n + 1);
00059   for (i=0; i<bit_len/DIGIT_BIT; ++i) x.digits[i] = 0;  
00060   x.digits[i] = 1u << (bit_len%DIGIT_BIT);
00061   x.used = ++i;
00062 
00063   /* 今、x は (2**k)**n > |<self>| なる最小の2**k */
00064 
00065 
00066   /* 作業領域確保 */
00067   ymp_alloca_initialize(&tmp, self->used * n + 1);
00068   ymp_alloca_initialize(&x_prev, self->used * n + 1);
00069 
00070   
00071   /* f(x) = x**n - |<self>| に対するNetwon法 */
00072   for (;;)
00073     {
00074     l_newton_iteration:
00075       ymp_assign(&x_prev, &x);
00076       
00077       /* x_{i+1} = ((n-1) * x_i**n + a) / (n * x_i**(n-1)) */
00078       ymp_pow(&tmp, &x_prev, n-1);  /* tmp = x_i ** (n-1)  */
00079 
00080       ymp_assign(&x, &tmp);         /* x = x_i ** n */
00081       ymp_mul(&x, &x, &x_prev);
00082       ymp_mul_digit(&x, &x, n-1);       /* x = (n-1) * x_i**n  */
00083       ymp_add(&x, &x, self);        /* (n-1) * x_i**n + a  */
00084       
00085       ymp_mul_digit(&tmp, &tmp, n); /* tmp = n*x_i**(n-1)  */
00086       
00087       ymp_div(&x, &x, &tmp);        /* x = x_{i+1} */
00088 
00089 
00090       if (x.used != x_prev.used) continue;  /* まだ誤差が大きい */
00091 
00092       for (i=1; i<x.used; ++i)
00093         {
00094           if (x.digits[i] != x_prev.digits[i]) /* まだ誤差が大きい */
00095             goto l_newton_iteration;           /* Newton法続行 */
00096         }
00097 
00098       /* かなり収束した。現在の誤差の絶対値が1以下なら、あとは微調整 */
00099       switch ((int)(x.digits[0] - x_prev.digits[0]))
00100         {
00101         case 0:
00102           ymp_assign_abs(result, &x);
00103           return;
00104 
00105         case 1:
00106           for (;;)
00107             {
00108               ymp_pow(&tmp, &x, n);
00109               if (ymp_compare_abs(&tmp, self) > 0) break;
00110               ymp_add_digit(&x, &x, 1);
00111             }
00112           ymp_sub_digit(&x, &x, 1);
00113           ymp_assign_abs(result, &x);
00114           return;
00115           
00116         case -1:
00117           for (;;)
00118             {
00119               ymp_pow(&tmp, &x, n);
00120               if (ymp_compare_abs(&tmp, self) <= 0) break;
00121               ymp_sub_digit(&x, &x, 1);
00122             }
00123           ymp_assign_abs(result, &x);
00124           return;
00125         }
00126     }
00127 }

YMPに対してTue Mar 16 19:23:52 2004に生成されました。 doxygen1.2.14 作者 Dimitri van Heesch, © 1997-2002