summaryrefslogtreecommitdiff
path: root/web/funnelAC/contrib
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /web/funnelAC/contrib
Initial commit
Diffstat (limited to 'web/funnelAC/contrib')
-rw-r--r--web/funnelAC/contrib/README36
-rw-r--r--web/funnelAC/contrib/dek.fw264
-rw-r--r--web/funnelAC/contrib/dek2.fw263
-rw-r--r--web/funnelAC/contrib/rand_int.p4
4 files changed, 567 insertions, 0 deletions
diff --git a/web/funnelAC/contrib/README b/web/funnelAC/contrib/README
new file mode 100644
index 0000000000..e34781ccdb
--- /dev/null
+++ b/web/funnelAC/contrib/README
@@ -0,0 +1,36 @@
+Hi ho! Here are some FunnelWeb bits and pieces.
+
+If you are reading this and decide to pick up
+the files in this directory, please send me an email.
+That way I know who is interested.
+
+dek.fw is the FunnelWeb source to a sample program originally
+written in (Pascal) WEB by Don Knuth, and published in CACM.
+
+dek2.fw is the same program, but designed to be processed
+with LaTeX instead of Plain TeX. You'll need fw-latex.sty
+in this directory.
+To do this, use
+ fw dek2 +t
+then remove the first 347 lines of dek2.tex (the Plain TeX
+header) with your editor. (Or maybe say
+ tail +348 dek2.tex > dek2.latex ; mv dek2.latex dek2.tex
+in a Makefile . . . .)
+Then run LaTeX on dek.tex.
+
+Oh, by the way - rand_int.p is the Pascal source for a
+suitable random number generator for use with the program.
+This is Sun-specific!
+To compile (on a Sun), do
+pc -o sample sample.p rand_int.p
+(you'll get a harmless warning).
+
+PLEASE PLEASE PLEASE send me bug reports for fw-latex.sty!
+
+Note that I have only tried to get the Plain TeX functionality
+to work properly - anything extra is up to you.
+
+Richard Walker richard@cs.anu.edu.au
+Department of Computer Science Aust: (06) 249 5687
+The Australian National University Intl: +61 6 249 5687
+GPO Box 4, Canberra, ACT 2601, Australia
diff --git a/web/funnelAC/contrib/dek.fw b/web/funnelAC/contrib/dek.fw
new file mode 100644
index 0000000000..a034f137ec
--- /dev/null
+++ b/web/funnelAC/contrib/dek.fw
@@ -0,0 +1,264 @@
+@p typesetter = tex
+
+% Set your own page size here . . . .
+
+\hsize 160mm
+\vsize 245mm
+
+\def\fwseca#1#2{\fwlibc{#1}{#2}}
+\def\fwsecb#1#2{\fwlibd{#1}{#2}}
+\def\fwsecc#1#2{\fwlibe{#1}{#2}}
+\def\fwsecd#1#2{\fwlibe{#1}{#2}}
+\def\fwsece#1#2{\fwlibe{#1}{#2}}
+
+@t vskip 40 mm
+@t title titlefont centre "A Programming Pearl"
+@t title titlefont centre "Generating sorted random numbers"
+@t vskip 20 mm
+@t title smalltitlefont centre "Don Knuth"
+@t vskip 10 mm
+@t title normalfont centre "FunnelWeb by Richard Walker"
+@t new_page
+@t table_of_contents
+@t new_page
+
+@!------------------------------------------------------------
+@a@<Introduction@>
+
+Jon Bentley recently discussed the following interesting problem
+as one of his `Programming Pearls' [{\sl Communications of the
+ACM 27\/} (December, 1984), 1179--1182]:
+
+The input consists of two integers @{M@} and @{N@}, with @{M@}$<$@{N@}.
+The output is a sorted list of @{M@} random numbers in the range
+1..@{N@} in which no integer occurs more than once. For probability
+buffs, we desire a sorted selection without replacement in which each
+selection occurs equiprobably.
+
+The present program illustrates what I think is the best solution to
+the problem, when @{M@} is reasonably large yet small compared to @{N@}.
+It's the method described tersely in the answer to exercise 3.4.2--15 of
+my book {\sl Seminumerical Algorithms}, pp.~141 and 555.
+
+@!------------------------------------------------------------
+@a@<Some macros@>
+
+For simplicity, all input and output in this program is assumed to be
+handled at the terminal. The @{WEB@} macros @{read_terminal@},
+@{print@}, and @{print_ln@} defined here can easily be changed to
+accommodate other conventions.
+
+Input a value from the terminal.
+@$@<read_terminal@>@(@1@)@M==@{read(@1)@}
+
+Output to the terminal.
+@$@<print@>@(@1@)@M==@{write(@1)@}
+
+Output to the terminal and end the line.
+@$@<print_ln@>@(@1@)@M==@{writeln(@1)@}
+
+@!------------------------------------------------------------
+@a@<An outline of the program@>
+
+Here's an outline of the entire Pascal program:
+
+@o@<sample.p@>==@{@-
+program sample(input,output);
+ var @<Global variables@>
+ @<The random number generation procedure@>
+ begin @<The main program@>;
+ end.
+@}
+
+@!------------------------------------------------------------
+@a@<Global variables@>
+
+The global variables @{M@} and @{N@} have already been mentioned; we had
+better declare them. Other global variables will be declared later.
+
+@{M_max@} is the maximum value of @{M@} allowed in this program.
+@$@<M_max@>@M==@{5000@}
+
+@{2M-1_max@} is $2M-1$ for use later on.
+@$@<2M-1_max@>@M==@{9999@}
+
+@$@<Global variables@>+=@{@-
+M: integer; { size of the sample }
+N: integer; { size of the population }
+@}
+
+@!------------------------------------------------------------
+@a@<Random number generator@>
+
+We assume the existence of a system routine called @{rand_int(i,j)@}
+that returns a random integer chosen uniformly in the range $i..j$.
+
+@$@<The random number generation procedure@>==@{@-
+function rand_int(i,j: integer): integer; external;
+@}
+
+@!------------------------------------------------------------
+@a@<A plan of attack@>
+
+After the user has specified @{M@} and @{N@}, we compute the sample by
+following a general procedure recommended by Bentley:
+
+@$@<The main program@>==@{@-
+@<Establish the values of M and N@>;
+size := 0; @<Initialise set S to empty@>;
+while size < M do
+ begin
+ T := rand_int(1,N);
+ @<If T is not in S, insert it and increase size@>;
+ end;
+@<Print the elements of S in sorted order@>@}
+
+@!------------------------------------------------------------
+@a@<More globals@>
+
+The main program just sketched has introduced several more
+globals. There's a set @{S@} of integers, whose representation
+will be deferred until later; but we can declare two auxiliary
+integer variables now.
+
+@$@<Global variables@>+=@{@-
+size: integer; { the number of elements in set S }
+T: integer; { new candidate for membership in S }
+@}
+
+@!------------------------------------------------------------
+@a
+
+The first order of business is to have a short dialogue with the
+user.
+
+@$@<Establish the values of M and N@>==@{@-
+repeat @<print@>@('population size: N = '@);
+ @<read_terminal@>@(N@);
+ if N <= 0 then
+ @<print_ln@>@('N should be positive!'@);
+until N > 0;
+repeat @<print@>@('sample size: M = '@);
+ @<read_terminal@>@(M@);
+ if M < 0 then
+ @<print_ln@>@('M shouldn''t be negative!'@)
+ else if M > N then
+ @<print_ln@>@('M shouldn''t exceed N!'@)
+ else if M > @<M_max@> then
+ @<print_ln@>@('(Sorry, M must be at most ',@<M_max@>:1,'.)'@);
+until (M >= 0) and (M <= N) and (M <= @<M_max@>)@}
+
+@!------------------------------------------------------------
+@a@<An ordered hash table@>
+
+The key idea to an efficient solution of this sampling problem is
+to maintain a set whose entries are easily sorted. The method of
+`ordered hash tables' [Amble and Knuth, {\sl The Computer Journal
+17\/} (May 1974), 135--142] is ideally suited to this task, as we
+shall see.
+
+Ordered hashing is similar to ordinary linear probing, except that
+the relative order of keys is taken into account. The cited
+paper derives theoretical results that will not be rederived
+here, but we shall use the following fundamental property: {\sl
+The entries of an ordered hash table are independent of the order
+in which its keys were inserted}. Thus, an ordered hash table is
+a `canonical' representation of its set of entries.
+
+We shall represent @{S@} by an array of $2M$ integers. Since
+Pascal doesn't permit arrays of variable size, we must leave room
+for the largest possible table.
+
+@$@<Global variables@>+=@{@-
+hash: array[0..@<2M-1_max@>] of integer;
+ { the ordered hash table }
+H: 0..@<2M-1_max@>; { an index into hash }
+H_max: 0..@<2M-1_max@>; { the current hash size }
+alpha: real; { the ratio of table size to N }
+@}
+
+@!------------------------------------------------------------
+@a
+
+@$@<Initialise set S to empty@>==@{@-
+H_max := 2 * M - 1; alpha := 2 * M / N;
+for H := 0 to H_max do hash[H] := 0@}
+
+@!------------------------------------------------------------
+@a
+
+Now we come to the interesting part, where the algorithm tries to
+insert @{T@} into an ordered hash table. The hash address
+$H=\lfloor2M(T-1)/N\rfloor$ is used as a starting point, since
+this quantity is monotonic in @{T@} and almost uniformly
+distributed in the range $0\le H<2M$.
+
+@$@<If T is not in S, insert it and increase size@>==@{@-
+H := trunc(alpha * (T-1));
+while hash[H] > T do
+ if H = 0 then H := H_max else H := H-1;
+if hash[H] < T then { T is not present }
+ begin size := size + 1;
+ @<Insert T into the ordered hash table@>;
+ end@}
+
+@!------------------------------------------------------------
+
+The heart of ordered hashing is the insertion process. In general,
+the new key @{T@} will be inserted in place of a previous key $T_1<T$,
+which is then re-inserted in place of $T_2<T_1$, etc., until an empty
+slot is discovered.
+
+@$@<Insert T into the ordered hash table@>==@{@-
+while hash[H] > 0 do
+ begin TT := hash[H]; { we have 0 < TT < T }
+ hash[H] := T; T := TT;
+ repeat if H = 0 then H := H_max
+ else H := H - 1;
+ until hash[H] < T;
+end;
+hash[H] := T@}
+
+@!------------------------------------------------------------
+@a
+
+@$@<Global variables@>+=@{@-
+TT: integer; { a key that's being moved }
+@}
+
+@!------------------------------------------------------------
+@a@<Sorting in linear time@>
+
+The climax of this program is the fact that the entries in our ordered
+hash table can easily be read out in increasing order.
+
+Why is this true? Well, we know that the final state of the table is
+independent of the order in which the elements entered. Furthermore
+it's easy to understand what the table looks like when the entries are
+inserted in decreasing order, because we have used a monotonic hash
+function. Therefore we know that the table must have an especially
+simple form.
+
+Suppose the nonzero entries are $T_1<\cdots<T_M$. If $k$ of these
+have `wrapped around' in the insertion process (i.e., if @{H@} passed
+from 0 to @{H\_max@}, $k$ times), table position @{hash[0]@} will
+either be zero (in which case $k$ must also be zero) or it will
+contain $T_{k+1}$. In the latter case, the entries
+$T_{k+1}<\cdots<T_M$ and $T_1<\cdots<T_k$ will appear in order from
+left to right. Thus the output can be sorted with at most two passes
+over the table!
+
+@$@<print_it@>@M==@{@<print_ln@>@(hash[H] : 10@)@}
+
+@$@<Print the elements of S in sorted order@>==@{@-
+if hash[0] = 0 then { there was no wrap-around }
+ begin for H := 1 to H_max do
+ if hash[H] > 0 then @<print_it@>;
+ end
+else begin for H := 1 to H_max do
+ { print the wrapped-around entries }
+ if hash[H] > 0 then
+ if hash[H] < hash[0] then @<print_it@>;
+ for H := 0 to H_max do
+ if hash[H] >= hash[0] then @<print_it@>;
+ end@}
diff --git a/web/funnelAC/contrib/dek2.fw b/web/funnelAC/contrib/dek2.fw
new file mode 100644
index 0000000000..0e7385dbf0
--- /dev/null
+++ b/web/funnelAC/contrib/dek2.fw
@@ -0,0 +1,263 @@
+@p typesetter = tex
+
+% Use a4 if you have A4 paper. If you're in the US you probably want
+% to take it out . . . .
+
+\documentstyle[fw-latex,a4]{article}
+
+\begin{document}
+
+% Just to show that it all works in LaTeX . . . .
+@t vskip 40 mm
+@t title titlefont centre "A Programming Pearl"
+@t title titlefont centre "Generating sorted random numbers"
+@t vskip 20 mm
+@t title smalltitlefont centre "Don Knuth"
+@t vskip 10 mm
+@t title normalfont centre "FunnelWeb by Richard Walker"
+@t new_page
+\tableofcontents % . . . BUT use LaTeX's table of contents.
+@t new_page
+
+@!------------------------------------------------------------
+@a@<Introduction@>
+
+Jon Bentley recently discussed the following interesting problem
+as one of his `Programming Pearls' [{\sl Communications of the
+ACM 27\/} (December, 1984), 1179--1182]:
+
+The input consists of two integers @{M@} and @{N@}, with @{M@}$<$@{N@}.
+The output is a sorted list of @{M@} random numbers in the range
+1..@{N@} in which no integer occurs more than once. For probability
+buffs, we desire a sorted selection without replacement in which each
+selection occurs equiprobably.
+
+The present program illustrates what I think is the best solution to
+the problem, when @{M@} is reasonably large yet small compared to @{N@}.
+It's the method described tersely in the answer to exercise 3.4.2--15 of
+my book {\sl Seminumerical Algorithms}, pp.~141 and 555.
+
+@!------------------------------------------------------------
+@a@<Some macros@>
+
+For simplicity, all input and output in this program is assumed to be
+handled at the terminal. The @{WEB@} macros @{read_terminal@},
+@{print@}, and @{print_ln@} defined here can easily be changed to
+accommodate other conventions.
+
+Input a value from the terminal.
+@$@<read_terminal@>@(@1@)@M==@{read(@1)@}
+
+Output to the terminal.
+@$@<print@>@(@1@)@M==@{write(@1)@}
+
+Output to the terminal and end the line.
+@$@<print_ln@>@(@1@)@M==@{writeln(@1)@}
+
+@!------------------------------------------------------------
+@a@<An outline of the program@>
+
+Here's an outline of the entire Pascal program:
+
+@o@<sample.p@>==@{@-
+program sample(input,output);
+ var @<Global variables@>
+ @<The random number generation procedure@>
+ begin @<The main program@>;
+ end.
+@}
+
+@!------------------------------------------------------------
+@a@<Global variables@>
+
+The global variables @{M@} and @{N@} have already been mentioned; we had
+better declare them. Other global variables will be declared later.
+
+@{M_max@} is the maximum value of @{M@} allowed in this program.
+@$@<M_max@>@M==@{5000@}
+
+@{2M-1_max@} is $2M-1$ for use later on.
+@$@<2M-1_max@>@M==@{9999@}
+
+@$@<Global variables@>+=@{@-
+M: integer; { size of the sample }
+N: integer; { size of the population }
+@}
+
+@!------------------------------------------------------------
+@a@<Random number generator@>
+
+We assume the existence of a system routine called @{rand_int(i,j)@}
+that returns a random integer chosen uniformly in the range $i..j$.
+
+@$@<The random number generation procedure@>==@{@-
+function rand_int(i,j: integer): integer; external;
+@}
+
+@!------------------------------------------------------------
+@a@<A plan of attack@>
+
+After the user has specified @{M@} and @{N@}, we compute the sample by
+following a general procedure recommended by Bentley:
+
+@$@<The main program@>==@{@-
+@<Establish the values of M and N@>;
+size := 0; @<Initialise set S to empty@>;
+while size < M do
+ begin
+ T := rand_int(1,N);
+ @<If T is not in S, insert it and increase size@>;
+ end;
+@<Print the elements of S in sorted order@>@}
+
+@!------------------------------------------------------------
+@a@<More globals@>
+
+The main program just sketched has introduced several more
+globals. There's a set @{S@} of integers, whose representation
+will be deferred until later; but we can declare two auxiliary
+integer variables now.
+
+@$@<Global variables@>+=@{@-
+size: integer; { the number of elements in set S }
+T: integer; { new candidate for membership in S }
+@}
+
+@!------------------------------------------------------------
+@a
+
+The first order of business is to have a short dialogue with the
+user.
+
+@$@<Establish the values of M and N@>==@{@-
+repeat @<print@>@('population size: N = '@);
+ @<read_terminal@>@(N@);
+ if N <= 0 then
+ @<print_ln@>@('N should be positive!'@);
+until N > 0;
+repeat @<print@>@('sample size: M = '@);
+ @<read_terminal@>@(M@);
+ if M < 0 then
+ @<print_ln@>@('M shouldn''t be negative!'@)
+ else if M > N then
+ @<print_ln@>@('M shouldn''t exceed N!'@)
+ else if M > @<M_max@> then
+ @<print_ln@>@('(Sorry, M must be at most ',@<M_max@>:1,'.)'@);
+until (M >= 0) and (M <= N) and (M <= @<M_max@>)@}
+
+@!------------------------------------------------------------
+@a@<An ordered hash table@>
+
+The key idea to an efficient solution of this sampling problem is
+to maintain a set whose entries are easily sorted. The method of
+`ordered hash tables' [Amble and Knuth, {\sl The Computer Journal
+17\/} (May 1974), 135--142] is ideally suited to this task, as we
+shall see.
+
+Ordered hashing is similar to ordinary linear probing, except that
+the relative order of keys is taken into account. The cited
+paper derives theoretical results that will not be rederived
+here, but we shall use the following fundamental property: {\sl
+The entries of an ordered hash table are independent of the order
+in which its keys were inserted}. Thus, an ordered hash table is
+a `canonical' representation of its set of entries.
+
+We shall represent @{S@} by an array of $2M$ integers. Since
+Pascal doesn't permit arrays of variable size, we must leave room
+for the largest possible table.
+
+@$@<Global variables@>+=@{@-
+hash: array[0..@<2M-1_max@>] of integer;
+ { the ordered hash table }
+H: 0..@<2M-1_max@>; { an index into hash }
+H_max: 0..@<2M-1_max@>; { the current hash size }
+alpha: real; { the ratio of table size to N }
+@}
+
+@!------------------------------------------------------------
+@a
+
+@$@<Initialise set S to empty@>==@{@-
+H_max := 2 * M - 1; alpha := 2 * M / N;
+for H := 0 to H_max do hash[H] := 0@}
+
+@!------------------------------------------------------------
+@a
+
+Now we come to the interesting part, where the algorithm tries to
+insert @{T@} into an ordered hash table. The hash address
+$H=\lfloor2M(T-1)/N\rfloor$ is used as a starting point, since
+this quantity is monotonic in @{T@} and almost uniformly
+distributed in the range $0\le H<2M$.
+
+@$@<If T is not in S, insert it and increase size@>==@{@-
+H := trunc(alpha * (T-1));
+while hash[H] > T do
+ if H = 0 then H := H_max else H := H-1;
+if hash[H] < T then { T is not present }
+ begin size := size + 1;
+ @<Insert T into the ordered hash table@>;
+ end@}
+
+@!------------------------------------------------------------
+
+The heart of ordered hashing is the insertion process. In general,
+the new key @{T@} will be inserted in place of a previous key $T_1<T$,
+which is then re-inserted in place of $T_2<T_1$, etc., until an empty
+slot is discovered.
+
+@$@<Insert T into the ordered hash table@>==@{@-
+while hash[H] > 0 do
+ begin TT := hash[H]; { we have 0 < TT < T }
+ hash[H] := T; T := TT;
+ repeat if H = 0 then H := H_max
+ else H := H - 1;
+ until hash[H] < T;
+end;
+hash[H] := T@}
+
+@!------------------------------------------------------------
+@a
+
+@$@<Global variables@>+=@{@-
+TT: integer; { a key that's being moved }
+@}
+
+@!------------------------------------------------------------
+@a@<Sorting in linear time@>
+
+The climax of this program is the fact that the entries in our ordered
+hash table can easily be read out in increasing order.
+
+Why is this true? Well, we know that the final state of the table is
+independent of the order in which the elements entered. Furthermore
+it's easy to understand what the table looks like when the entries are
+inserted in decreasing order, because we have used a monotonic hash
+function. Therefore we know that the table must have an especially
+simple form.
+
+Suppose the nonzero entries are $T_1<\cdots<T_M$. If $k$ of these
+have `wrapped around' in the insertion process (i.e., if @{H@} passed
+from 0 to @{H\_max@}, $k$ times), table position @{hash[0]@} will
+either be zero (in which case $k$ must also be zero) or it will
+contain $T_{k+1}$. In the latter case, the entries
+$T_{k+1}<\cdots<T_M$ and $T_1<\cdots<T_k$ will appear in order from
+left to right. Thus the output can be sorted with at most two passes
+over the table!
+
+@$@<print_it@>@M==@{@<print_ln@>@(hash[H] : 10@)@}
+
+@$@<Print the elements of S in sorted order@>==@{@-
+if hash[0] = 0 then { there was no wrap-around }
+ begin for H := 1 to H_max do
+ if hash[H] > 0 then @<print_it@>;
+ end
+else begin for H := 1 to H_max do
+ { print the wrapped-around entries }
+ if hash[H] > 0 then
+ if hash[H] < hash[0] then @<print_it@>;
+ for H := 0 to H_max do
+ if hash[H] >= hash[0] then @<print_it@>;
+ end@}
+
+\end{document}
diff --git a/web/funnelAC/contrib/rand_int.p b/web/funnelAC/contrib/rand_int.p
new file mode 100644
index 0000000000..0d836e30b1
--- /dev/null
+++ b/web/funnelAC/contrib/rand_int.p
@@ -0,0 +1,4 @@
+function rand_int(i,j: integer): integer;
+begin
+ rand_int := trunc(random(1)*(j-i+2)+i-1);
+end;