最近在写数据压缩课程的作业,演示算术编码的工作过程.受Tim老师启发,将概率的显示改成了分数,以避免精度问题.以下只实现了乘法与加法,减法和除法可以类推.
1 function Fraction(numerator,denominator){
2 // 分数类
3 this .n = numerator;
4 this .d = denominator;
5 }
6
7 function fra_add(a,b){
8 // 加法
9 if (a.n == 0 )
10 return b;
11 else if (b.n == 0 )
12 return a;
13 var x = lcm(a.d,b.d);
14 var y = a.n * (x / a.d)+b.n*(x / b.d);
15 var g = gcd(x,y);
16 return new Fraction(y / g,x / g);
17 }
18
19 function fra_mul(a,b){
20 // 乘法
21 var x = a.n * b.n;
22 var y = a.d * b.d;
23 if (x == 0 )
24 return new Fraction( 0 , 1 );
25 var g = gcd(x,y);
26 return new Fraction(x / g,y / g);
27 }
28
29 function lcm(a,b){
30 // 最小公倍数
31 if (a < b){
32 var temp = a;
33 a = b;
34 b = temp;
35 }
36 for ( var i = 1 ;i <= b;i ++ ){
37 if ((a * i) % b == 0 ){
38 return a * i;
39 }
40 }
41 }
42 function gcd(a,b){
43 // 最大公约数,用于化简
44 if (a < b){
45 var temp = a;
46 a = b;
47 b = temp;
48 }
49 return (a % b ? gcd(a % b,b):b);
50 }
51
52
53
54
55
2 // 分数类
3 this .n = numerator;
4 this .d = denominator;
5 }
6
7 function fra_add(a,b){
8 // 加法
9 if (a.n == 0 )
10 return b;
11 else if (b.n == 0 )
12 return a;
13 var x = lcm(a.d,b.d);
14 var y = a.n * (x / a.d)+b.n*(x / b.d);
15 var g = gcd(x,y);
16 return new Fraction(y / g,x / g);
17 }
18
19 function fra_mul(a,b){
20 // 乘法
21 var x = a.n * b.n;
22 var y = a.d * b.d;
23 if (x == 0 )
24 return new Fraction( 0 , 1 );
25 var g = gcd(x,y);
26 return new Fraction(x / g,y / g);
27 }
28
29 function lcm(a,b){
30 // 最小公倍数
31 if (a < b){
32 var temp = a;
33 a = b;
34 b = temp;
35 }
36 for ( var i = 1 ;i <= b;i ++ ){
37 if ((a * i) % b == 0 ){
38 return a * i;
39 }
40 }
41 }
42 function gcd(a,b){
43 // 最大公约数,用于化简
44 if (a < b){
45 var temp = a;
46 a = b;
47 b = temp;
48 }
49 return (a % b ? gcd(a % b,b):b);
50 }
51
52
53
54
55
转载于:https://www.cnblogs.com/cmleung/archive/2009/10/29/1591889.html