D. J. Bernstein

Integer factorization

# Psibound

Psibound quickly computes lower and upper bounds on
the distribution of smooth integers.
I have a
paper
explaining the method.
## Installation

The current version of
Psibound requires an x86 machine,
such as a Pentium III or (for better speed) an Athlon.
It will not compile on non-x86 machines.
Download
primegen-0.97.tar.gz,
zpfft-0.50.tar.gz,
and
psibound-0.50.tar.gz
in the same directory.
Compile everything as follows:

gunzip < primegen-0.97.tar.gz | tar -xf -
( cd primegen-0.97; make )
gunzip < zpfft-0.50.tar.gz | tar -xf -
( cd zpfft-0.50; make )
gunzip < psibound-0.50.tar.gz | tar -xf -
cd psibound-0.50
make

## Execution

For lower bounds and upper bounds on the distribution of 1000-smooth integers:
./psibound 1000 0 > 1000.0
./psibound 1000 1 > 1000.1

The current `psibound` program
takes roughly 35 billion Pentium-II cycles,
i.e., 100 seconds on a Pentium II-350,
using 38 megabytes of memory,
to produce 10 megabytes of output.
The output file `1000.0` contains 262144 lines
showing lower bounds on Psi(x,1000) for various values of x.
For example, the line

232800 776 3316969875331297976743493363095454174822048

says that Psi(2^(232800/776),1000) is at least 3.31696*10^42.
The output file `1000.1` contains 262144 lines
showing upper bounds;
for example,
231300 771 3352333995371428390153438494245232797204720

says that Psi(2^(231300/771),1000) is at most 3.35234*10^42.
You can feed the output of `psibound` through

./rho 1000

to obtain lines such as
2.037036e+90 1.000000e+03 3.010300e+01 1.945013e-50 1.645692e-48 84.610837

showing the first input to Psi,
the second input to Psi,
the ratio of the logs of the inputs,
Dickman's rho function evaluated at that ratio,
the approximate Psi output divided by the floor of the first input,
and the ratio between the approximate Psi output and
Dickman's rho function times the floor of the first input.