-
Notifications
You must be signed in to change notification settings - Fork 5
/
pearls.html
307 lines (279 loc) · 10.1 KB
/
pearls.html
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
<HTML>
<HEAD>
<TITLE>Programming Pearls</TITLE>
</HEAD>
<BODY>
<H1><IMG ALT="[picture of a maze]" ALIGN=top SRC="img/maze.gif">
Programming Pearls</H1>
My favourite
<A HREF="http://www.uwsg.iu.edu/usail/library/humor/tao.of.programming.html">programming</A>
language by far is <A HREF="http://haskell.org/">Haskell</A>.
Sometimes, when I have a big need for speed, I might fall back on
<A HREF="http://www.lysator.liu.se/c/index.html">C</A>
(or <A HREF="http://java.sun.com/">C++</A> for better data structures
and saner memory management while putting up with all its ugly warts).
After my very first programming language,
<A HREF="http://www.earth.ox.ac.uk/~steve/Spectrum/">Sinclair</A>
BASIC, Z80 assembly next, and Pascal as freshman in University,
C made a refreshing change. Behold the
<A HREF="http://www.lysator.liu.se/c/ten-commandments.html">
Ten Commandments for C Programmers</A>.
Also see Frans Faase's list of
<A HREF="http://www.iwriteiam.nl/SigProg.html">signature programs</A>.
<H1>A Space Filling Program</H1>
<PRE>
p(c){putchar( c);}f(x,y,m){
(y=m- abs(m -y))- m&&m-
x?f(x <m?y:x&m,x<m? x:y,m
/2):p (x-m-
1&&y?32:64);} main(z){for(z
=N*N; z--;p
(z%N?32:10))f (z%N,z/N,N);}
</PRE>
<p>
compiles with -DN=1, -DN=3, -DN=7, or -DN=15 (powers of two minus one) to produce outputs
<p>
<TABLE><TR valign="bottom"><TD>
<PRE>
@
</PRE>
</TD><TD> </TD><TD>
<PRE>
@ @ @
@ @
@ @
</PRE>
</TD><TD> </TD><TD>
<PRE>
@ @ @ @ @ @
@ @ @ @
@ @ @ @ @
@ @
@ @ @ @ @ @
@ @
@ @ @ @ @ @
</PRE>
</TD><TD> </TD><TD>
<PRE>
@ @ @ @ @ @ @ @ @ @ @ @
@ @ @ @ @ @ @ @
@ @ @ @ @ @ @ @ @ @
@ @ @ @
@ @ @ @ @ @ @ @ @ @ @ @
@ @ @ @
@ @ @ @ @ @ @ @ @ @ @ @ @
@ @
@ @ @ @ @ @ @ @ @ @ @ @
@ @ @ @ @ @
@ @ @ @ @ @ @ @ @ @ @ @
@ @
@ @ @ @ @ @ @ @ @ @ @ @
@ @ @ @ @ @
@ @ @ @ @ @ @ @ @ @ @ @
</PRE>
</TD></TR></TABLE>
This improved version (inspired by <a href="http://golf.shinh.org/p.rb?Hilbert+Curve+FIXED">nu's codegolf entry</a>)
<PRE>
f(y,x,m){return x?x=abs(~m+x),y
>m?-f (x,y, m):x& m?f(y
,x,m/ 2):m==y&y:-2; }main
(y,x) {for(
x=0;N/y;)y+=20/ putchar("\n| _"
[++x& !f(y+
1,x&N,N)|f(y-x %2,x&N,N)+2]);}
</PRE>
produces prettier output (with N=3,7,15,31):
<p>
<TABLE><TR valign="bottom"><TD>
</TD><TD> </TD><TD>
<PRE>
_
| |
</PRE>
</TD><TD> </TD><TD>
<PRE>
_ _
| |_| |
|_ _|
_| |__
</PRE>
</TD><TD> </TD><TD>
<PRE>
_ _ _ _
| |_| | | |_| |
|_ _| |_ _|
_| |_____| |_
| ___ ___ |
|_| _| |_ |_|
_ |_ _| _
| |___| |___| |
</PRE>
</TD><TD> </TD><TD>
<PRE>
_ _ _ _ _ _ _ _
| |_| | | |_| | | |_| | | |_| |
|_ _| |_ _| |_ _| |_ _|
_| |_____| |_ _| |_____| |_
| ___ ___ | | ___ ___ |
|_| _| |_ |_| |_| _| |_ |_|
_ |_ _| _ _ |_ _| _
| |___| |___| |_| |___| |___| |
|_ ___ ___ ___ ___ _|
_| |_ |_| _| |_ |_| _| |_
| _ | _ |_ _| _ | _ |
|_| |_| | |___| |___| | |_| |_|
_ _ | ___ ___ | _ _
| |_| | |_| _| |_ |_| | |_| |
|_ _| _ |_ _| _ |_ _|
_| |___| |___| |___| |___| |__
</PRE>
</TD></TR></TABLE>
<a name="maze"></a>
<H1>Amazing</H1>
This is my favourite programming pearl, a 237 character program that
generates
<A HREF="http://www.astrolog.org/labyrnth.htm">mazes</A>
of arbitrary length. It was my 1988 submission to the
<A HREF="http://www.ioccc.org/">
International Obfuscated C Code Contest</A>.
<PRE>
char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
-- E; J[ E] =T
[E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|"
) , A = 39 ,C --
) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C
& A == T[ A]
|6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}
</PRE>
Note that the constant 27 assumes a 31-bit random number generator,
and needs to be replaced with 11 if <TT>rand()</TT> produces 15-bit numbers
instead. Modern C compilers don't allow constant strings to be overwritten,
which can be avoided by changing the first line to
<PRE>
char M[3],A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf("%d",&C);
</PRE>
If you want to know how this program achieves its mystery, read
<A HREF="maze.html">this</A>.
<H1>Tetris</H1>
In 1989, in collaboration with my friend
<A HREF="http://www.cs.kun.nl/~freek/">Freek Wiedijk</A>,
I submitted a 1467 character <A HREF="tetris.html">tetris</A>
program, which won the Best Game category.
<H1>A heap of sorts</H1>
The following C-code sorts integers t[1]...t[j] in ascending order:
<PRE>
for (i = j/2; j > 1; t[l] = k) {
if (i) k = t[i--]; else { k = t[j]; t[j--] = t[1]; }
for (l = i + 1; (m = l + l) <= j; t[l] = t[m], l = m) {
if (m < j && t[m] < t[m+1]) m++;
if (t[m] <= k) break;
}
}
</PRE>
<H1>Hanoi revisited</H1>
Some problems, which are presented in algorithm textbooks as ideal candidates
for recursion, turn out to be much better suited to iteration:
<PRE>
max = 1 << no_of_discs;
for (x = 1; x < max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
</PRE>
<a name="goodstein"></a>
<H1>How fast can you grow?</H1>
Here's a one line Haskell-script that computes a <STRONG>very</STRONG> fast growing
function. It was introduced by
<a href="http://en.wikipedia.org/wiki/Reuben_Goodstein">R. L. Goodstein</a>
as an example of a function
that is total (i.e. defined on any input), although this fact is not provable
in first-order Peano Arithmetic!
(see also this <a href="http://en.wikipedia.org/wiki/Goodstein's_theorem">Wikipedia entry</a> including a proof).
<PRE>
main=mapM_(print.gs)[0..]where
gs=g 2
g b 0=b;g b n=g c$s 0 n-1where s _ 0=0;s e n=mod n b*c^s 0 e+s(e+1)(div n b);c=b+1
</PRE>
The values gs(0)=2,gs(1)=3,gs(2)=5,gs(3)=7 seem pretty modest
and in fact suspiciously familiar. <P>
But the function really takes off at gs(4)=3 * 2^402653211 - 1,
which is the
<a href="http://primes.utm.edu/glossary/page.php?sort=WoodallNumber">
Woodall number</a> W<sub>402653184</sub>, divisible by 29.
<BR>
Here's a Postscript picture showing how values <a href="img/goodstein.eps">grow as a function of the base</a> for this Goodstein sequence (all bigger ones
look the same, only differing in scale).
<P>
A more legible representation of function g is
<PRE>
g b 0 = b
g b n = g c ((s 0 n) - 1) where
s _ 0 = 0
s e n = (n `mod` b) * c^(s 0 e) + (s (e + 1) (n `div` b))
c = b + 1
</PRE>
Small values of gs() can be expressed in terms of a close analogue
of <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackerman's function</a>,
the finite part of this <a href="http://en.wikipedia.org/wiki/Fast-growing_hierarchy#Definition">fast-growing hierarchy</a>:
<p>f<sub>0</sub>(n)=n+1
<br> f<sub>k+1</sub>(n)=f<sub>k</sub><sup>n</sup>(n).
<p>
Then gs(4)=f<sub>3</sub>(3)-1,
gs(5)=f<sub>4</sub>(4)-1, gs(6)=f<sub>6</sub>(6)-1 and gs(7)=f<sub>8</sub>(8)-1.
<a name="sieve"></a>
<H1>A compact prime sieve</H1>
<PRE>
#include <stdio.h>
#include <stdlib.h>
#define DO(P,R,I,M,E,S,i0,v0,i1,v1,i2,v2,i3,v3,i4,v4,i5,v5,i6,v6,i7,v7) k=P;\
if (!(sieve[n] & (1<<R)))\
{ printf(" %ld",30*n + bits[R]);\
e = eos - I*n - M;\
for (m = sieve + (30*n + E) * n + S; m < e; m += i0)\
{ *m |= (1<<v0); *(m += i1) |= (1<<v1);\
*(m +=i2) |= (1<<v2); *(m += i3) |= (1<<v3);\
*(m +=i4) |= (1<<v4); *(m += i5) |= (1<<v5);\
*(m +=i6) |= (1<<v6); *(m += i7) |= (1<<v7);\
}\
if (m < eos) { *m|=(1<<v0);\
if ((m += i1) < eos) { *m |= (1<<v1);\
if ((m += i2) < eos) { *m |= (1<<v2);\
if ((m += i3) < eos) { *m |= (1<<v3);\
if ((m += i4) < eos) { *m |= (1<<v4);\
if ((m += i5) < eos) { *m |= (1<<v5);\
if ((m += i6) < eos) *m |= (1<<v6);\
} } } } } } }
char bits[] = {1,7,11,13,17,19,23,29} ;
int main(int argc, char *argv[])
{
unsigned long p,q,r,k=0,n,s;
char *m,*e,*eos,*sieve;
long bytes,atol();
if (argc!=2) printf("usage: %s (<bytes_used> or -<maxprime>)\n",*argv), exit(0);
if ((bytes=atol(argv[1])) < 0) bytes = 1 + (-bytes)/30;
if (!(sieve = calloc(bytes,1))) printf("Out of memory.\n"), exit(0);
if (bytes > 30) for (k = r = (bytes-1)/30; (q = r/k) < k; k >>= 1) k += q;
eos = sieve + bytes; s = k + 1; *sieve = 1; printf("2 3 5");
for (n = p = q = r = 0; n < s; n++)
{ DO(p++,0,28, 0, 2, 0,p,0,r,1,q,2,k,3,q,4,k,5,q,6,r,7); r++;
DO(q++,1,24, 6,14, 1,r,5,q,4,p,0,k,7,p,3,q,2,r,6,p,1); r++; q++;
DO(p-1,2,26, 9,22, 4,q,0,k,6,q,1,k,7,q,3,r,5,p,2,r,4); r++;
DO(q-1,3,28,12,26, 5,p,5,q,2,p,1,k,7,r,4,p,3,r,0,k,6);
DO(q+1,4,26,15,34, 9,q,5,p,6,k,0,r,3,p,4,r,7,k,1,p,2); r++;
DO(p+1,5,28,17,38,12,k,0,q,4,r,2,p,5,r,3,q,7,k,1,q,6); r++; q++;
DO(q++,6,26,20,46,17,k,5,r,1,p,6,r,2,k,3,p,7,q,0,p,4); r++;
DO(p++,7,24,23,58,28,r,0,k,7,r,6,q,5,p,4,q,3,p,2,q,1);
}
printf(" ...");
for (p = bytes - s; p < bytes; p++)
for (k = 0; k < 8; k++)
if (!(sieve[p] & (1<<k))) printf(" %ld",30 * p + bits[k]);
for (p = 0, n=3; p < bytes; p++)
for (k = 0; k < 8; k++) n += !(sieve[p] & (1<<k));
printf("\n%ld primes found\n", n);
exit(0);
}
</PRE>
<HR>
Back to my <A HREF="http://tromp.github.io">home page</A>. <BR>
<a href="mailto:[email protected]">[email protected]</a>
</BODY>
</HTML>