The Java Code
In this chapter we will give a detailled description of a Java program, that implements Gauss' cyclotomic method. The complete source code and the jar-files are available for download on this page. We will only describe those parts of the program, which are in direct connection with the Gaussian method.
As a matter of fact, we have to talk about two programs, called Hermes and Kompressor. However, the second program will not be presented here in detail, because its purpose is merely to compress (as indicated by the name) the output of the first program by discarding all square root expressions, that do not find their way into the final one. In case of the 257-gon 89 out of 129 expressions are eliminated in that way, in case of the 65537-gon even 8009 out of 10114 drop out (not counting the expressions that have already been rejected by the first program). Moreover, the second program splits the output of the roots into several lines, if they are too lengthy, which is prevalent in case of the 65537-gon.
Because Hermes is able to print out LaTeX code, which may be transferred unchanged into chap.8 or into the bulky PDF, the program Kompressor accepts its input as LaTeX code only.
Both programs are Java console applications, there is no elaborate graphical user interface. Both programs deliberately have a Spartan design, in order not to drown the important algorithms in a sea of trivialities. So even output to a file is abandoned and the lists are printed to System.out (of course Kompressor cannot avoid input from a file). Consequently, it is strongly recommended, to redirect the output stream to a file, if the calculations for the 65537-Eck are done.
Installation
To install the programs you copy the files Hermes.jar and Kompressor.jar into any directory of your choice. To run the programs, it is necessary to install the Java® SE Runtime Environment (JRE) Version 7 (or higher).
User Interface
To start the program Hermes, open the Windows command prompt or a Linux console and type
java -jar Hermes.jar [num] [opt]When starting an evaluation for the 65537-gon it is recommended to type
java -jar -Xms512m -Xmx768m -XX:MaxPermSize=256m Hermes.jar [num] [opt]
otherwise there may be not enough heap space. The argument [num] accepts only one of the numbers 5, 17, 257, 65537. A calculation for the triangle is not implemented, because it would have required ugly exceptional handling in several algorithms.
By the argument [opt] the layout of the output is defined:
-tex : Output of the square roots as LaTeX code -ascii : Output of the square roots as plain ASCII text -num : Output of the square roots including numerical values -val : Output of the numerical value of each period -ref : Output of the numerical value of each period plus reference value and deviation -roots : Output of the exponents of the roots of unity belonging to a period -sorted : Same as above, but sorted
Several options may be combined. In this case the particular output formats are mixed. As already said, the output goes to System.out.
To start the program Kompressor, open the Windows command prompt or a Linux console and type
java -jar Kompressor.jar [num] [file]
The argument [num]
accepts only the numbers 17,
257,
65537.
For the regular pentagon there is nothing to compress. The argument is necessary, to find the
starting point for the (simulated) insertion process into the square root expressions.
For the 17-gon this is the period $p_{3,0},$ for the
257-gon it's the period $p_{7,0}$ and for the 65537-gon the period $p_{15,0}.$
In a first run, let's say in the case of the 65537-gon, it is determined,
which periods of lower level are used by the period $p_{15,0},$ then it is
recursively searched backwards for periods used by these periods, and so on, until one
finally reaches the period of level $0.$
All those periods ar tagged as
necessary
for the construction of the polygon.
In a second run only the necessary periods are printed in correct order –
thus the other periods are automatically discarded.
The argument [file] specifies the name of the input file for Kompressor. This file, on its part, has to be the output file of a run of Hermes, created with the argument -tex. As already said, the output goes to System.out.
A Quick Tour through Hermes
In short prose the method of operation of the program can be summarized as follows:
At first, the Gaussian period of level $0$ is created by successive exponentiation of the
primitive element $3$ (see fill
).
The periods of level $1$ are created by splitting (see split
) of
the $0$th period, and generally the periods of level $n+1$ by splitting of periods of level $n.$
The two daughter-periods of a splitted period are multiplied with each other –
we don't care about adding the periods, because the result is already known, namely the
parent-period.
The multiplication is performed (see mult
)
employing a multiplication table, similar to what we have done for the 17-gon.
The exponents have to be added and are reduced$\pmod p$ immediately.
At the same time, a little book-keeping is done, counting the multiplicity of
every emerging exponent. That's also similar to our approach to the 17-gon, where
we have counted the exponents pointing at them with a pencil.
That's all we need for the core algorithm of the whole program: The parent-level is searched for periods which can be summed up to give the result of the multiplication. If an exponent (from the multiplication table) is found in a certain period of the parent-level, the whole period is taken as a summand for the linear combination, and the multiplicities of all exponents of this period are lowered by $1.$ This must work, without stumbling upon negative multiplicities or remaining exponents in the multiplication table, because we have proved it arduously in the preceding chapter. Of course, the program will check it anyway.
At the end of this procedure the coefficients of the linear combination have been found, and it becomes clear, why we have made such a fuss about the fact that these coefficients are positive integers or zero. Otherwise, the attempt to find the coefficients by counting would have been doomed to failure from the beginning.
Sum and product of the periods under inspection are now represented as linear combination of
periods of the preceding level, and can thus be inserted into the solution formula of the
quadratic equation, see compute
. At the next step, we
proceed to the periods of the daughter-level by splitting the periods just multiplied. This
algorithm (split – multiply – search coefficients – compute square roots)
is repeated until we reach the periods of length $2.$
The program produces a successive output of square root expressions, which contain only sums and products of square root expressions already printed. Because the $0$th period is always $-1,$ we have for every period a representation with only sums and products of rational numbers and nested square roots, in other words: this sequence of roots is the description for the construction of the regular polygon under inspection.
So much for the quick tour, now we will go into the details:
Top Level structure of the Program Hermes
On the top level the program Hermes
is structured as follows:
package hermes; class Period { ... } class Hermes { public static void main(String[] args) { ... } }
The main
-method of the class
Hermes
evaluates the command-line arguments and builds a linked list
of instances of the class
Period
, which – of course – represent the Gaussian periods.
The linkage is twofold: one horizontal chain links all periods of the
same level, another vertical link allows to step back from every period to
the parent-period of which it has been created by the splitting process.
The class Period
is the central part of the whole algorithm, so
we start now to analyze it. Let's begin with the data:
class Period { int len; // length of this period int modulus; // it's either 5, 17, 257 or 65537 int level; // level of the period int twoPowLevel; // 2^level int seqnr; // sequent. number within level int nr; // number of period within level // all exponents are 3^k with // k = nr (mod 2^level) int primroot = 3; // primitive root 3 int[] exponents = null; // exponents of the roots of unity int[] exponents_sorted = null; // the same sorted Period leftSplit = null; // used for splitting Period rightSplit = null; // the same Period father = null; // vertical link Period neighbour = null; // horizontal link Period mostleft = null; // to 1st period in level Period[] msummands = null; // representation as lin. comb. of periods int[] mfactors = null; // with these factors char sign; // sign of the squareroot double theP; // used for solving the double theQ; // quadratic equation double numericValue; // value of period by sqareroots double referenceValue; // value of period by cosinus String name; // name of period p_{m,n}
Here we meet again many quantities, that have played a role in the preceding chapter
when we performed our calculations with Gaussian periods.
The length len
of the period, which is cut in half during the
process of splitting, starting with the value $p-1$ or $2^N$ at
level
$0.$ The next quantities are used to identify the period,
using the notation scheme presented in the preceding chapter.
The most important quantity, however, is the array exponents
, because this
is in fact the Gaussian period. Of course, the array does only
contain the exponents of the roots of unity, in that order, as
is created by successive exponentiation with primroot
or by the splitting process.
The array exponents_sorted
is used on the one hand for sorted output of the
exponents, on the other hand, when searching for a certain exponent within this period.
The following pointers represent the vertical and horizontal linkage between the
periods. Following the link neighbour
one can scan a
level
from left (mostleft
) to right.
This is done, for example, to find the representation as linear combination of a product
of two periods.
This linear combination by periods of the parent-level is stored in the array
msummands
. At the same time the multiplicity of the particular period, or
in other words the coefficient of the particular period within the sum is stored
in parallel in the array mfactors
.
The following double
-quantities serve for the computation of the
numerical value of the period. In numericValue
the value is computed by
solving the quadratic equation, in
referenceValue
the same value is computed by directly summing up the
corresponding values of the cosine.
The last field is used to give every period its proper name
in printable LaTeX
notation, as it has been specified in the
preceding chapter.
Constructor and Initialization
The constructor of the class Period
is deliberately kept small, because
almost all instances of Period
are created by splitting and thus inherit their data
from the father
.
That's the reason why the procedure initialize
is separated from the constructor.
public Period(String name, int len, int modulus, int primroot) { this.len = len; this.modulus = modulus; this.name = name; this.primroot = primroot; exponents = new int[len]; } public void initialize(Period leftest, double numV, int level, int nr) { this.level = level; this.seqnr = nr; this.twoPowLevel = 1; for (int i=0;i < level;i++) this.twoPowLevel*=2; this.mostleft = leftest; this.numericValue = -1.0d; }
Computing Exponents
The following method to create a Gaussian period from scratch is a little bit more intersting:
public void fill(int primitive) { exponents_sorted = null; exponents[0] = 1; for (int i = 1; i < len; i++) { exponents[i] = (exponents[i-1]*primitive) % modulus; } setReferenceValue(); }
Here the array exponents
is filled by successive exponentiation of the
primitive element primitive
. Simultanuously the congruence class
due to the modulus
is computed in each step.
After completion the numerical reference value for this period is computed
by a call to setReferenceValue
. The latter method is implemented as follows:
private void setReferenceValue() { double re = 0.0d; for (int i = 0; i < this.len; i++) { int exp = this.exponents[i]; re += Math.cos(2 * exp * Math.PI / modulus); } this.referenceValue = re; }
The real parts of the roots of unity belonging to this period are summed up.
In other words, the expression
\[ \sum_{p_{n,m}} \Re(\zeta^{3^k}) = \sum_{p_{n,m}} \cos(\frac{2\pi 3^k}{p})
\]
is computed, where exp
$=3^k$ runs through all exponents of the
particular
Gaussian Period.
The reference value is used primarily to find the correct sign for the
corresponding square root expression.
Splitting of a Period
The following method is at the heart of the algorithm. It implements the splitting of a Gaussian period into two new periods each of half length.
public Period split(int which, int level, int seqnr) { if (leftSplit == null) { int l = this.len / 2; int index = this.nr; leftSplit = new Period("p_{" + level + "," + index + "}",l, modulus,primroot); leftSplit.father = this; leftSplit.level = level; leftSplit.seqnr = seqnr; leftSplit.nr = index; leftSplit.twoPowLevel = this.twoPowLevel * 2; seqnr++; index += leftSplit.twoPowLevel/2; rightSplit = new Period("p_{" + level + "," + index + "}",l, modulus,primroot); rightSplit.father = this; rightSplit.level = level; rightSplit.seqnr = seqnr; rightSplit.nr = index; rightSplit.twoPowLevel = leftSplit.twoPowLevel; int j = 0; for (int i = 0; i < l; i++) { leftSplit.exponents[i] = this.exponents[j]; j++; rightSplit.exponents[i] = this.exponents[j]; j++; } leftSplit.setReferenceValue(); rightSplit.setReferenceValue(); } if (which == 0) { return leftSplit; } return rightSplit; }
The method returns, depending on the parameter which
, the
left daughter-period (containing the first exponent of its parent-period)
or the right daughter-period. However, both periods are already computed
at the first call, the right one goes to the stock expecting the
second call. The most complicated part is the generation of the name of the
right daughter period. Due to the notation introduced in the last chapter,
a period with name $p_{n-1,m}$ is splitted to
$p_{n,m}$ and $p_{n,m+2^{n-1}}.$ The relevant computation is done by the line
index += leftSplit.twoPowLevel/2
.
The method stores its own instance
this
as father
for both daughter-periods. Moreover both new periods are
marked by a sequence number seqnr
. This number is used, when the
computation of periods is cancelled in case of the big moduli
257 or 65537. Cancellation may take place, if it's clear that more periods of
this level are not needed for the calculations of the next level (this will
be clarified soon).
The proper splitting of the exponents of
father
into those of his children within the for
-loop is
done canonically.
Multiplication
There is a method add
to add two periods. However this method
is only used by a validity check, and it's rather boring so that we refrain from
presenting it here. More complicated and more important is the method to
multiply two periods:
public boolean mult(Period other) { int[] temp = new int[modulus]; for (int i = 0; i < this.len; i++) { for (int j = 0; j < other.len; j++) { int result = (this.exponents[i] + other.exponents[j]) % modulus; temp[result]++; } } int le = modulus / (this.len + this.len); msummands = new Period[le]; mfactors = new int[le]; Period start = this.father.mostleft; int k = 0; while (start != null) { msummands[k] = start; k++; start = start.neighbour; } for (int i = 0; i < modulus; i++) { while (temp[i] > 0) { int j; // search exponent i in msummands for (j = 0; j < msummands.length; j++) { if (msummands[j] != null && msummands[j].contains(i)) { break; } } if (j < msummands.length) { for (int l = 0; l < msummands[j].len; l++) { temp[msummands[j].exponents[l]]--; } mfactors[j]++; } else { System.out.println("% Root "+i+" = "+temp[i]+"not resolved"); return false; } } } // plausibilty check for (int i = 0; i < modulus; i++) { if (temp[i] != 0) { return false; } } simplify(); other.msummands = this.msummands; other.mfactors = this.mfactors; compute(other); return true; }
At first a temporary array temp
is created, to store the result of the
multiplication temporarily. The multiplication itself is done within the
double for-loop for every pair of summands of the two periods
this
and
other
. Of course, we have only to add the exponents, and compute the
congruence class due to the modulus
on the fly.
The array temp
consists of counters, to memorize how often
each exponent appears in the product.
Now comes the critical step, because now the result of the multiplication has to
be represented as linear combination of periods of the parent-level.
That's the task of the the arrays msummands
and
mfactors
, which are created with the length
modulus/2*len
.
Within the while
-loop the possible summands are stored to the
array msummands
. To do this, the pointer
start
is set to the first or
most left period of the parent level, namely
this.father.mostleft
, and proceeding via the link
neighbour
the whole level is scanned.
The next two nested loops, the outer for
-loop and the inner
while
-loop implement the search for the exponents produced by the
multiplication within the periods of the parent-level.
The for
-loop processes successively each exponent of temp
,
the while
-loop takes care of the multiplicity of every exponent.
The loop marked by the comment search exponent i in msummands does exactly that,
namely to search the exponent, which is a result of the multiplication, within the periods of
the parent-level that have been collected in msummands
.
To do this, the method contains
is used, which will be presented later.
If the search is successful – and it must be successful by reason of
our proof, the inner loop is exited with break
.
By the way, the security check msummands[j] != null
is necessary, because
several levels are not completely computed – more about that later.
When the loop is exited j < msummands.length
must be true. The
else
-branch of the corresponding condition is only entered, if we
made a mistake when cancelling the computation of periods within a level,
in other words, if we did not compute periods although they are needed
for the computation of periods of a higher level. After debugging of the program this
cannot happen. The computations within the if
-branch
trust in our theory: We suppose that, if the result of the multiplication
contains the exponent i
found in the period
msummands[j]
, it contains all
exponents of msummands[j]
. Hence, we count down for all these exponents
in the array temp
the multiplicity by one and count up the corresponding
entry in mfactors
by one, indicating that we identified the whole period
as part of the linear combination.
The final loop, marked as plausibilty check, checks if all
exponents of temp
could indeed be assigned to a period.
By a call to the method simplify
we try to merge summands of the
linear combination just constructed.
Then the simplified linear combination is assigned to the second
period other
, since the representation as
linear combination is a property of the product of this
and other
, in the same way as the sum of
this
and
other
is assigned to both periods by the same value of
father
.
At the end the method compute
is called, in order to actually solve the
quadratic equation numerically – more will follow soon.
Hence, the method mult
gives the experimemntal proof, as we have called it in
the preceding chapter, that the result of a multiplication of the two periods
$p_{n,m} \cdot p_{n,m+2^{n-1}}$
is a linear combination of periods of the parent-level.
It shall not be concealed, that with some additional effort, both of the underlying theory and of the implementation, we could have obtained simpler expressions for the linear combinations, in some case with negative coefficients. You may find details at [Bracke 2011]. However, our main goal has been to keep the theory as well as the implementation as simple and transparent as possible.
Simplification and Setting of Signs
The method simplify
tries just that, to simplify the linear combination,
however very superficially.
private void simplify() { for (int i = 0; i < msummands.length - 1; i++) { if (mfactors[i] != 0 && msummands[i].seqnr % 2 == 0 && msummands[i + 1].seqnr == msummands[i].seqnr + 1) { if (mfactors[i] == mfactors[i + 1]) { if (msummands[i].father != null) { mfactors[i + 1] = 0; msummands[i + 1] = null; msummands[i] = msummands[i].father; } } } } }
It is checked, if two adjacent periods are children of the same father
and have the same multiplicity. If so, the sum of these periods is replaced by their
father
, who is this sum. The check is done by comparing the
seqnr
. It would as well be possible to compare the links to
the father
directly, but then a security check
father != null
had to be implemented, even if a simplification
is impossible because of different multiplicity.
You will surely agree, that this method is superficial, perhaps you feel inclined to
implement something more sophisticated yourself. If you succeed, don't hesitate to
let me know. However, even the simplistic simplify
merges about 3400 pairs of periods in case of
the 65537-gon.
The method compute
computes the numerical value of the two periods just
multiplied. Remember, that the value of a period is found as solution of a
quadratic equation:
\[
x_{0;1} = \frac{(x_0+x_1) \pm \sqrt{(x_0+x_1)^2-4x_0 x_1}}{2}\eqndot
\]
where $x_0+x_1$ is the value of the sum of the periods, in other words the value
of the father
, and the value of the product
$x_0 x_1$ is the value of the linear combination, we have just painfully assembled.
Because this linear combination contains only periods of lower level, all their
values are already known, and can directly be inserted into the computation.
In the method compute
the quantity
$x_0+x_1$ is denoted by $p$ and the quantity $x_0 x_1$ is denoted by
$q,$ as it is usually done with the solution formula for a quadratic equation.
public void compute(Period other){ double p = father.numericValue; double q = 0.0d; for (int i = 0; i < msummands.length; i++) { if (mfactors[i] != 0) { q = q + mfactors[i] * msummands[i].numericValue; } } double D = p * p - 4 * q; double root1 = (p + Math.sqrt(D)) / 2; double root2 = (p - Math.sqrt(D)) / 2; this.theP = p; this.theQ = q; if (Math.abs(root1 - this.referenceValue) < Math.abs(root2 - this.referenceValue)) { this.numericValue = root1; other.numericValue = root2; this.sign = '+'; other.sign = '-'; } else { this.numericValue = root2; other.numericValue = root1; this.sign = '-'; other.sign = '+'; } }
The value of p
arises immediately from
father.numericValue
.
The value of q
is calculated by summation of the values of
the periods, which are contained in the linear combination, of course multiplied with
their respective multiplicity.
After this both roots root1
and root2
are computed, simply by applying the solution formula
of a quadratic equation.
The last lines of the method implement the above-mentioned trick to get the signs correct.
The roots just computed by extracting a square root are compared with the reference values
computed before by summing up the cosines.
Depending on the result of the comparison either the period this
or the
period other
will get the positive or the negative sign of the root
respectively,
By the way, this trick has been already recommended by Gauss himself
(see [Gauß 1801]):
Hat man diese aus den Sinustafeln auf nur wenige Stellen berechnet, namlich soweit dass man entscheiden kann, welche größer, welche kleiner sind, so kann kein Zweifel mehr übrig sein, durch welche Bezeichnungen die einzelnen Wurzeln der Gleichung (A) zu unterscheiden sind.
Having computed the first few digits [of the reference values] by using a table of sines, namely only until one can decide which are greater and which are smaller, no doubt is possible, by which signs the particular roots of equation (A) must be distinguished.
At the beginning of the computation, the difference between
root1
or root2
respectively and the corresponding
referenceValue
is about
$10^{-12}.$ For the 65537-gon rounding errors accumulate, when higher level periods
are reached. For the last levels differences of about $10^{-4}$ may occur.
This will be discussed in more detail later on.
Auxiliary and Printing Procedures
The small auxiliary procedure contains
determines, whether
a peculiar exponent exists within this period. For this purpose the exponents are
sorted at first. This may seem expensive, but contains
may be called
very often, and the procedure sort
does nothing, if
exponents_sorted
is not null
. Hence, the effort may be
worthwile.
} public boolean contains(int what) { this.sort(); for (int i : this.exponents_sorted) { if (i == what) { return true; } if (i > what) { break; } } return false; }
Another small auxiliary procedure, using also the array exponents_sorted
, is
equals
. It determines, if two periods are equal, and is used only
during plausibility checks.
public boolean equals(Period other) { if (this.len != other.len) { return false; } if (this.modulus != other.modulus) { return false; } this.sort(); other.sort(); for (int i = 0; i < this.len; i++) { if (this.exponents_sorted[i] != other.exponents_sorted[i]) { return false; } } return true; }
Of the printing procedures only the branch of the LaTeX output is presented in what follows.
public void print(String arg) { switch (arg) { case "-tex": String texstring0 = "\\[%s = %.12f\\]%n"; String texstring = "\\[%s = \\tfrac{%s %s \\sqrt{%s^2 - 4(%s)}}{2}\\]%n"; if (this.father == null){ System.out.printf(texstring0,this.name, this.numericValue); break; } System.out.printf(texstring, this.name, father.name, this.sign, father.name, this.toString()); break; ... } }
The format string texstring
specifies, how the square root expression
of this period will be printed as LaTeX code. It can be seen, that
the name of the father
is inserted in place of the summand
before the sqrt
as well as in place of the
squared summand of the radicand. This reflects that the
father
is the sum of the two periods, of which one is under inspection.
The product of the two periods is given by the linear combination, that has been
assembled by the method mult
. This linear combination is
formatted for printing by the
toString
-method of this period:
public @Override String toString() { StringBuilder buf = new StringBuilder(); if (msummands != null) { for (int i = 0; i < msummands.length; i++) { if (mfactors[i] != 0) { if (mfactors[i] > 1) { buf.append(Integer.toString(mfactors[i])); } buf.append(msummands[i].name); buf.append("+"); } } } buf.setLength(buf.length() - 1); return buf.toString(); }
The building of the string is entirely canonical: Scanning the array
msummands
the names of the summed periods are extracted and
appended to the string together with their paticular factor, taken from
mfactors
. In the last but one line, the superfluous last
plus sign is eliminated. When doing the calculation for the 65537-gon,
the string may become very long. Fortunately, we never exceeded
the limits of the StringBuilder
class. For printing, this long string
is splitted by the above-mentioned separate program Kompressor
.
Other Methods of Period
Several methods of the class period
will not be presented in detail,
for example the standard algorithms, used in sort
or in quicksort
, or the procedure cleanUp
, which had been designed
to free heap memory, if in case of the 65537-gon there should be a shortage.
However, it turned out that no problems occured, when calling the program with
the above-mentioned arguments
-Xms512m -Xmx768m -XX:MaxPermSize=256m
. The elapsed time computing the 65537-gon
is tolerable as well. Originally the program had been written on a rather slow computer
(built 2008 with 3 GHz double-core CPU and 2 GB RAM). The CPU time of about 33 sec. found in
chap.7 or in the original output
is that of the old computer. On a slightly faster model
(built 2016; 3.3 GHz Core i5-6500 with 8 GB RAM) the computation of the 65537-Eck requires about 10 sec. CPU time.
The procedure refactor
will also not be described in detail.
It's a clone of compute
, but instead of the quantities numericValue
of the father
or the periods of msummands
the quantity
referenceValue
is used. As already said, when computing the highest
periods of the 65537-gon, the rounding errors have accumulated up to about
$10^{-4}.$ This would normally be no problem, but just in case of the very last period
$p_{15,0}$ this leads to a negative value of the radicand and the result NaN
for the square root. Hence, we have to refactor the last period. This problem is described
in detail in chapter 8 about the 65537-gon.
The Main Program
The main program starts with the evaluation of the arguments. We need not go into detail here.
Then the Gaussian period of level $0$ (called p_base
) is initialized
and filled with its exponents by a call to p_base.fill(3)
.
Here the primitive element $3$ is fixed for the rest of the computations.
It follows the main loop to create the vertically and horizontally linked periods:
public static void main(String[] args) { long startTimeNano = System.nanoTime(); System.err.println("% Job started."); System.out.print("% Running with arguments: "); for (String arg : args) { System.out.print(arg + " "); } ... Hermes cyc = new Hermes(); int base = fermatPrime - 1; Period p_base = new Period("p_{0,0}", base, fermatPrime, 3); p_base.initialize(p_base, -1.0d, 0, 0); p_base.fill(3); int periodLen = base; int level = 0; Period actV = p_base; p_base.print(args); while (periodLen > 2) { periodLen /= 2; Period actH = actV; Period baseH = null; Period leftest = null; level++; int nr = 0; while (actH != null) { Period left = actH.split(0, level, nr); if (baseH != null) { baseH.neighbour = left; } else { leftest = left; } baseH = left; left.mostleft = leftest; Period right = actH.split(1, level, nr); if (!actH.equals(left.add(right))) { System.err.println("% Error when splitting!"); } baseH.neighbour = right; baseH = right; right.mostleft = leftest; // the kernel of the whole program if (left.mult(right)) { left.print(args); right.print(args); } else { System.err.println("Error in multiplication!"); } if (periodLen == 2) { finalPrint(left, right, fermatPrime, args); break; } actH = actH.neighbour; nr += 2; if (level == 14 && nr > 16) { break; } if (level == 13 && nr > 1900) { break; } } actV = leftest; } long taskTimeNano = System.nanoTime() - startTimeNano; System.out.println("% Time used: " + taskTimeNano / 1000000000.0d + "sec"); System.err.println("% Job finished."); }
The two periods actV
, suggesting
vertical, and
actH
, suggesting
horizontal are used, to navigate through the periods under construction.
The outer while
-loop moves vertically, from level to level,
the inner while
-loop creates the periods within one level by
splitting the periods of the parent level, and links them horizontally via neighbour
.
Admittedly, the direct access to neighbour
and
mostleft
, located in another class, is not flawless Java, but
it seemed not appropriate to inflate the code by implementation of
setter
-methods, and to distract from the essential.
The essential is marked – a little elevated – by the comment
the kernel of the whole program. Here the two periods left
and right
, just created by splitting, are multiplied. We have already seen,
what hard work lurks behind this multiplication.
Immediately after this, the output of the two periods is triggered. The reason is on the one hand, that all necessary information is completey available at this moment (we work successively ), on the other hand it reflects the fear of heap saturation, when computing the 65537-gon. The information should be quickly saved on paper , to allow the garbage collector to do its work as soon as possible.
Thereby most of the work is done. We only have to talk about some
special treatments. Of the last level with period length $2$, only the
first period has to be computed, because its value is $2\cos(2\pi/p).$
Hence, periodLen == 2
trigers the final output and the inner loop is
exited. Because the period length $2$ has been reached, the outer loop is terminated as well
and the program ends.
The two if
-statements, checking for
level == 14
or
level == 13
respectively, are intended to reduce the amount of data,
when computing the 65537-gon. These cuts have been introduced only after the
first trial run, when it became clear that the periods skipped were not needed for
the calculation of $p_{15,0}.$ After all, one saves about 6000 lines of output in level 13
and even 16000 lines of output in level 14.
We have already mentioned the checks within the program, that would yell, if
a period had been skipped erroneously.
Note, that the trigger for the cut is the sequence number nr
.
The last computed roots within the respective level are
$p_{13,3164}$ and $p_{14,3072}.$
We end this chapter with the description of the method finalPrint
:
public static void finalPrint(Period left, Period right, int fermatPrime, String[] args){ System.out.println("% 1/2 * " + left.name + " = " + left.numericValue / 2); System.out.println("% cos(2*pi/" + fermatPrime + "): " + Math.cos(2 * Math.PI / fermatPrime)); if (Double.isNaN(left.numericValue)) { System.out.println("% Taking reference values!"); left.refactor(right); left.print(args); System.out.println("% 1/2 * " + left.name + " = " + left.numericValue / 2); } }
The numerical value of the period computed by evaluation of the square roots is printed,
followed by the value computed by evaluation of the cosine, for comparison.
If necessary, the special treatment in case of rounding errors follows. If the
value of the last period is NaN
, the method
refactor
is called and the value is computed again on basis of the
reference values. Let's remark again, that this special treatment is only
for the very last period of the 65537-gon.