####################################################################
# README file for quart
# Authors: Andreas-Stephan Elsenhans and Joerg Jahnel
#   Email: elsenhan@uni-math.gwdg.de, jahnel@uni-math.gwdg.de
#   Web:   http://www.gwdg.de/jahnel
# Date: 2006-08-25
####################################################################

BE ALERT: This code ASSUMES that a "long int" is a 64-bit integer.
          On 32-bit machines it is highly unlikely to run properly.

          Compilation with the WITH_PREFETCH option (set in
          settings_hash.h) is limited to modern x86 processors.


COMPILATION (Version 1.0, August 2006):

To compile quart on a 64-bit LINUX/UNIX system, from the
Hashing package you need the three files below.

   hashing.c
   hashing.h    settings_hash.h

You might have to edit settings_hash.h. If you have less than 2GB
RAM then the HASH_BREITE needs to be reduced.

Further, the following seven files are necessary.

   arith.c    quart.c       post_proc_quart.c
   arith.h    settings.h    post_proc_quart.h    gmp_headers.h

It is important to edit gmp_headers.h.
Quart needs to know the exact place where in your system the two
include files gmp-impl.h and longlong.h from the GMP package are
located.

You might also want to edit settings.h.

When all the above files are copied into the current directory,
the simple command line

  gcc -O2 -lgmp hashing.c arith.c quart.c post_proc_quart.c -o quart

should compile quart.

Be aware that quart.c contains almost no macros but some functions
declared as inline. It is important for the performance that the
compiler takes this into account.

Instead, you might prefer to use the Makefile provided. The command

        make quart

will compile quart, as well.

For this, it is important that each of the files is located at its
proper place. Depending on your system, you might have to edit the
Makefile before compilation.

We decided to provide a makefile for your comfort although quart is
a very small project which does not actually require a makefile.


INSTALLATION

To run quart, only the executable file quart is necessary. Move it
to a directory which is in the PATH variable.

Be aware that quart needs to be recompiled when settings.h is changed.


PURPOSE

We consider the Diophantine equation
   a*x**4 - b*y**4 = z**4 + v**4 + w**4         (a, b > 0)
and search for small primitive solutions in non-negative integers.

Up to now, a and b are limited to 8 bits while x, y, z, v, and w
are limited to 20 bits.


Idea:
We hash all useful quadruples (a, b, x, y).

Here, useful means
 non-negative and not too big,
 congruences modulo 16 and modulo 5 are tested,
 if ax**4 - by**4 = 0 then there is a primitive solution only if
      gcd(x, y) = 1.

Then, we search for (z, v, w) in the table.

The hash function is
   (z, x)
    ---> "hash_breite leading bits of (z**4 - x**4) mod 2**32".
The control value is (z**4 - x**4 div 2**32) mod 2**15.


Estimated total running time for SUCHWEITE 100000 and
A_LIMIT = B_LIMIT = 100 on a Sun V20z with an Opteron 248 and
4GB RAM: Approximately 155 days.


TO RUN quart on the pages from low to high type
   quart low high
on the command line. All solutions within the given limit will be
found for low = 0 and high = page_prime - 1.


REFERENCES

A more detailed description of the quart project may be found in the
paper

A.-S. Elsenhans and J. Jahnel: The Asymptotics of Points of Bounded
Height on Diagonal Cubic and Quartic Threefolds, Algorithmic number
theory, Lecture Notes in Computer Science 4076, Springer, Berlin
2006, 317--332