31 #if defined __MINGW32__
32 #define USHORT _USHORT
35 #define BDIGITS(x) (RBIGNUM_DIGITS(x))
36 #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
37 #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
38 #define BIGRAD_HALF ((BDIGIT)(BIGRAD >> 1))
39 #define DIGSPERLONG (SIZEOF_LONG/SIZEOF_BDIGITS)
41 # define DIGSPERLL (SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
43 #define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
44 #define BIGDN(x) RSHIFT((x),BITSPERDIG)
45 #define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
46 #define BDIGMAX ((BDIGIT)-1)
48 #define BIGZEROP(x) (RBIGNUM_LEN(x) == 0 || \
49 (BDIGITS(x)[0] == 0 && \
50 (RBIGNUM_LEN(x) == 1 || bigzero_p(x))))
52 #define BIGNUM_DEBUG 0
54 #define ON_DEBUG(x) do { x; } while (0)
104 if (l < 0)
return -1;
117 #define RBIGNUM_SET_LEN(b,l) \
118 ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
119 (void)(RBASIC(b)->flags = \
120 (RBASIC(b)->flags & ~RBIGNUM_EMBED_LEN_MASK) | \
121 ((l) << RBIGNUM_EMBED_LEN_SHIFT)) : \
122 (void)(RBIGNUM(b)->as.heap.len = (l)))
133 RBIGNUM(big)->as.heap.digits = ds;
134 RBASIC(big)->flags &= ~RBIGNUM_EMBED_FLAG;
139 ds =
RBIGNUM(big)->as.heap.digits;
183 #define bignew(len,sign) bignew_1(rb_cBignum,(len),(sign))
188 return bignew(len, sign != 0);
210 while (i--) ds[
i] = ~ds[
i];
214 ds[i++] =
BIGLO(num);
236 if (len == 0)
return x;
237 while (--len && !ds[len]);
250 if (len == 0)
return INT2FIX(0);
253 #if 2*SIZEOF_BDIGITS > SIZEOF_LONG
298 digits[i++] =
BIGLO(num);
303 while (--i && !digits[i]) ;
339 #if SIZEOF_LONG % SIZEOF_BDIGITS != 0
340 # error unexpected SIZEOF_LONG : SIZEOF_BDIGITS ratio
365 buf[0] = (
unsigned long)tmp;
366 tmp = tmp < 0 ? ~0L : 0;
367 for (i = 1; i < num_longs; i++)
368 buf[i] = (
unsigned long)tmp;
375 for (i = 0; i < num_longs && ds < dend; i++) {
377 for (j = 0; j <
DIGSPERLONG && ds < dend; j++, ds++) {
382 for (; i < num_longs; i++)
385 for (i = 0; i < num_longs; i++) {
388 for (i = 0; i < num_longs; i++) {
401 while (2 <= num_longs) {
402 if (buf[num_longs-1] == 0 && (
long)buf[num_longs-2] >= 0)
404 else if (buf[num_longs-1] == ~0UL && (
long)buf[num_longs-2] < 0)
411 else if (num_longs == 1)
420 for (i = 0; i < num_longs; i++) {
421 unsigned long d = buf[
i];
422 #if SIZEOF_LONG == SIZEOF_BDIGITS
432 if ((
long)buf[num_longs-1] < 0) {
442 #if SIZEOF_LONG_LONG == QUAD_SIZE && SIZEOF_BDIGITS*2 == SIZEOF_LONG_LONG
468 memcpy(buf, (
char*)&q, SIZEOF_LONG_LONG);
474 unsigned LONG_LONG q;
480 memcpy(&q, buf, SIZEOF_LONG_LONG);
483 if ((LONG_LONG)q < 0) {
493 big =
bignew(DIGSPERLL, 1);
495 while (i < DIGSPERLL) {
496 digits[i++] =
BIGLO(q);
501 while (i-- && !digits[i]) ;
516 for (i = 0; i <
len; i++)
518 for (i = 0; i <
len; i++) {
540 memcpy(buf, (
char*)
BDIGITS(val), len);
546 #define BNEG(b) (RSHIFT(((BDIGIT*)(b))[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)
554 if (sign &&
BNEG(buf)) {
555 char *tmp = (
char*)
BDIGITS(big);
571 char sign = 1, nondigit = 0;
580 #define ISDIGIT(c) ('0' <= (c) && (c) <= '9')
581 #define conv_digit(c) \
582 (!ISASCII(c) ? -1 : \
583 ISDIGIT(c) ? ((c) - '0') : \
584 ISLOWER(c) ? ((c) - 'a' + 10) : \
585 ISUPPER(c) ? ((c) - 'A' + 10) : \
589 if (badcheck)
goto bad;
597 else if (str[0] ==
'-') {
601 if (str[0] ==
'+' || str[0] ==
'-') {
602 if (badcheck)
goto bad;
624 else if (base < -1) {
634 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
642 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
645 case 4:
case 5:
case 6:
case 7:
649 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
652 case 9:
case 11:
case 12:
case 13:
case 14:
case 15:
657 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
662 if (base < 2 || 36 < base) {
675 while ((c = *++str) ==
'0' || c ==
'_') {
682 if (!(c = *str) ||
ISSPACE(c)) --str;
686 if (c < 0 || c >= base) {
687 if (badcheck)
goto bad;
690 len *=
strlen(str)*
sizeof(char);
693 unsigned long val =
STRTOUL(str, &end, base);
695 if (str < end && *end ==
'_')
goto bigparse;
697 if (end == str)
goto bad;
698 while (*end &&
ISSPACE(*end)) end++;
717 if (badcheck && *str ==
'_')
goto bad;
721 for (i=len;i--;) zds[i]=0;
722 while ((c = *str++) != 0) {
725 if (badcheck)
goto bad;
734 if (c >= base)
break;
741 zds[i++] =
BIGLO(num);
753 if (s+1 < str && str[-1] ==
'_')
goto bad;
754 while (*str &&
ISSPACE(*str)) str++;
798 rb_ull2big(
unsigned LONG_LONG n)
805 big =
bignew(DIGSPERLL, 1);
807 while (i < DIGSPERLL) {
808 digits[i++] =
BIGLO(num);
813 while (i-- && !digits[i]) ;
819 rb_ll2big(LONG_LONG n)
836 rb_ull2inum(
unsigned LONG_LONG n)
839 return rb_ull2big(n);
843 rb_ll2inum(LONG_LONG n)
868 #define POW2_P(x) (((x)&((x)-1))==0)
874 # define MASK_55 0x5555555555555555UL
875 # define MASK_33 0x3333333333333333UL
876 # define MASK_0f 0x0f0f0f0f0f0f0f0fUL
878 # define MASK_55 0x55555555UL
879 # define MASK_33 0x33333333UL
880 # define MASK_0f 0x0f0f0f0fUL
890 return (
int)(x & 0x7f);
896 static inline unsigned long
921 return (
int)
ones(x) - 1;
930 #define LOG2_KARATSUBA_DIGITS 7
931 #define KARATSUBA_DIGITS (1L<<LOG2_KARATSUBA_DIGITS)
932 #define MAX_BIG2STR_TABLE_ENTRIES 64
940 for (i = 0; i < 35; ++
i) {
942 big2str_power_cache[
i][j] =
Qnil;
950 if (
NIL_P(big2str_power_cache[base - 2][i])) {
951 big2str_power_cache[base - 2][
i] =
956 return big2str_power_cache[base - 2][
i];
967 rb_bug(
"n1 > KARATSUBA_DIGITS");
970 if (m1) *m1 = 1 << m;
1000 static const double log_2[] = {
1001 1.0, 1.58496250072116, 2.0,
1002 2.32192809488736, 2.58496250072116, 2.8073549220576,
1003 3.0, 3.16992500144231, 3.32192809488736,
1004 3.4594316186373, 3.58496250072116, 3.70043971814109,
1005 3.8073549220576, 3.90689059560852, 4.0,
1006 4.08746284125034, 4.16992500144231, 4.24792751344359,
1007 4.32192809488736, 4.39231742277876, 4.4594316186373,
1008 4.52356195605701, 4.58496250072116, 4.64385618977472,
1009 4.70043971814109, 4.75488750216347, 4.8073549220576,
1010 4.85798099512757, 4.90689059560852, 4.95419631038688,
1011 5.0, 5.04439411935845, 5.08746284125034,
1012 5.12928301694497, 5.16992500144231
1016 if (base < 2 || 36 < base)
1017 rb_bug(
"invalid radix %d", base);
1020 bits = (SIZEOF_LONG*
CHAR_BIT - 1)/2 + 1;
1032 return (
long)ceil(bits/log_2[base - 2]);
1041 while (i && j > 0) {
1046 num =
BIGUP(num) + ds[k];
1047 ds[k] = (
BDIGIT)(num / hbase);
1050 if (trim && ds[i-1] == 0) i--;
1053 ptr[--j] = ruby_digitmap[num % base];
1056 if (trim && i == 0 && num == 0)
break;
1060 while (j < len && ptr[j] ==
'0') j++;
1061 MEMMOVE(ptr, ptr + j,
char, len - j);
1069 long n1,
long len,
long hbase,
int trim)
1077 memset(ptr,
'0', len);
1089 len - m1, hbase, trim);
1092 m1, hbase, !lh && trim);
1103 long n1, n2,
len, hbase;
1113 if (base < 2 || 36 < base)
1123 #if SIZEOF_BDIGITS > 2
1130 len = off +
big2str_orig(xx, base, ptr + off, n2, hbase, trim);
1169 if (argc == 0) base = 10;
1216 if ((
long)num < 0) {
1229 if ((
long)num < 0 &&
1239 static unsigned LONG_LONG
1260 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
1270 unsigned LONG_LONG num = big2ull(x,
"long long");
1273 || (LONG_LONG)num != LLONG_MIN)) {
1289 double u = (d < 0)?-d:d;
1326 y = x >> 64;
if (y) {n -= 64; x = y;}
1329 y = x >> 32;
if (y) {n -= 32; x = y;}
1332 y = x >> 16;
if (y) {n -= 16; x = y;}
1334 y = x >> 8;
if (y) {n -= 8; x = y;}
1335 y = x >> 4;
if (y) {n -= 4; x = y;}
1336 y = x >> 2;
if (y) {n -= 2; x = y;}
1337 y = x >> 1;
if (y) {
return n - 2;}
1362 if (bits && (dl & (1UL << (bits %=
BITSPERDIG)))) {
1363 int carry = dl & ~(~(
BDIGIT)0 << bits);
1366 if ((carry = ds[i]) != 0)
break;
1370 dl &= (
BDIGIT)~0 << bits;
1449 if (a > 0.0)
return INT2FIX(-1);
1469 while(xlen-- && (xds[xlen]==yds[xlen]));
1470 if (-1 == xlen)
return INT2FIX(0);
1471 return (xds[xlen] > yds[xlen]) ?
1493 if (a > 0.0) rel =
INT2FIX(-1);
1505 case 0:
id =
'>';
break;
1507 case 2:
id =
'<';
break;
1604 volatile double a, b;
1696 for (i = 0, num = 0; i < yn; i++) {
1701 while (num && i < xn) {
1703 zds[i++] =
BIGLO(num);
1725 z = x; x = y; y = z;
1732 if (xds[i] > yds[i]) {
1735 if (xds[i] < yds[i]) {
1736 z = x; x = y; y = z;
1768 #if SIZEOF_BDIGITS == SIZEOF_LONG
1770 if (xn == 1 && num < 0) {
1776 zds[0] =
BIGLO(num);
1781 for (i=0; i<(int)(
sizeof(y)/
sizeof(
BDIGIT)); i++) {
1788 while (num && i < xn) {
1790 zds[i++] =
BIGLO(num);
1825 #if SIZEOF_BDIGITS == SIZEOF_LONG
1827 zds[0] =
BIGLO(num);
1832 for (i=0; i<(int)(
sizeof(y)/
sizeof(
BDIGIT)); i++) {
1839 while (num && i < xn) {
1841 zds[i++] =
BIGLO(num);
1844 if (num) zds[i++] = (
BDIGIT)num;
1845 else while (i < xn) {
1865 tds = xds; xds = yds; yds = tds;
1866 i = xn; xn = yn; yn =
i;
1872 zds[i++] =
BIGLO(num);
1875 while (num && i < yn) {
1877 zds[i++] =
BIGLO(num);
1884 if (num) zds[i++] = (
BDIGIT)num;
1899 if (sign)
return bigsub(y, x);
1997 while (--i && !xds[i]);
2030 while (j--) zds[j] = 0;
2031 for (i = 0; i < xl; i++) {
2034 if (dd == 0)
continue;
2036 for (j = 0; j < yl; j++) {
2038 n = zds[i + j] + ee;
2039 if (ee) zds[i + j] =
BIGLO(n);
2057 long i, xn, yn, r, n;
2058 BDIGIT *yds, *zds, *t1ds;
2062 assert(2 * xn <= yn || 3 * xn <= 2*(yn+2));
2071 for (i = 0; i < xn + yn; i++) zds[i] = 0;
2075 r = xn > yn ? yn : xn;
2106 while (--hn && !vds[hn + ln]);
2112 while (--ln && !vds[ln]);
2125 long i, n, xn, yn, t1n, t2n;
2126 VALUE xh, xl, yh, yl, z, t1, t2, t3;
2161 for (i = 2 * n + t1n; i < xn + yn; i++) zds[i] = 0;
2170 for (i = t2n; i < 2 * n; i++) zds[i] = 0;
2177 for (i = 0; i < 2 * n; i++) zds[i] = 0;
2182 t3 = xl; xl = xh; xh = t3;
2192 t3 = yl; yl = yh; yh = t3;
2222 int const s3 = BITSPERDIG-s2;
2234 *zds-- = num | xds[--xn]>>s3;
2239 for (i = s1; i > 0; --
i)
2248 int s3 = BITSPERDIG - s2;
2261 xds[i++] = (
BDIGIT)(*zds<<s3) | num;
2264 while (i < xn - s1 - 1);
2272 VALUE v0, v12, v1, v2;
2290 VALUE x0, x1, x2, y0, y1, y2;
2291 VALUE u0, u1, u2, u3, u4, v1, v2, v3;
2292 VALUE z0, z1, z2, z3, z4, z, t;
2302 y0 = x0; y1 = x1; y2 = x2;
2359 v1 = u1; v2 = u2; v3 = u3;
2397 v1 = v2 = v3 =
Qnil;
2464 for (i = 2 * len + 1; i--; ) zds[i] = 0;
2465 for (i = 0; i <
len; i++) {
2472 for (j = i + 1; j <
len; j++) {
2475 zds[i + j] =
BIGLO(c);
2477 if (
BIGDN(v)) c += w;
2484 if (c) zds[i + len + 1] += (
BDIGIT)c;
2489 #define KARATSUBA_MUL_DIGITS 70
2490 #define TOOM3_MUL_DIGITS 150
2518 t = x; x = y; y = t;
2519 tn = xn; xn = yn; yn = tn;
2542 else if (3*xn <= 2*(yn + 2))
2593 for (nyzero = 0; !yds[nyzero]; nyzero++);
2599 i = nyzero; num = 0; t2 = 0;
2603 ee = num -
BIGLO(t2);
2609 num +=
zds[j -
ny +
i] - t2;
2611 i = 0; num = 0; q--;
2622 }
while (--j >=
ny);
2647 if (nx <
ny || (nx ==
ny && xds[nx - 1] < yds[
ny - 1])) {
2649 if (modp) *modp = x;
2667 if (divp) *divp = z;
2673 if (nx==
ny) zds[nx+1] = 0;
2674 while (!yds[
ny-1])
ny--;
2689 tds[j++] =
BIGLO(t2);
2698 zds[j++] =
BIGLO(t2);
2706 while (j--) zds[j] = xds[j];
2714 if (nx > 10000 ||
ny > 10000) {
2724 j = (nx==
ny ? nx+2 : nx+1) -
ny;
2725 for (i = 0;i < j;i++) zds[i] = zds[i+
ny];
2732 while (--
ny && !zds[
ny]); ++
ny;
2736 t2 = (t2 | zds[
i]) >> dd;
2742 if (!zds[ny-1]) ny--;
2757 if (modp) *modp =
bigadd(mod, y, 1);
2918 BDIGIT bits = (~0 << nb);
2950 #define DBL_BIGDIG ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)
2975 #if SIZEOF_LONG > SIZEOF_INT
2979 if (l < INT_MIN)
return DBL2NUM(0.0);
3073 rb_warn(
"in a**b, b may be too big");
3087 const long BIGLEN_LIMIT =
BITSPERDIG*1024*1024;
3089 if ((xbits > BIGLEN_LIMIT) || (xbits * yy > BIGLEN_LIMIT)) {
3090 rb_warn(
"in a**b, b may be too big");
3094 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
3132 if (y == 0)
return INT2FIX(0);
3136 #if SIZEOF_BDIGITS == SIZEOF_LONG
3146 #if SIZEOF_BDIGITS == SIZEOF_LONG
3148 zds[0] = xds[0] & y;
3153 for (i=0; i<(int)(
sizeof(y)/
sizeof(
BDIGIT)); i++) {
3160 zds[
i] = sign?0:xds[
i];
3177 volatile VALUE x, y, z;
3212 for (i=0; i<l1; i++) {
3213 zds[
i] = ds1[
i] & ds2[
i];
3216 zds[
i] = sign?0:ds2[
i];
3237 #if SIZEOF_BDIGITS == SIZEOF_LONG
3239 zds[0] = xds[0] | y;
3244 for (i=0; i<(int)(
sizeof(y)/
sizeof(
BDIGIT)); i++) {
3268 volatile VALUE x, y, z;
3304 for (i=0; i<l1; i++) {
3305 zds[
i] = ds1[
i] | ds2[
i];
3323 sign = (y >= 0) ? 1 : 0;
3329 #if SIZEOF_BDIGITS == SIZEOF_LONG
3331 zds[0] = xds[0] ^ y;
3336 for (i=0; i<(int)(
sizeof(y)/
sizeof(
BDIGIT)); i++) {
3343 zds[
i] = sign?xds[
i]:~xds[
i];
3359 volatile VALUE x, y;
3398 for (i=0; i<l1; i++) {
3399 zds[
i] = ds1[
i] ^ ds2[
i];
3402 zds[
i] = sign?ds2[
i]:~ds2[
i];
3444 if (!
NIL_P(t))
return t;
3470 for (i=0; i<s1; i++) {
3474 for (i=0; i<
len; i++) {
3476 *zds++ =
BIGLO(num);
3508 if (!
NIL_P(t))
return t;
3532 volatile VALUE save_x;
3556 num = (num | xds[
i]) >> s2;
3557 zds[j] =
BIGLO(num);
3558 num =
BIGUP(xds[i]);
3615 while (num += ~xds[i], ++i <= s1) {