1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: public class FactorialSwingRational implements IFactorialFunction
6: {
7:
8: private long D, N, h;
9: private int i;
10:
11: public FactorialSwingRational()
12: {
13: }
14:
15: public String getName()
16: {
17: return "SwingRational ";
18: }
19:
20: public Xint factorial(int n)
21: {
22: if (n < 0)
23: {
24: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
25: }
26:
27: return recFactorial(n);
28: }
29:
30: private Xint recFactorial(int n)
31: {
32: if (n < 2)
33: {
34: return Xint.ONE;
35: }
36:
37: return recFactorial(n / 2).square().multiply(swing(n));
38: }
39:
40: private Xint swing(int n)
41: {
42: switch (n % 4)
43: {
44: case 1:
45: h = n / 2 + 1;
46: break;
47: case 2:
48: h = 2;
49: break;
50: case 3:
51: h = 2 * (n / 2 + 2);
52: break;
53: default:
54: h = 1;
55: break;
56: }
57:
58: N = 2 * (n + 2 - ((n + 1) & 1));
59: D = 1;
60: i = n / 4;
61:
62: return product(i + 1).getNumerator();
63: }
64:
65: private Rational product(int l)
66: {
67: if (l > 1)
68: {
69: int m = l / 2;
70: return product(m).multiply(product(l - m));
71: }
72:
73: if (i-- > 0)
74: {
75: return new Rational(N -= 4, D++);
76: }
77:
78: return new Rational(h, 1);
79: }
80:
81: // --------------------------------------------------------
82: // A minimalistic rational arithmetic *only* for the use of
83: // FactorialSwingRational. The sole purpose for inclusion
84:
85: // here is to make the description of the algorithm more
86: // independent and more easy to port.
87: // ---------------------------------------------------------
88: private class Rational
89: {
90:
91: private Xint num; // Numerator
92: private Xint den; // Denominator
93:
94: public Xint getNumerator()
95: {
96: Xint cd = num.gcd(den);
97: return num.divide(cd);
98: }
99:
100: public Rational(long _num, long _den)
101: {
102: long g = gcd(_num, _den);
103: num = Xint.valueOf(_num / g);
104: den = Xint.valueOf(_den / g);
105: }
106:
107: public Rational(Xint _num, Xint _den)
108: {
109: // If the arithmetic supports a *real* fast gcd
110: // this would lead to a speed up:
111: // Xint cd = _num.gcd(_den);
112: // num = _num.divide(cd);
113: // den = _den.divide(cd);
114: num = _num;
115: den = _den;
116: }
117:
118: public Rational multiply(Rational r)
119: {
120: return new Rational(num.multiply(r.num), den.multiply(r.den));
121: }
122:
123: private long gcd(long a, long b)
124: {
125: long x, y;
126:
127: if (a >= b)
128: {
129: x = a;
130: y = b;
131: }
132: else
133: {
134: x = b;
135: y = a;
136: }
137:
138: while (y != 0)
139: {
140: long t = x % y;
141: x = y;
142: y = t;
143: }
144: return x;
145: }
146: } // endOfRational
147: } // endOfSwingRational