Ruby: bignum.c Source File

00001 /**********************************************************************
00002 
00003   bignum.c -
00004 
00005   $Author: akr $
00006   $Date: 2005/12/16 18:59:31 $
00007   created at: Fri Jun 10 00:48:55 JST 1994
00008 
00009   Copyright (C) 1993-2003 Yukihiro Matsumoto
00010 
00011 **********************************************************************/
00012 
00013 #include "ruby.h"
00014 
00015 #include <math.h>
00016 #include <ctype.h>
00017 #ifdef HAVE_IEEEFP_H
00018 #include <ieeefp.h>
00019 #endif
00020 
00021 VALUE rb_cBignum;
00022 
00023 #if defined __MINGW32__
00024 #define USHORT _USHORT
00025 #endif
00026 
00027 #define BDIGITS(x) ((BDIGIT*)RBIGNUM(x)->digits)
00028 #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
00029 #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
00030 #define DIGSPERLONG ((unsigned int)(SIZEOF_LONG/SIZEOF_BDIGITS))
00031 #if HAVE_LONG_LONG
00032 # define DIGSPERLL ((unsigned int)(SIZEOF_LONG_LONG/SIZEOF_BDIGITS))
00033 #endif
00034 #define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
00035 #define BIGDN(x) RSHIFT(x,BITSPERDIG)
00036 #define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
00037 #define BDIGMAX ((BDIGIT)-1)
00038 
00039 #define BIGZEROP(x) (RBIGNUM(x)->len == 0 || (RBIGNUM(x)->len == 1 && BDIGITS(x)[0] == 0))
00040 
00041 static VALUE
00042 bignew_1(klass, len, sign)
00043     VALUE klass;
00044     long len;
00045     int sign;
00046 {
00047     NEWOBJ(big, struct RBignum);
00048     OBJSETUP(big, klass, T_BIGNUM);
00049     big->sign = sign?1:0;
00050     big->len = len;
00051     big->digits = ALLOC_N(BDIGIT, len);
00052 
00053     return (VALUE)big;
00054 }
00055 
00056 #define bignew(len,sign) bignew_1(rb_cBignum,len,sign)
00057 
00058 VALUE
00059 rb_big_clone(x)
00060     VALUE x;
00061 {
00062     VALUE z = bignew_1(CLASS_OF(x), RBIGNUM(x)->len, RBIGNUM(x)->sign);
00063 
00064     MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT, RBIGNUM(x)->len);
00065     return z;
00066 }
00067 
00068 /* modify a bignum by 2's complement */
00069 static void
00070 get2comp(x)
00071     VALUE x;
00072 {
00073     long i = RBIGNUM(x)->len;
00074     BDIGIT *ds = BDIGITS(x);
00075     BDIGIT_DBL num;
00076 
00077     while (i--) ds[i] = ~ds[i];
00078     i = 0; num = 1;
00079     do {
00080         num += ds[i];
00081         ds[i++] = BIGLO(num);
00082         num = BIGDN(num);
00083     } while (i < RBIGNUM(x)->len);
00084     if (num != 0) {
00085         REALLOC_N(RBIGNUM(x)->digits, BDIGIT, ++RBIGNUM(x)->len);
00086         ds = BDIGITS(x);
00087         ds[RBIGNUM(x)->len-1] = RBIGNUM(x)->sign ? ~0 : 1;
00088     }
00089 }
00090 
00091 void
00092 rb_big_2comp(x)                 /* get 2's complement */
00093     VALUE x;
00094 {
00095     get2comp(x);
00096 }
00097 
00098 static VALUE
00099 bignorm(x)
00100     VALUE x;
00101 {
00102     if (!FIXNUM_P(x)) {
00103         long len = RBIGNUM(x)->len;
00104         BDIGIT *ds = BDIGITS(x);
00105 
00106         while (len-- && !ds[len]) ;
00107         RBIGNUM(x)->len = ++len;
00108 
00109         if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) {
00110             long num = 0;
00111             while (len--) {
00112                 num = BIGUP(num) + ds[len];
00113             }
00114             if (num >= 0) {
00115                 if (RBIGNUM(x)->sign) {
00116                     if (POSFIXABLE(num)) return LONG2FIX(num);
00117                 }
00118                 else if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(long)num);
00119             }
00120         }
00121     }
00122     return x;
00123 }
00124 
00125 VALUE
00126 rb_big_norm(x)
00127     VALUE x;
00128 {
00129     return bignorm(x);
00130 }
00131 
00132 VALUE
00133 rb_uint2big(n)
00134     unsigned long n;
00135 {
00136     BDIGIT_DBL num = n;
00137     long i = 0;
00138     BDIGIT *digits;
00139     VALUE big;
00140 
00141     big = bignew(DIGSPERLONG, 1);
00142     digits = BDIGITS(big);
00143     while (i < DIGSPERLONG) {
00144         digits[i++] = BIGLO(num);
00145         num = BIGDN(num);
00146     }
00147 
00148     i = DIGSPERLONG;
00149     while (--i && !digits[i]) ;
00150     RBIGNUM(big)->len = i+1;
00151     return big;
00152 }
00153 
00154 VALUE
00155 rb_int2big(n)
00156     long n;
00157 {
00158     long neg = 0;
00159     VALUE big;
00160 
00161     if (n < 0) {
00162         n = -n;
00163         neg = 1;
00164     }
00165     big = rb_uint2big(n);
00166     if (neg) {
00167         RBIGNUM(big)->sign = 0;
00168     }
00169     return big;
00170 }
00171 
00172 VALUE
00173 rb_uint2inum(n)
00174     unsigned long n;
00175 {
00176     if (POSFIXABLE(n)) return LONG2FIX(n);
00177     return rb_uint2big(n);
00178 }
00179 
00180 VALUE
00181 rb_int2inum(n)
00182     long n;
00183 {
00184     if (FIXABLE(n)) return LONG2FIX(n);
00185     return rb_int2big(n);
00186 }
00187 
00188 #ifdef HAVE_LONG_LONG
00189 
00190 void
00191 rb_quad_pack(buf, val)
00192     char *buf;
00193     VALUE val;
00194 {
00195     LONG_LONG q;
00196 
00197     val = rb_to_int(val);
00198     if (FIXNUM_P(val)) {
00199         q = FIX2LONG(val);
00200     }
00201     else {
00202         long len = RBIGNUM(val)->len;
00203         BDIGIT *ds;
00204 
00205         if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
00206             rb_raise(rb_eRangeError, "bignum too big to convert into `quad int'");
00207         ds = BDIGITS(val);
00208         q = 0;
00209         while (len--) {
00210             q = BIGUP(q);
00211             q += ds[len];
00212         }
00213         if (!RBIGNUM(val)->sign) q = -q;
00214     }
00215     memcpy(buf, (char*)&q, SIZEOF_LONG_LONG);
00216 }
00217 
00218 VALUE
00219 rb_quad_unpack(buf, sign)
00220     const char *buf;
00221     int sign;
00222 {
00223     unsigned LONG_LONG q;
00224     long neg = 0;
00225     long i;
00226     BDIGIT *digits;
00227     VALUE big;
00228 
00229     memcpy(&q, buf, SIZEOF_LONG_LONG);
00230     if (sign) {
00231         if (FIXABLE((LONG_LONG)q)) return LONG2FIX((LONG_LONG)q);
00232         if ((LONG_LONG)q < 0) {
00233             q = -(LONG_LONG)q;
00234             neg = 1;
00235         }
00236     }
00237     else {
00238         if (POSFIXABLE(q)) return LONG2FIX(q);
00239     }
00240 
00241     i = 0;
00242     big = bignew(DIGSPERLL, 1);
00243     digits = BDIGITS(big);
00244     while (i < DIGSPERLL) {
00245         digits[i++] = BIGLO(q);
00246         q = BIGDN(q);
00247     }
00248 
00249     i = DIGSPERLL;
00250     while (i-- && !digits[i]) ;
00251     RBIGNUM(big)->len = i+1;
00252 
00253     if (neg) {
00254         RBIGNUM(big)->sign = 0;
00255     }
00256     return bignorm(big);
00257 }
00258 
00259 #else
00260 
00261 #define QUAD_SIZE 8
00262 
00263 void
00264 rb_quad_pack(buf, val)
00265     char *buf;
00266     VALUE val;
00267 {
00268     long len;
00269 
00270     memset(buf, 0, QUAD_SIZE);
00271     val = rb_to_int(val);
00272     if (FIXNUM_P(val)) {
00273         val = rb_int2big(FIX2LONG(val));
00274     }
00275     len = RBIGNUM(val)->len * SIZEOF_BDIGITS;
00276     if (len > QUAD_SIZE) {
00277         rb_raise(rb_eRangeError, "bignum too big to convert into `quad int'");
00278     }
00279     memcpy(buf, (char*)BDIGITS(val), len);
00280     if (!RBIGNUM(val)->sign) {
00281         len = QUAD_SIZE;
00282         while (len--) {
00283             *buf = ~*buf;
00284             buf++;
00285         }
00286     }
00287 }
00288 
00289 #define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)
00290 
00291 VALUE
00292 rb_quad_unpack(buf, sign)
00293     const char *buf;
00294     int sign;
00295 {
00296     VALUE big = bignew(QUAD_SIZE/SIZEOF_BDIGITS, 1);
00297 
00298     memcpy((char*)BDIGITS(big), buf, QUAD_SIZE);
00299     if (sign && BNEG(buf)) {
00300         long len = QUAD_SIZE;
00301         char *tmp = (char*)BDIGITS(big);
00302 
00303         RBIGNUM(big)->sign = 0;
00304         while (len--) {
00305             *tmp = ~*tmp;
00306             tmp++;
00307         }
00308     }
00309 
00310     return bignorm(big);
00311 }
00312 
00313 #endif
00314 
00315 VALUE
00316 rb_cstr_to_inum(str, base, badcheck)
00317     const char *str;
00318     int base;
00319     int badcheck;
00320 {
00321     const char *s = str;
00322     char *end;
00323     char sign = 1, nondigit = 0;
00324     int c;
00325     BDIGIT_DBL num;
00326     long len, blen = 1;
00327     long i;
00328     VALUE z;
00329     BDIGIT *zds;
00330 
00331     if (!str) {
00332         if (badcheck) goto bad;
00333         return INT2FIX(0);
00334     }
00335     if (badcheck) {
00336         while (ISSPACE(*str)) str++;
00337     }
00338     else {
00339         while (ISSPACE(*str) || *str == '_') str++;
00340     }
00341 
00342     if (str[0] == '+') {
00343         str++;
00344     }
00345     else if (str[0] == '-') {
00346         str++;
00347         sign = 0;
00348     }
00349     if (str[0] == '+' || str[0] == '-') {
00350         if (badcheck) goto bad;
00351         return INT2FIX(0);
00352     }
00353     if (base <= 0) {
00354         if (str[0] == '0') {
00355             switch (str[1]) {
00356               case 'x': case 'X':
00357                 base = 16;
00358                 break;
00359               case 'b': case 'B':
00360                 base = 2;
00361                 break;
00362               case 'o': case 'O':
00363                 base = 8;
00364                 break;
00365               case 'd': case 'D':
00366                 base = 10;
00367                 break;
00368               default:
00369                 base = 8;
00370             }
00371         }
00372         else if (base < -1) {
00373             base = -base;
00374         }
00375         else {
00376             base = 10;
00377         }
00378     }
00379     switch (base) {
00380       case 2:
00381         len = 1;
00382         if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) {
00383             str += 2;
00384         }
00385         break;
00386       case 3:
00387         len = 2;
00388         break;
00389       case 8:
00390         if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) {
00391             str += 2;
00392         }
00393       case 4: case 5: case 6: case 7:
00394         len = 3;
00395         break;
00396       case 10:
00397         if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) {
00398             str += 2;
00399         }
00400       case 9: case 11: case 12: case 13: case 14: case 15:
00401         len = 4;
00402         break;
00403       case 16:
00404         len = 4;
00405         if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) {
00406             str += 2;
00407         }
00408         break;
00409       default:
00410         if (base < 2 || 36 < base) {
00411             rb_raise(rb_eArgError, "illegal radix %d", base);
00412         }
00413         if (base <= 32) {
00414             len = 5;
00415         }
00416         else {
00417             len = 6;
00418         }
00419         break;
00420     }
00421     if (*str == '0') {          /* squeeze preceeding 0s */
00422         while (*++str == '0');
00423         --str;
00424     }
00425     len *= strlen(str)*sizeof(char);
00426 
00427     if (len <= (sizeof(VALUE)*CHAR_BIT)) {
00428         unsigned long val = strtoul((char*)str, &end, base);
00429 
00430         if (*end == '_') goto bigparse;
00431         if (badcheck) {
00432             if (end == str) goto bad; /* no number */
00433             while (*end && ISSPACE(*end)) end++;
00434             if (*end) goto bad;       /* trailing garbage */
00435         }
00436 
00437         if (POSFIXABLE(val)) {
00438             if (sign) return LONG2FIX(val);
00439             else {
00440                 long result = -(long)val;
00441                 return LONG2FIX(result);
00442             }
00443         }
00444         else {
00445             VALUE big = rb_uint2big(val);
00446             RBIGNUM(big)->sign = sign;
00447             return bignorm(big);
00448         }
00449     }
00450   bigparse:
00451     len = (len/BITSPERDIG)+1;
00452     if (badcheck && *str == '_') goto bad;
00453 
00454     z = bignew(len, sign);
00455     zds = BDIGITS(z);
00456     for (i=len;i--;) zds[i]=0;
00457     while (c = *str++) {
00458         if (c == '_') {
00459             if (badcheck) {
00460                 if (nondigit) goto bad;
00461                 nondigit = c;
00462             }
00463             continue;
00464         }
00465         else if (!ISASCII(c)) {
00466             break;
00467         }
00468         else if (isdigit(c)) {
00469             c -= '0';
00470         }
00471         else if (islower(c)) {
00472             c -= 'a' - 10;
00473         }
00474         else if (isupper(c)) {
00475             c -= 'A' - 10;
00476         }
00477         else {
00478             break;
00479         }
00480         if (c >= base) break;
00481         nondigit = 0;
00482         i = 0;
00483         num = c;
00484         for (;;) {
00485             while (i<blen) {
00486                 num += (BDIGIT_DBL)zds[i]*base;
00487                 zds[i++] = BIGLO(num);
00488                 num = BIGDN(num);
00489             }
00490             if (num) {
00491                 blen++;
00492                 continue;
00493             }
00494             break;
00495         }
00496     }
00497     if (badcheck) {
00498         str--;
00499         if (s+1 < str && str[-1] == '_') goto bad;
00500         while (*str && ISSPACE(*str)) str++;
00501         if (*str) {
00502           bad:
00503             rb_invalid_str(s, "Integer");
00504         }
00505     }
00506 
00507     return bignorm(z);
00508 }
00509 
00510 VALUE
00511 rb_str_to_inum(str, base, badcheck)
00512     VALUE str;
00513     int base;
00514     int badcheck;
00515 {
00516     char *s;
00517     long len;
00518 
00519     StringValue(str);
00520     if (badcheck) {
00521         s = StringValueCStr(str);
00522     }
00523     else {
00524         s = RSTRING(str)->ptr;
00525     }
00526     if (s) {
00527         len = RSTRING(str)->len;
00528         if (s[len]) {           /* no sentinel somehow */
00529             char *p = ALLOCA_N(char, len+1);
00530 
00531             MEMCPY(p, s, char, len);
00532             p[len] = '\0';
00533             s = p;
00534         }
00535     }
00536     return rb_cstr_to_inum(s, base, badcheck); 
00537 }
00538 
00539 #if HAVE_LONG_LONG
00540 
00541 VALUE
00542 rb_ull2big(n)
00543     unsigned LONG_LONG n;
00544 {
00545     BDIGIT_DBL num = n;
00546     long i = 0;
00547     BDIGIT *digits;
00548     VALUE big;
00549 
00550     big = bignew(DIGSPERLL, 1);
00551     digits = BDIGITS(big);
00552     while (i < DIGSPERLL) {
00553         digits[i++] = BIGLO(num);
00554         num = BIGDN(num);
00555     }
00556 
00557     i = DIGSPERLL;
00558     while (i-- && !digits[i]) ;
00559     RBIGNUM(big)->len = i+1;
00560     return big;
00561 }
00562 
00563 VALUE
00564 rb_ll2big(n)
00565     LONG_LONG n;
00566 {
00567     long neg = 0;
00568     VALUE big;
00569 
00570     if (n < 0) {
00571         n = -n;
00572         neg = 1;
00573     }
00574     big = rb_ull2big(n);
00575     if (neg) {
00576         RBIGNUM(big)->sign = 0;
00577     }
00578     return big;
00579 }
00580 
00581 VALUE
00582 rb_ull2inum(n)
00583     unsigned LONG_LONG n;
00584 {
00585     if (POSFIXABLE(n)) return LONG2FIX(n);
00586     return rb_ull2big(n);
00587 }
00588 
00589 VALUE
00590 rb_ll2inum(n)
00591     LONG_LONG n;
00592 {
00593     if (FIXABLE(n)) return LONG2FIX(n);
00594     return rb_ll2big(n);
00595 }
00596 
00597 #endif  /* HAVE_LONG_LONG */
00598  
00599 VALUE
00600 rb_cstr2inum(str, base)
00601     const char *str;
00602     int base;
00603 {
00604     return rb_cstr_to_inum(str, base, base==0);
00605 }
00606 
00607 VALUE
00608 rb_str2inum(str, base)
00609     VALUE str;
00610     int base;
00611 {
00612     return rb_str_to_inum(str, base, base==0);
00613 }
00614 
00615 const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";
00616 VALUE
00617 rb_big2str(x, base)
00618     VALUE x;
00619     int base;
00620 {
00621     volatile VALUE t;
00622     BDIGIT *ds;
00623     long i, j, hbase;
00624     VALUE ss;
00625     char *s, c;
00626 
00627     if (FIXNUM_P(x)) {
00628         return rb_fix2str(x, base);
00629     }
00630     i = RBIGNUM(x)->len;
00631     if (BIGZEROP(x)) {
00632         return rb_str_new2("0");
00633     }
00634     j = SIZEOF_BDIGITS*CHAR_BIT*i;
00635     switch (base) {
00636       case 2: break;
00637       case 3:
00638         j = j * 647L / 1024;
00639         break;
00640       case 4: case 5: case 6: case 7:
00641         j /= 2;
00642         break;
00643       case 8: case 9:
00644         j /= 3;
00645         break;
00646       case 10: case 11: case 12: case 13: case 14: case 15:
00647         j = j * 241L / 800;
00648         break;
00649       case 16: case 17: case 18: case 19: case 20: case 21:
00650       case 22: case 23: case 24: case 25: case 26: case 27:
00651       case 28: case 29: case 30: case 31:
00652         j /= 4;
00653         break;
00654       case 32: case 33: case 34: case 35: case 36:
00655         j /= 5;
00656         break;
00657       default:
00658         rb_raise(rb_eArgError, "illegal radix %d", base);
00659         break;
00660     }
00661     j += 2;
00662 
00663     hbase = base * base;
00664 #if SIZEOF_BDIGITS > 2
00665     hbase *= hbase;
00666 #endif
00667 
00668     t = rb_big_clone(x);
00669     ds = BDIGITS(t);
00670     ss = rb_str_new(0, j);
00671     s = RSTRING(ss)->ptr;
00672 
00673     s[0] = RBIGNUM(x)->sign ? '+' : '-';
00674     while (i && j) {
00675         long k = i;
00676         BDIGIT_DBL num = 0;
00677 
00678         while (k--) {
00679             num = BIGUP(num) + ds[k];
00680             ds[k] = (BDIGIT)(num / hbase);
00681             num %= hbase;
00682         }
00683         if (ds[i-1] == 0) i--;
00684         k = SIZEOF_BDIGITS;
00685         while (k--) {
00686             c = (char)(num % base);
00687             s[--j] = ruby_digitmap[(int)c];
00688             num /= base;
00689             if (i == 0 && num == 0) break;
00690         }
00691     }
00692     while (s[j] == '0') j++;
00693     RSTRING(ss)->len -= RBIGNUM(x)->sign?j:j-1;
00694     memmove(RBIGNUM(x)->sign?s:s+1, s+j, RSTRING(ss)->len);
00695     s[RSTRING(ss)->len] = '\0';
00696 
00697     return ss;
00698 }
00699 
00700 /*
00701  *  call-seq:
00702  *     big.to_s(base=10)   =>  string
00703  *  
00704  *  Returns a string containing the representation of <i>big</i> radix
00705  *  <i>base</i> (2 through 36).
00706  *     
00707  *     12345654321.to_s         #=> "12345654321"
00708  *     12345654321.to_s(2)      #=> "1011011111110110111011110000110001"
00709  *     12345654321.to_s(8)      #=> "133766736061"
00710  *     12345654321.to_s(16)     #=> "2dfdbbc31"
00711  *     78546939656932.to_s(36)  #=> "rubyrules"
00712  */
00713 
00714 static VALUE
00715 rb_big_to_s(argc, argv, x)
00716     int argc;
00717     VALUE *argv;
00718     VALUE x;
00719 {
00720     VALUE b;
00721     int base;
00722 
00723     rb_scan_args(argc, argv, "01", &b);
00724     if (argc == 0) base = 10;
00725     else base = NUM2INT(b);
00726     return rb_big2str(x, base);
00727 }
00728 
00729 static unsigned long
00730 big2ulong(x, type)
00731     VALUE x;
00732     char *type;
00733 {
00734     long len = RBIGNUM(x)->len;
00735     BDIGIT_DBL num;
00736     BDIGIT *ds;
00737 
00738     if (len > SIZEOF_LONG/SIZEOF_BDIGITS)
00739         rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
00740     ds = BDIGITS(x);
00741     num = 0;
00742     while (len--) {
00743         num = BIGUP(num);
00744         num += ds[len];
00745     }
00746     return num;
00747 }
00748 
00749 unsigned long
00750 rb_big2ulong_pack(x)   
00751     VALUE x;  
00752 {   
00753     unsigned long num = big2ulong(x, "unsigned long");
00754     if (!RBIGNUM(x)->sign) {
00755         return -num;
00756     }
00757     return num;
00758 }  
00759 
00760 unsigned long
00761 rb_big2ulong(x)
00762     VALUE x;
00763 {
00764     unsigned long num = big2ulong(x, "unsigned long");
00765 
00766     if (!RBIGNUM(x)->sign) {
00767         if ((long)num < 0) {
00768             rb_raise(rb_eRangeError, "bignum out of range of unsigned long");
00769         }
00770         return -num;
00771     }
00772     return num;
00773 }
00774 
00775 long
00776 rb_big2long(x)
00777     VALUE x;
00778 {
00779     unsigned long num = big2ulong(x, "long");
00780 
00781     if ((long)num < 0 && (RBIGNUM(x)->sign || (long)num != LONG_MIN)) {
00782         rb_raise(rb_eRangeError, "bignum too big to convert into `long'");
00783     }
00784     if (!RBIGNUM(x)->sign) return -(long)num;
00785     return num;
00786 }
00787 
00788 #if HAVE_LONG_LONG
00789 
00790 static unsigned LONG_LONG
00791 big2ull(x, type)
00792     VALUE x;
00793     char *type;
00794 {
00795     long len = RBIGNUM(x)->len;
00796     BDIGIT_DBL num;
00797     BDIGIT *ds;
00798 
00799     if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
00800         rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
00801     ds = BDIGITS(x);
00802     num = 0;
00803     while (len--) {
00804         num = BIGUP(num);
00805         num += ds[len];
00806     }
00807     return num;
00808 }
00809 
00810 unsigned LONG_LONG
00811 rb_big2ull(x)
00812     VALUE x;
00813 {
00814     unsigned LONG_LONG num = big2ull(x, "unsigned long long");
00815 
00816     if (!RBIGNUM(x)->sign) return -num;
00817     return num;
00818 }
00819 
00820 LONG_LONG
00821 rb_big2ll(x)
00822     VALUE x;
00823 {
00824     unsigned LONG_LONG num = big2ull(x, "long long");
00825 
00826     if ((LONG_LONG)num < 0 && (RBIGNUM(x)->sign
00827                                || (LONG_LONG)num != LLONG_MIN)) {
00828         rb_raise(rb_eRangeError, "bignum too big to convert into `long long'");
00829     }
00830     if (!RBIGNUM(x)->sign) return -(LONG_LONG)num;
00831     return num;
00832 }
00833 
00834 #endif  /* HAVE_LONG_LONG */
00835 
00836 static VALUE
00837 dbl2big(d)
00838     double d;
00839 {
00840     long i = 0;
00841     BDIGIT c;
00842     BDIGIT *digits;
00843     VALUE z;
00844     double u = (d < 0)?-d:d;
00845 
00846     if (isinf(d)) {
00847         rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity");
00848     }
00849     if (isnan(d)) {
00850         rb_raise(rb_eFloatDomainError, "NaN");
00851     }
00852 
00853     while (!POSFIXABLE(u) || 0 != (long)u) {
00854         u /= (double)(BIGRAD);
00855         i++;
00856     }
00857     z = bignew(i, d>=0);
00858     digits = BDIGITS(z);
00859     while (i--) {
00860         u *= BIGRAD;
00861         c = (BDIGIT)u;
00862         u -= c;
00863         digits[i] = c;
00864     }
00865 
00866     return z;
00867 }
00868 
00869 VALUE
00870 rb_dbl2big(d)
00871     double d;
00872 {
00873     return bignorm(dbl2big(d));
00874 }
00875 
00876 double
00877 rb_big2dbl(x)
00878     VALUE x;
00879 {
00880     double d = 0.0;
00881     long i = RBIGNUM(x)->len;
00882     BDIGIT *ds = BDIGITS(x);
00883 
00884     while (i--) {
00885         d = ds[i] + BIGRAD*d;
00886     }
00887     if (isinf(d)) {
00888         rb_warn("Bignum out of Float range");
00889         d = HUGE_VAL;
00890     }
00891     if (!RBIGNUM(x)->sign) d = -d;
00892     return d;
00893 }
00894 
00895 /*
00896  *  call-seq:
00897  *     big.to_f -> float
00898  *  
00899  *  Converts <i>big</i> to a <code>Float</code>. If <i>big</i> doesn't
00900  *  fit in a <code>Float</code>, the result is infinity.
00901  *     
00902  */
00903 
00904 static VALUE
00905 rb_big_to_f(x)
00906     VALUE x;
00907 {
00908     return rb_float_new(rb_big2dbl(x));
00909 }
00910 
00911 /*
00912  *  call-seq:
00913  *     big <=> numeric   => -1, 0, +1
00914  *  
00915  *  Comparison---Returns -1, 0, or +1 depending on whether <i>big</i> is
00916  *  less than, equal to, or greater than <i>numeric</i>. This is the
00917  *  basis for the tests in <code>Comparable</code>.
00918  *     
00919  */
00920 
00921 static VALUE
00922 rb_big_cmp(x, y)
00923     VALUE x, y;
00924 {
00925     long xlen = RBIGNUM(x)->len;
00926 
00927     switch (TYPE(y)) {
00928       case T_FIXNUM:
00929         y = rb_int2big(FIX2LONG(y));
00930         break;
00931 
00932       case T_BIGNUM:
00933         break;
00934 
00935       case T_FLOAT:
00936         return rb_dbl_cmp(rb_big2dbl(x), RFLOAT(y)->value);
00937 
00938       default:
00939         return rb_num_coerce_cmp(x, y);
00940     }
00941 
00942     if (RBIGNUM(x)->sign > RBIGNUM(y)->sign) return INT2FIX(1);
00943     if (RBIGNUM(x)->sign < RBIGNUM(y)->sign) return INT2FIX(-1);
00944     if (xlen < RBIGNUM(y)->len)
00945         return (RBIGNUM(x)->sign) ? INT2FIX(-1) : INT2FIX(1);
00946     if (xlen > RBIGNUM(y)->len)
00947         return (RBIGNUM(x)->sign) ? INT2FIX(1) : INT2FIX(-1);
00948 
00949     while(xlen-- && (BDIGITS(x)[xlen]==BDIGITS(y)[xlen]));
00950     if (-1 == xlen) return INT2FIX(0);
00951     return (BDIGITS(x)[xlen] > BDIGITS(y)[xlen]) ?
00952         (RBIGNUM(x)->sign ? INT2FIX(1) : INT2FIX(-1)) :
00953             (RBIGNUM(x)->sign ? INT2FIX(-1) : INT2FIX(1));
00954 }
00955 
00956 /*
00957  *  call-seq:
00958  *     big == obj  => true or false
00959  *  
00960  *  Returns <code>true</code> only if <i>obj</i> has the same value
00961  *  as <i>big</i>. Contrast this with <code>Bignum#eql?</code>, which
00962  *  requires <i>obj</i> to be a <code>Bignum</code>.
00963  *     
00964  *     68719476736 == 68719476736.0   #=> true
00965  */
00966 
00967 static VALUE
00968 rb_big_eq(x, y)
00969     VALUE x, y;
00970 {
00971     switch (TYPE(y)) {
00972       case T_FIXNUM:
00973         y = rb_int2big(FIX2LONG(y));
00974         break;
00975       case T_BIGNUM:
00976         break;
00977       case T_FLOAT:
00978         {
00979             volatile double a, b;
00980 
00981             a = RFLOAT(y)->value;
00982             if (isnan(a)) return Qfalse;
00983             b = rb_big2dbl(x);
00984             return (a == b)?Qtrue:Qfalse;
00985         }
00986       default:
00987         return rb_equal(y, x);
00988     }
00989     if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse;
00990     if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse;
00991     if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse;
00992     return Qtrue;
00993 }
00994 
00995 /*
00996  *  call-seq:
00997  *     big.eql?(obj)   => true or false
00998  *  
00999  *  Returns <code>true</code> only if <i>obj</i> is a
01000  *  <code>Bignum</code> with the same value as <i>big</i>. Contrast this
01001  *  with <code>Bignum#==</code>, which performs type conversions.
01002  *     
01003  *     68719476736.eql?(68719476736.0)   #=> false
01004  */
01005 
01006 static VALUE
01007 rb_big_eql(x, y)
01008     VALUE x, y;
01009 {
01010     if (TYPE(y) != T_BIGNUM) return Qfalse;
01011     if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse;
01012     if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse;
01013     if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse;
01014     return Qtrue;
01015 }
01016 
01017 /*
01018  * call-seq:
01019  *    -big   =>  other_big
01020  *
01021  * Unary minus (returns a new Bignum whose value is 0-big)
01022  */
01023 
01024 static VALUE
01025 rb_big_uminus(x)
01026     VALUE x;
01027 {
01028     VALUE z = rb_big_clone(x);
01029 
01030     RBIGNUM(z)->sign = !RBIGNUM(x)->sign;
01031 
01032     return bignorm(z);
01033 }
01034 
01035 /*
01036  * call-seq:
01037  *     ~big  =>  integer
01038  *
01039  * Inverts the bits in big. As Bignums are conceptually infinite
01040  * length, the result acts as if it had an infinite number of one
01041  * bits to the left. In hex representations, this is displayed
01042  * as two periods to the left of the digits.
01043  *  
01044  *   sprintf("%X", ~0x1122334455)    #=> "..FEEDDCCBBAA"
01045  */
01046 
01047 static VALUE
01048 rb_big_neg(x)
01049     VALUE x;
01050 {
01051     VALUE z = rb_big_clone(x);
01052     long i;
01053     BDIGIT *ds;
01054 
01055     if (!RBIGNUM(x)->sign) get2comp(z);
01056     ds = BDIGITS(z);
01057     i = RBIGNUM(x)->len;
01058     while (i--) ds[i] = ~ds[i];
01059     RBIGNUM(z)->sign = !RBIGNUM(z)->sign;
01060     if (RBIGNUM(x)->sign) get2comp(z);
01061 
01062     return bignorm(z);
01063 }
01064 
01065 static VALUE
01066 bigsub(x, y)
01067     VALUE x, y;
01068 {
01069     VALUE z = 0;
01070     BDIGIT *zds;
01071     BDIGIT_DBL_SIGNED num;
01072     long i = RBIGNUM(x)->len;
01073     
01074     /* if x is larger than y, swap */
01075     if (RBIGNUM(x)->len < RBIGNUM(y)->len) {
01076         z = x; x = y; y = z;    /* swap x y */
01077     }
01078     else if (RBIGNUM(x)->len == RBIGNUM(y)->len) {
01079         while (i > 0) {
01080             i--;
01081             if (BDIGITS(x)[i] > BDIGITS(y)[i]) {
01082                 break;
01083             }
01084             if (BDIGITS(x)[i] < BDIGITS(y)[i]) {
01085                 z = x; x = y; y = z;    /* swap x y */
01086                 break;
01087             }
01088         }
01089     }
01090 
01091     z = bignew(RBIGNUM(x)->len, z==0);
01092     zds = BDIGITS(z);
01093 
01094     for (i = 0, num = 0; i < RBIGNUM(y)->len; i++) { 
01095         num += (BDIGIT_DBL_SIGNED)BDIGITS(x)[i] - BDIGITS(y)[i];
01096         zds[i] = BIGLO(num);
01097         num = BIGDN(num);
01098     } 
01099     while (num && i < RBIGNUM(x)->len) {
01100         num += BDIGITS(x)[i];
01101         zds[i++] = BIGLO(num);
01102         num = BIGDN(num);
01103     }
01104     while (i < RBIGNUM(x)->len) {
01105         zds[i] = BDIGITS(x)[i];
01106         i++;
01107     }
01108     
01109     return z;
01110 }
01111 
01112 static VALUE
01113 bigadd(x, y, sign)
01114     VALUE x, y;
01115     int sign;
01116 {
01117     VALUE z;
01118     BDIGIT_DBL num;
01119     long i, len;
01120 
01121     sign = (sign == RBIGNUM(y)->sign);
01122     if (RBIGNUM(x)->sign != sign) {
01123         if (sign) return bigsub(y, x);
01124         return bigsub(x, y);
01125     }
01126 
01127     if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
01128         len = RBIGNUM(x)->len + 1;
01129         z = x; x = y; y = z;
01130     }
01131     else {
01132         len = RBIGNUM(y)->len + 1;
01133     }
01134     z = bignew(len, sign);
01135 
01136     len = RBIGNUM(x)->len;
01137     for (i = 0, num = 0; i < len; i++) {
01138         num += (BDIGIT_DBL)BDIGITS(x)[i] + BDIGITS(y)[i];
01139         BDIGITS(z)[i] = BIGLO(num);
01140         num = BIGDN(num);
01141     }
01142     len = RBIGNUM(y)->len;
01143     while (num && i < len) {
01144         num += BDIGITS(y)[i];
01145         BDIGITS(z)[i++] = BIGLO(num);
01146         num = BIGDN(num);
01147     }
01148     while (i < len) {
01149         BDIGITS(z)[i] = BDIGITS(y)[i];
01150         i++;
01151     }
01152     BDIGITS(z)[i] = (BDIGIT)num;
01153 
01154     return z;
01155 }
01156 
01157 /*
01158  *  call-seq:
01159  *     big + other  => Numeric
01160  *
01161  *  Adds big and other, returning the result.
01162  */
01163 
01164 VALUE
01165 rb_big_plus(x, y)
01166     VALUE x, y;
01167 {
01168     switch (TYPE(y)) {
01169       case T_FIXNUM:
01170         y = rb_int2big(FIX2LONG(y));
01171         /* fall through */
01172       case T_BIGNUM:
01173         return bignorm(bigadd(x, y, 1));
01174 
01175       case T_FLOAT:
01176         return rb_float_new(rb_big2dbl(x) + RFLOAT(y)->value);
01177 
01178       default:
01179         return rb_num_coerce_bin(x, y);
01180     }
01181 }
01182 
01183 /*
01184  *  call-seq:
01185  *     big - other  => Numeric
01186  *
01187  *  Subtracts other from big, returning the result.
01188  */
01189 
01190 VALUE
01191 rb_big_minus(x, y)
01192     VALUE x, y;
01193 {
01194     switch (TYPE(y)) {
01195       case T_FIXNUM:
01196         y = rb_int2big(FIX2LONG(y));
01197         /* fall through */
01198       case T_BIGNUM:
01199         return bignorm(bigadd(x, y, 0));
01200 
01201       case T_FLOAT:
01202         return rb_float_new(rb_big2dbl(x) - RFLOAT(y)->value);
01203 
01204       default:
01205         return rb_num_coerce_bin(x, y);
01206     }
01207 }
01208 
01209 /*
01210  *  call-seq:
01211  *     big * other  => Numeric
01212  *
01213  *  Multiplies big and other, returning the result.
01214  */
01215 
01216 VALUE
01217 rb_big_mul(x, y)
01218     VALUE x, y;
01219 {
01220     long i, j;
01221     BDIGIT_DBL n = 0;
01222     VALUE z;
01223     BDIGIT *zds;
01224 
01225     if (FIXNUM_P(x)) x = rb_int2big(FIX2LONG(x));
01226     switch (TYPE(y)) {
01227       case T_FIXNUM:
01228         y = rb_int2big(FIX2LONG(y));
01229         break;
01230 
01231       case T_BIGNUM:
01232         break;
01233 
01234       case T_FLOAT:
01235         return rb_float_new(rb_big2dbl(x) * RFLOAT(y)->value);
01236 
01237       default:
01238         return rb_num_coerce_bin(x, y);
01239     }
01240 
01241     j = RBIGNUM(x)->len + RBIGNUM(y)->len + 1;
01242     z = bignew(j, RBIGNUM(x)->sign==RBIGNUM(y)->sign);
01243     zds = BDIGITS(z);
01244     while (j--) zds[j] = 0;
01245     for (i = 0; i < RBIGNUM(x)->len; i++) {
01246         BDIGIT_DBL dd = BDIGITS(x)[i]; 
01247         if (dd == 0) continue;
01248         n = 0;
01249         for (j = 0; j < RBIGNUM(y)->len; j++) {
01250             BDIGIT_DBL ee = n + (BDIGIT_DBL)dd * BDIGITS(y)[j];
01251             n = zds[i + j] + ee;
01252             if (ee) zds[i + j] = BIGLO(n);
01253             n = BIGDN(n);
01254         }
01255         if (n) {
01256             zds[i + j] = n;
01257         }
01258     }
01259 
01260     return bignorm(z);
01261 }
01262 
01263 static void
01264 bigdivrem(x, y, divp, modp)
01265     VALUE x, y;
01266     VALUE *divp, *modp;
01267 {
01268     long nx = RBIGNUM(x)->len, ny = RBIGNUM(y)->len;
01269     long i, j;
01270     VALUE yy, z;
01271     BDIGIT *xds, *yds, *zds, *tds;
01272     BDIGIT_DBL t2;
01273     BDIGIT_DBL_SIGNED num;
01274     BDIGIT dd, q;
01275 
01276     if (BIGZEROP(y)) rb_num_zerodiv();
01277     yds = BDIGITS(y);
01278     if (nx < ny || (nx == ny && BDIGITS(x)[nx - 1] < BDIGITS(y)[ny - 1])) {
01279         if (divp) *divp = rb_int2big(0);
01280         if (modp) *modp = x;
01281         return;
01282     }
01283     xds = BDIGITS(x);
01284     if (ny == 1) {
01285         dd = yds[0];
01286         z = rb_big_clone(x);
01287         zds = BDIGITS(z);
01288         t2 = 0; i = nx;
01289         while (i--) {
01290             t2 = BIGUP(t2) + zds[i];
01291             zds[i] = (BDIGIT)(t2 / dd);
01292             t2 %= dd;
01293         }
01294         RBIGNUM(z)->sign = RBIGNUM(x)->sign==RBIGNUM(y)->sign;
01295         if (modp) {
01296             *modp = rb_uint2big((unsigned long)t2);
01297             RBIGNUM(*modp)->sign = RBIGNUM(x)->sign;
01298         }
01299         if (divp) *divp = z;
01300         return;
01301     }
01302     z = bignew(nx==ny?nx+2:nx+1, RBIGNUM(x)->sign==RBIGNUM(y)->sign);
01303     zds = BDIGITS(z);
01304     if (nx==ny) zds[nx+1] = 0;
01305     while (!yds[ny-1]) ny--;
01306 
01307     dd = 0;
01308     q = yds[ny-1];
01309     while ((q & (1<<(BITSPERDIG-1))) == 0) {
01310         q <<= 1;
01311         dd++;
01312     }
01313     if (dd) {
01314         yy = rb_big_clone(y);
01315         tds = BDIGITS(yy);
01316         j = 0;
01317         t2 = 0;
01318         while (j<ny) {
01319             t2 += (BDIGIT_DBL)yds[j]<<dd;
01320             tds[j++] = BIGLO(t2);
01321             t2 = BIGDN(t2);
01322         }
01323         yds = tds;
01324         j = 0;
01325         t2 = 0;
01326         while (j<nx) {
01327             t2 += (BDIGIT_DBL)xds[j]<<dd;
01328             zds[j++] = BIGLO(t2);
01329             t2 = BIGDN(t2);
01330         }
01331         zds[j] = (BDIGIT)t2;
01332     }
01333     else {
01334         zds[nx] = 0;
01335         j = nx;
01336         while (j--) zds[j] = xds[j];
01337     }
01338 
01339     j = nx==ny?nx+1:nx;
01340     do {
01341         if (zds[j] ==  yds[ny-1]) q = BIGRAD-1;
01342         else q = (BDIGIT)((BIGUP(zds[j]) + zds[j-1])/yds[ny-1]);
01343         if (q) {
01344             i = 0; num = 0; t2 = 0;
01345             do {                        /* multiply and subtract */
01346                 BDIGIT_DBL ee;
01347                 t2 += (BDIGIT_DBL)yds[i] * q;
01348                 ee = num - BIGLO(t2);
01349                 num = (BDIGIT_DBL)zds[j - ny + i] + ee;
01350                 if (ee) zds[j - ny + i] = BIGLO(num);
01351                 num = BIGDN(num);
01352                 t2 = BIGDN(t2);
01353             } while (++i < ny);
01354             num += zds[j - ny + i] - t2;/* borrow from high digit; don't update */
01355             while (num) {               /* "add back" required */
01356                 i = 0; num = 0; q--;
01357                 do {
01358                     BDIGIT_DBL ee = num + yds[i];
01359                     num = (BDIGIT_DBL)zds[j - ny + i] + ee;
01360                     if (ee) zds[j - ny + i] = BIGLO(num);
01361                     num = BIGDN(num);
01362                 } while (++i < ny);
01363                 num--;
01364             }
01365         }
01366         zds[j] = q;
01367     } while (--j >= ny);
01368     if (divp) {                 /* move quotient down in z */
01369         *divp = rb_big_clone(z);
01370         zds = BDIGITS(*divp);
01371         j = (nx==ny ? nx+2 : nx+1) - ny;
01372         for (i = 0;i < j;i++) zds[i] = zds[i+ny];
01373         RBIGNUM(*divp)->len = i;
01374     }
01375     if (modp) {                 /* normalize remainder */
01376         *modp = rb_big_clone(z);
01377         zds = BDIGITS(*modp);
01378         while (--ny && !zds[ny]); ++ny;
01379         if (dd) {
01380             t2 = 0; i = ny;
01381             while(i--) {
01382                 t2 = (t2 | zds[i]) >> dd;
01383                 q = zds[i];
01384                 zds[i] = BIGLO(t2);
01385                 t2 = BIGUP(q);
01386             }
01387         }
01388         RBIGNUM(*modp)->len = ny;
01389         RBIGNUM(*modp)->sign = RBIGNUM(x)->sign;
01390     }
01391 }
01392 
01393 static void
01394 bigdivmod(x, y, divp, modp)
01395     VALUE x, y;
01396     VALUE *divp, *modp;
01397 {
01398     VALUE mod;
01399 
01400     bigdivrem(x, y, divp, &mod);
01401     if (RBIGNUM(x)->sign != RBIGNUM(y)->sign && !BIGZEROP(mod)) {
01402         if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
01403         if (modp) *modp = bigadd(mod, y, 1);
01404     }
01405     else {
01406         if (divp) *divp = *divp;
01407         if (modp) *modp = mod;
01408     }
01409 }
01410 
01411 /*
01412  *  call-seq:
01413  *     big / other     => Numeric
01414  *     big.div(other)  => Numeric
01415  *
01416  *  Divides big by other, returning the result.
01417  */
01418 
01419 static VALUE
01420 rb_big_div(x, y)
01421     VALUE x, y;
01422 {
01423     VALUE z;
01424 
01425     switch (TYPE(y)) {
01426       case T_FIXNUM:
01427         y = rb_int2big(FIX2LONG(y));
01428         break;
01429 
01430       case T_BIGNUM:
01431         break;
01432 
01433       case T_FLOAT:
01434         return rb_float_new(rb_big2dbl(x) / RFLOAT(y)->value);
01435 
01436       default:
01437         return rb_num_coerce_bin(x, y);
01438     }
01439     bigdivmod(x, y, &z, 0);
01440 
01441     return bignorm(z);
01442 }
01443 
01444 /*
01445  *  call-seq:
01446  *     big % other         => Numeric
01447  *     big.modulo(other)   => Numeric
01448  *
01449  *  Returns big modulo other. See Numeric.divmod for more
01450  *  information.
01451  */
01452 
01453 static VALUE
01454 rb_big_modulo(x, y)
01455     VALUE x, y;
01456 {
01457     VALUE z;
01458 
01459     switch (TYPE(y)) {
01460       case T_FIXNUM:
01461         y = rb_int2big(FIX2LONG(y));
01462         break;
01463 
01464       case T_BIGNUM:
01465         break;
01466 
01467       default:
01468         return rb_num_coerce_bin(x, y);
01469     }
01470     bigdivmod(x, y, 0, &z);
01471 
01472     return bignorm(z);
01473 }
01474 
01475 /*
01476  *  call-seq:
01477  *     big.remainder(numeric)    => number
01478  *  
01479  *  Returns the remainder after dividing <i>big</i> by <i>numeric</i>.
01480  *     
01481  *     -1234567890987654321.remainder(13731)      #=> -6966
01482  *     -1234567890987654321.remainder(13731.24)   #=> -9906.22531493148
01483  */
01484 static VALUE
01485 rb_big_remainder(x, y)
01486     VALUE x, y;
01487 {
01488     VALUE z;
01489 
01490     switch (TYPE(y)) {
01491       case T_FIXNUM:
01492         y = rb_int2big(FIX2LONG(y));
01493         break;
01494 
01495       case T_BIGNUM:
01496         break;
01497 
01498       default:
01499         return rb_num_coerce_bin(x, y);
01500     }
01501     bigdivrem(x, y, 0, &z);
01502 
01503     return bignorm(z);
01504 }
01505 
01506 /*
01507  *  call-seq:
01508  *     big.divmod(numeric)   => array
01509  *  
01510  *  See <code>Numeric#divmod</code>.
01511  *     
01512  */
01513 VALUE
01514 rb_big_divmod(x, y)
01515     VALUE x, y;
01516 {
01517     VALUE div, mod;
01518 
01519     switch (TYPE(y)) {
01520       case T_FIXNUM:
01521         y = rb_int2big(FIX2LONG(y));
01522         break;
01523 
01524       case T_BIGNUM:
01525         break;
01526 
01527       default:
01528         return rb_num_coerce_bin(x, y);
01529     }
01530     bigdivmod(x, y, &div, &mod);
01531 
01532     return rb_assoc_new(bignorm(div), bignorm(mod));
01533 }
01534 
01535 /*
01536  *  call-seq:
01537  *     big.quo(numeric) -> float
01538  *  
01539  *  Returns the floating point result of dividing <i>big</i> by
01540  *  <i>numeric</i>.
01541  *     
01542  *     -1234567890987654321.quo(13731)      #=> -89910996357705.5
01543  *     -1234567890987654321.quo(13731.24)   #=> -89909424858035.7
01544  *     
01545  */
01546 
01547 static VALUE
01548 rb_big_quo(x, y)
01549     VALUE x, y;
01550 {
01551     double dx = rb_big2dbl(x);
01552     double dy;
01553 
01554     switch (TYPE(y)) {
01555       case T_FIXNUM:
01556         dy = (double)FIX2LONG(y);
01557         break;
01558 
01559       case T_BIGNUM:
01560         dy = rb_big2dbl(y);
01561         break;
01562 
01563       case T_FLOAT:
01564         dy = RFLOAT(y)->value;
01565         break;
01566 
01567       default:
01568         return rb_num_coerce_bin(x, y);
01569     }
01570     return rb_float_new(dx / dy);
01571 }
01572 
01573 /*
01574  *  call-seq:
01575  *     big ** exponent   #=> numeric
01576  *
01577  *  Raises _big_ to the _exponent_ power (which may be an integer, float,
01578  *  or anything that will coerce to a number). The result may be
01579  *  a Fixnum, Bignum, or Float
01580  *
01581  *    123456789 ** 2      #=> 15241578750190521
01582  *    123456789 ** 1.2    #=> 5126464716.09932
01583  *    123456789 ** -2     #=> 6.5610001194102e-17
01584  */
01585 
01586 VALUE
01587 rb_big_pow(x, y)
01588     VALUE x, y;
01589 {
01590     double d;
01591     long yy;
01592     
01593     if (y == INT2FIX(0)) return INT2FIX(1);
01594     switch (TYPE(y)) {
01595       case T_FLOAT:
01596         d = RFLOAT(y)->value;
01597         break;
01598 
01599       case T_BIGNUM:
01600         rb_warn("in a**b, b may be too big");
01601         d = rb_big2dbl(y);
01602         break;
01603 
01604       case T_FIXNUM:
01605         yy = FIX2LONG(y);
01606         if (yy > 0) {
01607             VALUE z = x;
01608 
01609             for (;;) {
01610                 yy -= 1;
01611                 if (yy == 0) break;
01612                 while (yy % 2 == 0) {
01613                     yy /= 2;
01614                     x = rb_big_mul(x, x);
01615                 }
01616                 z = rb_big_mul(z, x);
01617             }
01618             return bignorm(z);
01619         }
01620         d = (double)yy;
01621         break;
01622 
01623       default:
01624         return rb_num_coerce_bin(x, y);
01625     }
01626     return rb_float_new(pow(rb_big2dbl(x), d));
01627 }
01628 
01629 /*
01630  * call-seq:
01631  *     big & numeric   =>  integer
01632  *
01633  * Performs bitwise +and+ between _big_ and _numeric_.
01634  */
01635 
01636 VALUE
01637 rb_big_and(xx, yy)
01638     VALUE xx, yy;
01639 {
01640     volatile VALUE x, y, z;
01641     BDIGIT *ds1, *ds2, *zds;
01642     long i, l1, l2;
01643     char sign;
01644 
01645     x = xx;
01646     y = rb_to_int(yy);
01647     if (FIXNUM_P(y)) {
01648         y = rb_int2big(FIX2LONG(y));
01649     }
01650     if (!RBIGNUM(y)->sign) {
01651         y = rb_big_clone(y);
01652         get2comp(y);
01653     }
01654     if (!RBIGNUM(x)->sign) {
01655         x = rb_big_clone(x);
01656         get2comp(x);
01657     }
01658     if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
01659         l1 = RBIGNUM(y)->len;
01660         l2 = RBIGNUM(x)->len;
01661         ds1 = BDIGITS(y);
01662         ds2 = BDIGITS(x);
01663         sign = RBIGNUM(y)->sign;
01664     }
01665     else {
01666         l1 = RBIGNUM(x)->len;
01667         l2 = RBIGNUM(y)->len;
01668         ds1 = BDIGITS(x);
01669         ds2 = BDIGITS(y);
01670         sign = RBIGNUM(x)->sign;
01671     }
01672     z = bignew(l2, RBIGNUM(x)->sign || RBIGNUM(y)->sign);
01673     zds = BDIGITS(z);
01674 
01675     for (i=0; i<l1; i++) {
01676         zds[i] = ds1[i] & ds2[i];
01677     }
01678     for (; i<l2; i++) {
01679         zds[i] = sign?0:ds2[i];
01680     }
01681     if (!RBIGNUM(z)->sign) get2comp(z);
01682     return bignorm(z);
01683 }
01684 
01685 /*
01686  * call-seq:
01687  *     big | numeric   =>  integer
01688  *
01689  * Performs bitwise +or+ between _big_ and _numeric_.
01690  */
01691 
01692 VALUE
01693 rb_big_or(xx, yy)
01694     VALUE xx, yy;
01695 {
01696     volatile VALUE x, y, z;
01697     BDIGIT *ds1, *ds2, *zds;
01698     long i, l1, l2;
01699     char sign;
01700 
01701     x = xx;
01702     y = rb_to_int(yy);
01703     if (FIXNUM_P(y)) {
01704         y = rb_int2big(FIX2LONG(y));
01705     }
01706     if (!RBIGNUM(y)->sign) {
01707         y = rb_big_clone(y);
01708         get2comp(y);
01709     }
01710     if (!RBIGNUM(x)->sign) {
01711         x = rb_big_clone(x);
01712         get2comp(x);
01713     }
01714     if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
01715         l1 = RBIGNUM(y)->len;
01716         l2 = RBIGNUM(x)->len;
01717         ds1 = BDIGITS(y);
01718         ds2 = BDIGITS(x);
01719         sign = RBIGNUM(y)->sign;
01720     }
01721     else {
01722         l1 = RBIGNUM(x)->len;
01723         l2 = RBIGNUM(y)->len;
01724         ds1 = BDIGITS(x);
01725         ds2 = BDIGITS(y);
01726         sign = RBIGNUM(x)->sign;
01727     }
01728     z = bignew(l2, RBIGNUM(x)->sign && RBIGNUM(y)->sign);
01729     zds = BDIGITS(z);
01730 
01731     for (i=0; i<l1; i++) {
01732         zds[i] = ds1[i] | ds2[i];
01733     }
01734     for (; i<l2; i++) {
01735         zds[i] = sign?ds2[i]:(BIGRAD-1);
01736     }
01737     if (!RBIGNUM(z)->sign) get2comp(z);
01738 
01739     return bignorm(z);
01740 }
01741 
01742 /*
01743  * call-seq:
01744  *     big ^ numeric   =>  integer
01745  *
01746  * Performs bitwise +exclusive or+ between _big_ and _numeric_.
01747  */
01748 
01749 VALUE
01750 rb_big_xor(xx, yy)
01751     VALUE xx, yy;
01752 {
01753     volatile VALUE x, y;
01754     VALUE z;
01755     BDIGIT *ds1, *ds2, *zds;
01756     long i, l1, l2;
01757     char sign;
01758 
01759     x = xx;
01760     y = rb_to_int(yy);
01761     if (FIXNUM_P(y)) {
01762         y = rb_int2big(FIX2LONG(y));
01763     }
01764     if (!RBIGNUM(y)->sign) {
01765         y = rb_big_clone(y);
01766         get2comp(y);
01767     }
01768     if (!RBIGNUM(x)->sign) {
01769         x = rb_big_clone(x);
01770         get2comp(x);
01771     }
01772     if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
01773         l1 = RBIGNUM(y)->len;
01774         l2 = RBIGNUM(x)->len;
01775         ds1 = BDIGITS(y);
01776         ds2 = BDIGITS(x);
01777         sign = RBIGNUM(y)->sign;
01778     }
01779     else {
01780         l1 = RBIGNUM(x)->len;
01781         l2 = RBIGNUM(y)->len;
01782         ds1 = BDIGITS(x);
01783         ds2 = BDIGITS(y);
01784         sign = RBIGNUM(x)->sign;
01785     }
01786     RBIGNUM(x)->sign = RBIGNUM(x)->sign?1:0;
01787     RBIGNUM(y)->sign = RBIGNUM(y)->sign?1:0;
01788     z = bignew(l2, !(RBIGNUM(x)->sign ^ RBIGNUM(y)->sign));
01789     zds = BDIGITS(z);
01790 
01791     for (i=0; i<l1; i++) {
01792         zds[i] = ds1[i] ^ ds2[i];
01793     }
01794     for (; i<l2; i++) {
01795         zds[i] = sign?ds2[i]:~ds2[i];
01796     }
01797     if (!RBIGNUM(z)->sign) get2comp(z);
01798 
01799     return bignorm(z);
01800 }
01801 
01802 static VALUE rb_big_rshift (VALUE,VALUE);
01803 
01804 /*
01805  * call-seq:
01806  *     big << numeric   =>  integer
01807  *
01