1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
/* The Great Computer Language Shootout
http://shootout.alioth.debian.org/
contributed by Isaac Gouy
*/
import java.math.BigInteger;
public class pidigits {
static final int L = 10;
public static void main(String args[]) {
int n = Integer.parseInt(args[0]);
int j = 0;
PiDigitSpigot digits = new PiDigitSpigot();
while (n > 0){
if (n >= L){
for (int i=0; i<L; i++) System.out.print( digits.next() );
j += L;
} else {
for (int i=0; i<n; i++) System.out.print( digits.next() );
for (int i=n; i<L; i++) System.out.print(" ");
j += n;
}
System.out.print("\t:"); System.out.println(j);
n -= L;
}
}
}
class PiDigitSpigot {
Transformation z, x, inverse;
public PiDigitSpigot(){
z = new Transformation(1,0,0,1);
x = new Transformation(0,0,0,0);
inverse = new Transformation(0,0,0,0);
}
public int next(){
int y = digit();
if (isSafe(y)){
z = produce(y); return y;
} else {
z = consume( x.next() ); return next();
}
}
public int digit(){
return z.extract(3);
}
public boolean isSafe(int digit){
return digit == z.extract(4);
}
public Transformation produce(int i){
return ( inverse.qrst(10,-10*i,0,1) ).compose(z);
}
public Transformation consume(Transformation a){
return z.compose(a);
}
}
class Transformation {
BigInteger q, r, s, t;
int k;
public Transformation(int q, int r, int s, int t){
this.q = BigInteger.valueOf(q);
this.r = BigInteger.valueOf(r);
this.s = BigInteger.valueOf(s);
this.t = BigInteger.valueOf(t);
k = 0;
}
public Transformation(BigInteger q, BigInteger r, BigInteger s, BigInteger t){
this.q = q;
this.r = r;
this.s = s;
this.t = t;
k = 0;
}
public Transformation next(){
k++;
q = BigInteger.valueOf(k);
r = BigInteger.valueOf(4 * k + 2);
s = BigInteger.valueOf(0);
t = BigInteger.valueOf(2 * k + 1);
return this;
}
public int extract(int j){
BigInteger bigj = BigInteger.valueOf(j);
BigInteger numerator = (q.multiply(bigj)).add(r);
BigInteger denominator = (s.multiply(bigj)).add(t);
return ( numerator.divide(denominator) ).intValue();
}
public Transformation qrst(int q, int r, int s, int t){
this.q = BigInteger.valueOf(q);
this.r = BigInteger.valueOf(r);
this.s = BigInteger.valueOf(s);
this.t = BigInteger.valueOf(t);
k = 0;
return this;
}
public Transformation compose(Transformation a){
return new Transformation(
q.multiply(a.q)
,(q.multiply(a.r)).add( (r.multiply(a.t)) )
,(s.multiply(a.q)).add( (t.multiply(a.s)) )
,(s.multiply(a.r)).add( (t.multiply(a.t)) )
);
}
}
|
