@^Steinerberger, Stefan@>
@^Gibbs, Philip Edward@>
Of course I couldn't resist translating it from Java into \.{CWEB},
because that's what I do for a living. So this is the result.
@ This program has lots of tunable parameters, and it should prove
to be interesting to see how they affect the performance. Of course
the main parameter is $N$, the desired number of outputs. Other options
are preceded on the command line by a letter; for example,
`\.{v5}' sets the verboseness parameter to~5.
Each parameter will
be explained later, but it's convenient to summarize the option letters here:
\smallskip
\item{$\bullet$}
`\.v$\langle\,$integer$\,\rangle$' to enable various binary-coded
levels of verbose output on |stderr| (default=1).
\item{$\bullet$}
`\.p$\langle\,$positive integer$\,\rangle$' to specify the numerator
of a rational approximation to~$\lambda$ (default=120500181).
\item{$\bullet$}
`\.q$\langle\,$positive integer$\,\rangle$' to specify the denominator
of a rational approximation to~$\lambda$ (default=49315733). The program
assumes that $p$ and $q$ are less than $2^{32}$, and that $22198412$.)
\item{$\bullet$}
`\.B$\langle\,$positive integer$\,\rangle$' to specify the number
of initial |is_ulam| entries that are encoded with one bit per byte
(default=18000). This value should be a multiple of the \.b option,
and at least~3.
\item{$\bullet$}
`\.w$\langle\,$positive integer$\,\rangle$' to specify the window size
for remembering recently computed Ulam numbers (default=1000000).
The window size must be at least~3.
\item{$\bullet$}
`\.M$\langle\,$filename$\,\rangle$' to produce \MP\ illustrations
showing the distributions of Ulam numbers and Ulam misses, modulo~$\lambda$.
@ The |vbose| parameter is the sum of the following binary codes.
To enable everything, you can say `\.{v-1}'.
@d show_usage_stats 1 /* reports time and space usage */
@d show_compression_stats 2 /* reports details of |is_ulam| encoding */
@d show_histograms 4 /* reports Ulams and misses mod $\lambda$ */
@d show_gap_stats 8 /* gives histogram and examples of every gap */
@d show_record_gaps 16 /* reports every gap that exceeded all predecessors */
@d show_record_outliers 32 /* reports outliers that exceeded earlier ones */
@d show_outlier_details 64 /* reports insertion or deletion of all outliers */
@d show_record_cutoffs 128 /* reports residue cutoffs for near outliers */
@d show_omitted_inliers 256 /* reports inliers that aren't near outliers */
@d show_brute_winners 512 /* reports unusual cases after brute-force trials */
@d show_inlier_anchors 1024 /* reports cases when two inliers make Ulam */
@ Here then is an outline of the whole program:
@d o mems++ /* count one mem (one access to or from 64 bits of memory) */
@d oo mems+=2 /* count two mems */
@d ooo mems+=3 /* count three mems */
@d O "%" /* used for percent signs in format strings */
@d mod % /* used for percent signs denoting remainder in \CEE/ */
@c
#include
#include
#include
typedef unsigned char uchar; /* a convenient abbreviation */
typedef unsigned int uint; /* ditto */
typedef unsigned long long ullng; /* ditto */
@@;
@@;
@@;
main (int argc,char*argv[]) {
register int i,j,k,r,rp,t,x,y,hits,count;
register ullng n,u,up;
@;
@;
@;
for (u=3;n;
if (mp_file) @