test_bigint.js (8478B)
1 "use strict"; 2 3 function assert(actual, expected, message) { 4 if (arguments.length == 1) 5 expected = true; 6 7 if (actual === expected) 8 return; 9 10 if (actual !== null && expected !== null 11 && typeof actual == 'object' && typeof expected == 'object' 12 && actual.toString() === expected.toString()) 13 return; 14 15 throw Error("assertion failed: got |" + actual + "|" + 16 ", expected |" + expected + "|" + 17 (message ? " (" + message + ")" : "")); 18 } 19 20 function assertThrows(err, func) 21 { 22 var ex; 23 ex = false; 24 try { 25 func(); 26 } catch(e) { 27 ex = true; 28 assert(e instanceof err); 29 } 30 assert(ex, true, "exception expected"); 31 } 32 33 // load more elaborate version of assert if available 34 try { __loadScript("test_assert.js"); } catch(e) {} 35 36 /*----------------*/ 37 38 function bigint_pow(a, n) 39 { 40 var r, i; 41 r = 1n; 42 for(i = 0n; i < n; i++) 43 r *= a; 44 return r; 45 } 46 47 /* a must be < b */ 48 function test_less(a, b) 49 { 50 assert(a < b); 51 assert(!(b < a)); 52 assert(a <= b); 53 assert(!(b <= a)); 54 assert(b > a); 55 assert(!(a > b)); 56 assert(b >= a); 57 assert(!(a >= b)); 58 assert(a != b); 59 assert(!(a == b)); 60 } 61 62 /* a must be numerically equal to b */ 63 function test_eq(a, b) 64 { 65 assert(a == b); 66 assert(b == a); 67 assert(!(a != b)); 68 assert(!(b != a)); 69 assert(a <= b); 70 assert(b <= a); 71 assert(!(a < b)); 72 assert(a >= b); 73 assert(b >= a); 74 assert(!(a > b)); 75 } 76 77 function test_bigint1() 78 { 79 var a, r; 80 81 test_less(2n, 3n); 82 test_eq(3n, 3n); 83 84 test_less(2, 3n); 85 test_eq(3, 3n); 86 87 test_less(2.1, 3n); 88 test_eq(Math.sqrt(4), 2n); 89 90 a = bigint_pow(3n, 100n); 91 assert((a - 1n) != a); 92 assert(a == 515377520732011331036461129765621272702107522001n); 93 assert(a == 0x5a4653ca673768565b41f775d6947d55cf3813d1n); 94 95 r = 1n << 31n; 96 assert(r, 2147483648n, "1 << 31n === 2147483648n"); 97 98 r = 1n << 32n; 99 assert(r, 4294967296n, "1 << 32n === 4294967296n"); 100 } 101 102 function test_bigint2() 103 { 104 assert(BigInt(""), 0n); 105 assert(BigInt(" 123"), 123n); 106 assert(BigInt(" 123 "), 123n); 107 assertThrows(SyntaxError, () => { BigInt("+") } ); 108 assertThrows(SyntaxError, () => { BigInt("-") } ); 109 assertThrows(SyntaxError, () => { BigInt("\x00a") } ); 110 assertThrows(SyntaxError, () => { BigInt(" 123 r") } ); 111 } 112 113 function test_bigint3() 114 { 115 assert(Number(0xffffffffffffffffn), 18446744073709552000); 116 assert(Number(-0xffffffffffffffffn), -18446744073709552000); 117 assert(100000000000000000000n == 1e20, true); 118 assert(100000000000000000001n == 1e20, false); 119 assert((1n << 100n).toString(10), "1267650600228229401496703205376"); 120 assert((-1n << 100n).toString(36), "-3ewfdnca0n6ld1ggvfgg"); 121 assert((1n << 100n).toString(8), "2000000000000000000000000000000000"); 122 123 assert(0x5a4653ca673768565b41f775n << 78n, 8443945299673273647701379149826607537748959488376832n); 124 assert(-0x5a4653ca673768565b41f775n << 78n, -8443945299673273647701379149826607537748959488376832n); 125 assert(0x5a4653ca673768565b41f775n >> 78n, 92441n); 126 assert(-0x5a4653ca673768565b41f775n >> 78n, -92442n); 127 128 assert(~0x5a653ca6n, -1516584103n); 129 assert(0x5a463ca6n | 0x67376856n, 2138537206n); 130 assert(0x5a463ca6n & 0x67376856n, 1107699718n); 131 assert(0x5a463ca6n ^ 0x67376856n, 1030837488n); 132 133 assert(3213213213213213432453243n / 123434343439n, 26031760073331n); 134 assert(-3213213213213213432453243n / 123434343439n, -26031760073331n); 135 assert(-3213213213213213432453243n % -123434343439n, -26953727934n); 136 assert(3213213213213213432453243n % 123434343439n, 26953727934n); 137 138 assert((-2n) ** 127n, -170141183460469231731687303715884105728n); 139 assert((2n) ** 127n, 170141183460469231731687303715884105728n); 140 assert((-256n) ** 11n, -309485009821345068724781056n); 141 assert((7n) ** 20n, 79792266297612001n); 142 } 143 144 /* pi computation */ 145 146 /* return floor(log2(a)) for a > 0 and 0 for a = 0 */ 147 function floor_log2(a) 148 { 149 var k_max, a1, k, i; 150 k_max = 0n; 151 while ((a >> (2n ** k_max)) != 0n) { 152 k_max++; 153 } 154 k = 0n; 155 a1 = a; 156 for(i = k_max - 1n; i >= 0n; i--) { 157 a1 = a >> (2n ** i); 158 if (a1 != 0n) { 159 a = a1; 160 k |= (1n << i); 161 } 162 } 163 return k; 164 } 165 166 /* return ceil(log2(a)) for a > 0 */ 167 function ceil_log2(a) 168 { 169 return floor_log2(a - 1n) + 1n; 170 } 171 172 /* return floor(sqrt(a)) (not efficient but simple) */ 173 function int_sqrt(a) 174 { 175 var l, u, s; 176 if (a == 0n) 177 return a; 178 l = ceil_log2(a); 179 u = 1n << ((l + 1n) / 2n); 180 /* u >= floor(sqrt(a)) */ 181 for(;;) { 182 s = u; 183 u = ((a / s) + s) / 2n; 184 if (u >= s) 185 break; 186 } 187 return s; 188 } 189 190 /* return pi * 2**prec */ 191 function calc_pi(prec) { 192 const CHUD_A = 13591409n; 193 const CHUD_B = 545140134n; 194 const CHUD_C = 640320n; 195 const CHUD_C3 = 10939058860032000n; /* C^3/24 */ 196 const CHUD_BITS_PER_TERM = 47.11041313821584202247; /* log2(C/12)*3 */ 197 198 /* return [P, Q, G] */ 199 function chud_bs(a, b, need_G) { 200 var c, P, Q, G, P1, Q1, G1, P2, Q2, G2; 201 if (a == (b - 1n)) { 202 G = (2n * b - 1n) * (6n * b - 1n) * (6n * b - 5n); 203 P = G * (CHUD_B * b + CHUD_A); 204 if (b & 1n) 205 P = -P; 206 Q = b * b * b * CHUD_C3; 207 } else { 208 c = (a + b) >> 1n; 209 [P1, Q1, G1] = chud_bs(a, c, true); 210 [P2, Q2, G2] = chud_bs(c, b, need_G); 211 P = P1 * Q2 + P2 * G1; 212 Q = Q1 * Q2; 213 if (need_G) 214 G = G1 * G2; 215 else 216 G = 0n; 217 } 218 return [P, Q, G]; 219 } 220 221 var n, P, Q, G; 222 /* number of serie terms */ 223 n = BigInt(Math.ceil(Number(prec) / CHUD_BITS_PER_TERM)) + 10n; 224 [P, Q, G] = chud_bs(0n, n, false); 225 Q = (CHUD_C / 12n) * (Q << prec) / (P + Q * CHUD_A); 226 G = int_sqrt(CHUD_C << (2n * prec)); 227 return (Q * G) >> prec; 228 } 229 230 function compute_pi(n_digits) { 231 var r, n_digits, n_bits, out; 232 /* we add more bits to reduce the probability of bad rounding for 233 the last digits */ 234 n_bits = BigInt(Math.ceil(n_digits * Math.log2(10))) + 32n; 235 r = calc_pi(n_bits); 236 r = ((10n ** BigInt(n_digits)) * r) >> n_bits; 237 out = r.toString(); 238 return out[0] + "." + out.slice(1); 239 } 240 241 function test_pi() 242 { 243 assert(compute_pi(2000), "3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151557485724245415069595082953311686172785588907509838175463746493931925506040092770167113900984882401285836160356370766010471018194295559619894676783744944825537977472684710404753464620804668425906949129331367702898915210475216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992458631503028618297455570674983850549458858692699569092721079750930295532116534498720275596023648066549911988183479775356636980742654252786255181841757467289097777279380008164706001614524919217321721477235014144197356854816136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179049460165346680498862723279178608578438382796797668145410095388378636095068006422512520511739298489608412848862694560424196528502221066118630674427862203919494504712371378696095636437191728746776465757396241389086583264599581339047802759009"); 244 } 245 246 test_bigint1(); 247 test_bigint2(); 248 test_bigint3(); 249 test_pi();