1 2 /** 3 * @name CeL quotient function 4 * @fileoverview 5 * 本檔案包含了 quotient 的 functions。 6 * @since 2010/3/11 16:59:59 7 * @example 8 * CeL.use('math'); // TODO: bug 9 * CeL.use('math.quotient'); 10 * var q1 = new CeL.quotient(2,3); 11 * // 數字基底的轉換: 12 * CeL.log(CeL.quotient.parse_base('4877.6'.toLowerCase(),10).to_base(16).replace(/_([^\(]+)/,'_<i style="text-decoration:overline">$1</i>')); 13 */ 14 15 16 /* 17 TODO: 18 use {String} value + {Number} exponent 19 20 http://www.leemon.com/crypto/BigInt.html 21 http://www-cs-students.stanford.edu/~tjw/jsbn/ 22 http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html 23 24 */ 25 26 if (typeof CeL === 'function') 27 CeL.setup_module('data.math.quotient', 28 { 29 require : 'data.math.to_rational_number|data.math.gcd|data.math.factorization', 30 code : function(library_namespace, load_arguments) { 31 32 // requiring 33 var to_rational_number,gcd,factorization; 34 eval(library_namespace.use_function(this)); 35 36 37 //library_namespace.debug(to_rational_number); 38 //library_namespace.debug(gcd); 39 40 41 //============================================================================ 42 // definition of module quotient 43 44 var 45 /* 46 整數部分 47 分數 fraction 48 真分數 proper fraction 49 vinculum = "divide by" 50 */ 51 /** 52 * 有理數 rational number,有理数全体のつくる集合はしばしば、商を意味する quotient の頭文字をとり、太字の Q で表す。<br/> 53 * 若要輸入不同基底的數值,請用 parse_base() 54 * @param numerator 分子 55 * @param denominator 分母 56 * @param {Boolean} approximate 取近似值 57 * @example 58 * CeL.log((new CeL.quotient(3,4)).count('*',new CeL.quotient(2,7)).reduce().to_print_mode()); 59 * @class quotient 的 functions 60 * @constructor 61 */ 62 CeL.data.math.quotient 63 = function(numerator, denominator, approximate) { 64 if (typeof numerator === 'object' && numerator instanceof _ 65 //&& numerator.Class === 'quotient' 66 ) 67 return numerator; 68 if (isNaN(numerator)) 69 numerator = 0; 70 if (!denominator || isNaN(denominator)) 71 denominator = 1; 72 else if (denominator < 0) 73 denominator = -denominator, numerator = -numerator; 74 75 // to_rational_number 需 test,並回傳(分子,分母,誤差)! 76 var q = to_rational_number(numerator); 77 //library_namespace.debug(numerator + ' → ' + q); 78 if (!q) 79 numerator = 0; 80 else if (approximate || !q[2]) 81 // 無誤差時使用之 82 numerator = q[0], denominator *= q[1] || 1; 83 else 84 while (numerator % 1 || denominator % 1) 85 // 化為整數 86 numerator *= 10, denominator *= 10; 87 88 // value 89 this.n = numerator, this.d = denominator; 90 // this.type='quotient'; 91 //library_namespace.debug(this.n + ' / ' + this.d); 92 return this; 93 }; 94 95 //class public interface --------------------------- 96 97 CeL.data.math.quotient 98 . 99 /** 100 * 循環節分隔符號: {String} 整數.小數__repetend_separator__循環節 101 * @memberOf CeL.data.math.quotient 102 */ 103 repetend_separator = '_';//' ' 104 105 CeL.data.math.quotient 106 . 107 /** 108 * 數字集 109 * @memberOf CeL.data.math.quotient 110 * @see 111 * <a href="http://en.wikipedia.org/wiki/Numerical_digit" accessdate="2010/4/16 20:47">Numerical digit</a> 112 */ 113 digit_char = '0123456789abcdefghijklmnopqrstuvwxyz';//.split('') 114 115 116 CeL.data.math.quotient 117 . 118 /** 119 * 轉換指定進位的數字成為 quotient 物件 120 * @since 2004/7/9 16:13 121 * @param number 數字 122 * @param base 基底 123 * @param digit_char 循環小數 digit 字集 124 * @return 回傳 quotient 物件,請用 quotient.to_base() 傳回所欲之 base 125 * @memberOf CeL.data.math.quotient 126 * @example 127 * var q=parse_base('10000.'+_.repetend_separator+'3',11); 128 * if(!q) 129 * alert('bad input!'); 130 * else 131 * library_namespace.debug('<br/>'+q.base(8)+','+q.base()+' , '+q.to_print_mode()+','+q.print(1)+','+q.to_print_mode(2)+','+q.to_print_mode(3,0,'',5)); 132 */ 133 parse_base = function(number, base, digit_char) { 134 // if(!num) num = 0; 135 if ((!(base = Math.floor(base)) || base < 2) && digit_char) 136 base = digit_char.length; 137 138 if (!digit_char) 139 digit_char = _.digit_char; 140 if (isNaN(base) || base < 2 || base > digit_char.length) 141 base = 10; 142 if (!number || base === 10 143 && ('' + number).indexOf(_.repetend_separator) === -1) 144 // 可能有循環小數,所以不能放過僅僅 base === 10 145 return new _(number); 146 147 var i = 0, n = new _(0, 1), m = 0, t = 0, p, c = {}, r = new _(0, 1); 148 for (; i < digit_char.length; i++) 149 c[digit_char.charAt(i)] = i; // 字集 150 151 number += '', i = -1, n.d = r.d = 1; 152 //library_namespace.debug('<br/>'+i+','+num.length+','+t+','+num+','+n.to_print_mode()); 153 if (number.charAt(0) === '-') 154 i = 0, m = 1; 155 while (++i < number.length && (p = number.charAt(i)) != '.') 156 // 整數 157 if (isNaN(p = c[p]) || p >= base) 158 // error! 159 return; 160 else 161 t = t * base + p; 162 //library_namespace.debug('<br/>'+i+','+num.length+','+t+','+num+','+n.to_print_mode()); 163 while (++i < number.length 164 && (p = number.charAt(i)) != _.repetend_separator) 165 // 小數 166 if (isNaN(p = c[p]) || p >= base) 167 // error! 168 return; 169 else 170 n.n = n.n * base + p, n.d *= base; 171 while (++i < number.length) 172 // 循環節 173 if (isNaN(p = c[number.charAt(i)]) || p >= base) 174 return; // error! 175 else 176 r.n = r.n * base + p, r.d *= base; 177 //library_namespace.debug('<br/>**'+n.to_print_mode()); 178 // 善後 179 n = n.count('+=', t); 180 if (r.n) 181 r.d = (r.d - 1) * n.d, n.count('+=', r); 182 n.reduce(); 183 //library_namespace.debug('<br/>*'+n.to_print_mode()); 184 if (m) 185 n.n = -n.n; 186 return n; 187 }; 188 189 190 191 CeL.data.math.quotient 192 .prototype = { 193 194 // instance public interface ------------------- 195 196 197 /** 198 * 最簡分數/化簡, 約分 reduction 199 * @return 化簡後的 200 * @name CeL.data.math.quotient.prototype.reduce 201 */ 202 reduce : function() { 203 var g = gcd(this.n, this.d); 204 if (g && g > 1) 205 this.n /= g, this.d /= g; 206 return this; 207 }, 208 209 /** 210 * 四則運算 + - * / (+-×÷)**[=] 211 * @param op operator 212 * @param q2 the second quotient 213 * @return 計算後的結果 214 * @see 215 * <a href="http://www.javaworld.com.tw/jute/post/view?bid=35&id=30169&tpg=1&ppg=1&sty=1&age=0#30169" accessdate="2010/4/16 20:47">JavaWorld@TW Java論壇 - post.view</a> 216 * @name CeL.data.math.quotient.prototype.count 217 */ 218 count : function(op, q2) { 219 var q; 220 if (op.slice(-1) === '=') 221 q = this, op = op.slice(0, -1); 222 else 223 q = new _(this); 224 225 q2 = new _(q2); 226 //library_namespace.debug('<br/>'+this.type+','+q.to_print_mode()+' , '+q2.to_print_mode()); 227 if (op === '-') 228 q2.n = -q2.n, op = '+'; 229 else if (op === '/') { 230 var t = q2.n; 231 q2.n = q2.d, q2.d = t, op = '*'; 232 } 233 //library_namespace.debug('<br/>'+q.to_print_mode(1)+','+q2.to_print_mode(1)); 234 if (op === '+') 235 q.n = q.n * q2.d + q.d * q2.n, q.d *= q2.d; 236 else if (op === '*') 237 q.n *= q2.n, q.d *= q2.d; 238 // N! 是指 N的階乘 (Factorial,power) 239 else if ((op === '**' || op === '^') && q2.reduce().d === 1) { 240 q.reduce(), q.n = Math.pow(q.n, q2.n), q.d = Math.pow(q.d, q2.n); 241 return q; 242 } else { 243 library_namespace.err('illegal operator [' + op + ']!'); 244 return this; 245 } 246 //library_namespace.debug('<br/>'+q.to_print_mode(1)+','+q2.to_print_mode(1)); 247 // other: error 248 //library_namespace.debug('<br/>_'+q.reduce().to_print_mode()); 249 try { 250 return q.reduce(); 251 } catch (e) { 252 } 253 return q; 254 }, 255 256 /** 257 * 依指定基底轉成循環小數 circulating decimal / repeating decimal。 258 * 特殊情況可以考慮使用 .toString(),會快很多。 259 * TODO: 小數 260 * @since 2004/7/9 13:28 261 * @param base 基底 262 * @param digit_char 循環小數 digit 字集 263 * @return (decimal/數字部分string,repunitIndex/循環節Repetend出現在) 264 * @see 265 * <a href="http://mathworld.wolfram.com/RepeatingDecimal.html" accessdate="2010/4/16 20:47">Repeating Decimal -- from Wolfram MathWorld</a> 266 * <a href="http://hk.geocities.com/goodprimes/OFrp.htm">循環小數與素數。素之異類。</a> 267 * @name CeL.data.math.quotient.prototype.to_base 268 */ 269 to_base : function(base, digit_char) { 270 //if (!isNaN(digit_char)) digit_char += ''; 271 if (typeof digit_char !== 'string' || digit_char.length < 2) 272 // 字集 273 digit_char = _.digit_char; 274 275 // 基底預設為 10 進位 276 if (!(base = Math.floor(base)) || base == 10 || 277 // illegal base 278 base < 2 || base > digit_char.length) 279 return this.to_decimal(); 280 281 this.reduce(); 282 var d = this.d, o = this.n, i, t, m = 0, 283 // find base 的因數(factor) 284 f = factorization(base); 285 if (o < 0) 286 // 負數 287 o = -o, m = 1; 288 289 // find 分母的因數(factor)與基底 base 之交集(不能用gcd) 290 for (i = 0, g = 1, t = d; i < f.length; i += 2) 291 while (t % f[i] === 0) 292 g *= f[i], t /= f[i]; 293 294 // get 整數 integer 部分 → out 295 f = o % d; 296 i = (o - f) / d; 297 o = ''; 298 while (i) 299 t = i % base, i = (i - t) / base, o = digit_char.charAt(t) + o; 300 if (!o) 301 o = '0', m = 0; 302 //library_namespace.debug('<br/>_' + typeof o + ',' + (o || '(null)') + ',' + o); 303 if (!f) 304 return m ? '-' + o : o; 305 306 // 進入小數 307 o += '.'; 308 309 // set 餘數f/分母d, 餘數residue mark r=f, 循環節 Repetend location of out:l, 已解決的因數 s 310 var r = f, l = o.length, s = 1; 311 312 // do main loop 313 // while(o.length-l<d){ // 限制?位: debug用 314 for (;;) { 315 //library_namespace.debug('<br/>.'+r+','+f+'/'+d+'('+base+'),'+s+':'+g+','+o); 316 if (!f) { 317 // 可以整除,無循環。 318 l = 0; 319 break; 320 } 321 f *= base; 322 if (s === g) { 323 // 分母與 base 已互質 324 t = f, f %= d, o += digit_char.charAt((t - f) / d); 325 if (f === r) 326 // bingo! 餘數重複出現,循環節結束。 327 break; 328 } else { 329 // f 與 d 已互質 330 t = gcd(base, d), s *= t, f /= t, d /= t, 331 // do the same thing 332 t = f, f %= d, o += digit_char.charAt((t - f) / d), 333 // r 需重設..此處有否可能出問題? maybe not? 334 r = f, l = o.length; 335 } 336 } 337 338 // 善後 339 if (l) 340 o += '(' + (o.length - l) + ')', o = o.slice(0, l) 341 + _.repetend_separator + o.substr(l); 342 if (m) 343 o = '-' + o; 344 return o; 345 }, 346 347 /** 348 * 為十進位最佳化的 to_base()<br/> 349 * 以結論來說,好像快不了多少? 350 * @since 2004/7/9 13:47 351 * @return 352 * @name CeL.data.math.quotient.prototype.to_decimal 353 */ 354 to_decimal : function() { 355 this.reduce(); 356 var d = this.d, t = d, g = 1, m = 0, f, o = this.n; 357 if (o < 0) 358 o = -o, m = 1; // 負數 359 360 // find 分母的 2,5 因數 361 while (t % 2 === 0) 362 // 使用下面這行會造成 bug: 輸出 .110011001100110011001100110011001100(2) 會導致 g===t===0, 掛掉 363 // 以結論來說,好像快不了多少? 364 //g <<= 1, t >>= 1; 365 g *= 2, t /= 2; 366 while (t % 5 === 0) 367 g *= 5, t /= 5; 368 369 // get 整數 integer 部分 → out 370 f = o % d, o = (o - f) / d; 371 //library_namespace.debug('<br/>_'+typeof o+','+(o||'(null)')+','+o); 372 if (!f) 373 // 留下+- 374 return (m ? '-' : '') + o; 375 376 // 進入小數 377 o += '.'; 378 379 // set 餘數f/分母d, 餘數 residue mark r=f, 循環節 Repetend location of out:l, 已解決的因數 s 380 var r = f, l = o.length, s = 1; 381 382 // do main loop 383 // while(o.length-l<d){// 限制?位:debug用 384 for (;;) { 385 //library_namespace.debug('<br/>.'+r+','+f+'/'+d+','+s+':'+g+','+o); 386 if (!f) { 387 // 可以整除,無循環。 388 l = 0; 389 break; 390 } 391 f *= 10; 392 if (s === g) { 393 // 分母與 base 已互質 394 t = f, f %= d, o += (t - f) / d; 395 if (f === r) 396 // bingo! 循環節結束 397 break; 398 } else { 399 t = d % 5 === 0 ? d % 2 === 0 ? 10 : 5 : 2, s *= t, f /= t, d /= t, 400 // do the same thing 401 t = f, f %= d, o += (t - f) / d, 402 // r 需重設..此處有否可能出問題? maybe not? 403 r = f, l = o.length; 404 } 405 } 406 407 // 善後 408 if (l) 409 o += '(' + (o.length - l) + ')', 410 o = o.slice(0, l) + _.repetend_separator + o.substr(l); 411 if (m) 412 o = '-' + o; 413 return o; 414 }, 415 416 417 /* 418 有效位數、小數位數 http://technet.microsoft.com/zh-tw/library/ms190476.aspx 419 Precision, Scale 420 有效位數是數字的位數。小數位數是數字中在小數點右側的位數。例如,123.45 這個數字的有效位數是 5,小數位數是 2。 421 Precision is the number of digits in a number. Scale is the number of digits to the right of the decimal point in a number. For example, the number 123.45 has a precision of 5 and a scale of 2. 422 */ 423 424 /** 425 * 顯示成各種不同模式的數字 426 * @since 2004/7/9 14:23 427 * @param mode 顯示模式 428 * 0 假分數 improper fraction, 429 * 1 帶分數 mixed number, 430 * 2 直接除(10進位), 431 * 3 轉成循環小數,除至小數點下digit位數(非四捨五入!). 432 * @param base 基底 433 * @param sum_char 顯示帶分數時代表整數與真分數之間的分隔。多為' '或'+'或''。 434 * @param digit 轉成循環小數時,代表循環小數 digit 字集 435 * @return {String} 顯示模式數字 436 * @name CeL.data.math.quotient.prototype.to_print_mode 437 */ 438 to_print_mode : function(mode, base, sum_char, digit) { 439 if (mode < 3 || !mode) { 440 if (mode === 2) 441 return this.n / this.d; 442 var p, f; 443 if (!mode || this.n < this.d) 444 p = this.n + '/' + this.d; 445 else 446 f = this.n % this.d, 447 p = (this.n - f) / this.d 448 + (f ? (sum_char || '+') + f + '/' + this.d : ''); 449 return p; 450 } 451 452 if (mode === 3) { 453 var n = this.to_base(base, sum_char); 454 if (isNaN(digit)) 455 return n; 456 var f = n.indexOf(_.repetend_separator), b = n.indexOf('.'); 457 if (f === -1 || !digit) 458 return b === -1 ? n : 459 digit ? n.slice(0, b + digit + 1) : n.slice(0, b); 460 digit += b + 1, 461 // 循環節 462 b = n.substr(f + 1), 463 n = n.slice(0, f); 464 while (n.length < digit) 465 n += b; 466 return n.slice(0, digit); 467 } 468 }, 469 470 /** 471 * 測試大小 472 * @param q2 the second quotient 473 * @return {Number} 0:==, <0:<, >0:> 474 * @name CeL.data.math.quotient.prototype.compare_to 475 */ 476 compare_to : function(q2) { 477 q2 = new _(q2); 478 return this.n * q2.d - this.d * q2.n; 479 } 480 481 }; 482 483 // setup toString function 484 _.prototype.toString = _.prototype.to_print_mode; 485 486 487 488 return ( 489 CeL.data.math.quotient 490 ); 491 } 492 493 494 }); 495 496