      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