Copyright (C) 2004 Bryant Lee This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. README ------------- FPeriod v3.67 Written by: Bryant Lee (blee3@wam.umd.edu) 12/20/04 last modified: 1/18/06 This document describes how to use the FPeriod program. For information on how to compile from source code, see COMPILE.txt. Run FPeriod ------------- The FPeriod program determines how many points of a given shift period are also periodic under a function f. To run, type: FPeriod < INPUT_FILE The easiest way to explain how the program works is to use an example. Suppose we use the following input file: Input1.txt ------------- output after each no trunc out/FP_12_20_2004_ 2 10; 11; [14,16] BEGIN DEFINITIONS func1 = t(4, 0001 1101 1110 0010) M = x[0] + x[1] A = x[0] + x[1] * x[2] BEGIN COMMANDS M#A func1 Explanation of the input -------------------------------- Line 1: Output mode. There are only two valid inputs for line 1, either "output after each" or "output at end". If "output at end" is chosen, then the program does not produce output files until the runs for all values of K are complete. If "output after each" is chosen, then the program generates output files at the end of each run for a different value of K. This is helpful when using a long range of K values where some of the larger values may cause the program to crash (due to running out of memory), which results in no output at all in the "output at end" mode. However, it wastes a little time because outputting after each K value is redundant. Line 2: Must be either "trunc" or "no trunc" which determines whether the full output is given or truncated output is given. See the section "Output" below for the difference between these output modes. Line 3: Prefix for output files. When the program finishes, output will be written into several different files. In the example, all the output files will be written into the subdirectory "out" and will start with the prefix FP_12_20_2004_. Line 4: N = Number of symbols in the shift. Line 5: Values for K, the shift period. Specify ranges of values using [a,b] notation or specify single values as a number. Different sets of values are separated by ';'. The use of whitespace on this line is not important. Line 6: "BEGIN DEFINITIONS." This signifies that on the following lines you will define functions (give them names). This line is not case sensitive: "BeGiN DeFiNiTiOnS" is equally valid. The definitions section is used to name functions so that the names can be used in the command section. Defining a function does not mean that FPeriod will analyze that function. You must give the command to analyze a function in the command section. Lines 7 - 9: The first function is named "func1." A function can be named with any single word (i.e., a string of characters with no spaces). The = signifies that the function on the RHS is named by the LHS. This function, "func1," is specified in lookup table syntax. The 't' signifies that the function is specified as a table. The first value in parenthesis is the span of the function and the second value is the table itself. The rules for specifying lookup tables are explained in "Lookup table syntax" below. The second and third functions are specified as polynomials. Certain rules apply to specifying functions as polynomials: see the section "Polynomial syntax" below. NOTE: Using a lookup table is many times faster than calculating a polynomial (in tests, one function was 25 times faster as a table than as a polynomial). However, one can optimize functions specified as polynomials to make them as fast as a lookup table. See the section "Optimizing polynomial functions" below. Line 10: "BEGIN COMMANDS." This signifies that you are done defining functions and will now give commands on the following lines. The commands tell the program which functions it should analyze. In the command section, you specify functions and compositions by using the names you defined in the definitions section. You cannot write polynomials or lookup tables themselves in the command section. The program generates two output files for each function/composition in the command section (see "Output" section). Lines 11 - 12: The # character signifies composition. Hence, the line "M#A" tells the program to analyze the composition (A(x)). Compositions can be arbitrarily long; you can compose 3, 4, 5, or as many functions as you would like. Both functions that were specified as polynomials and lookup tables can be used in compositions. The next line "func1" tells the program to analyze the function "func1." Output ---------- If "no trunc" is used: Running the program on Input1.txt generates four files in the subdirectory "out": FP_12_20_2004_M#A.txt, FP_12_20_2004_M#A_preperiods.txt, FP_12_20_2004_func1.txt, and FP_12_20_2004_func1_preperiods.txt. If files already exist with these names, they are overwritten. Note that the subdirectory "out" must already exist for this to work. FPeriod will not create directories. It happens that M#A = func1, so the results for both sets of files is the same. The file with the name of the function (or composition) gives the summary and period information, while the file with the name of the function (or composition) and with suffix "_preperiods" contains the preperiod information. Summary and period file: The top of the file gives the input information. Following is information concerning all points of shift period K (these results count the points not of least period K). First is a table of summary information: p is the number of periodic points, and L is the length of the longest orbit. AvgPd refers to the average "eventual" period (a point's eventual period is the period of its orbit, regardless of whether the point itself is periodic). Then comes a table of the periods: Mult(#orbits) is the number of orbits with given period, Mult(#perpoints) is the number of periodic points with given period, and Mult(#points) is the number of points having the given period as their eventual period. Following is similar information except counting only the points of least period K. Preperiod file: This file has the table of preperiods for period K and least period K. If the "output after each" option was used, then some entries in the summary or the preperiod file may be listed as "PENDING". This happens when the program crashes before filling in those entries. If "trunc" is used: Only a summary file is generated, which gives a table of P^(1/k) for each K. Polynomial syntax ------------------------- The operators +, -, *, and ^ may be used. No parentheses are allowed, so strict order of operations must be followed. Often this means that you must simplify by hand a function you wish to express. The coordinates of the x terms are relative (and can be positive or negative). When calculating image[i], the term x[j] refers to the absolute coordinate x[i + j] (e.g., when calculating image[2], the term x[-5] refers to the absolute coordinate x[-3]). Positive integer constants are allowed. Do not use negative constants; instead, change an addition (+) to a subtraction (-). There is one exception to this rule: you may use a negative constant if it is the very first thing in the function (in this case you could not create a subtraction). When writing multiplication, be sure to use *. You cannot juxtapose terms/constants to imply multiplication. The use of white space is not important. Examples of valid polynomials: a = x[0] + x[1] * x[2] b = x[-9] ^ 5 + x[2] * x[3] * 3 + x[5] * x[102] + x[17] + x[-300] * 3 c = - x[99] Examples of invalid polynomials: d = x[0] * -1 e = (x[0] + x[1]) * x[2] f = x[0]x[1] Lookup table syntax --------------------------- Suppose we want to specify the function f = x[0] + x[1]*x[2] as a table. First, note that the function is of span 3. Enumerate the values of the function for values of x[0], x[1], and x[2], going through them in lexicographic order as demonstrated below. Notice that incrementing starts at x[2] rather than x[0]. 0 1 2 3 4 5 6 7 x[0] 0 0 0 0 1 1 1 1 x[1] 0 0 1 1 0 0 1 1 x[2] 0 1 0 1 0 1 0 1 f 0 0 0 1 1 1 1 0 Then the lookup table is "t(3, 0001 1110)". The use of whitespace is not important. Commenting out --------------------------- Lines in the definitions section (after "BEGIN DEFINITIONS" and before "BEGIN COMMANDS") and the commands section (after "BEGIN COMMANDS") can be commented out by preceding them with "//". Commented out lines are completely ignored. In the example Input1.txt, if the last line was replaced with "//func1", the program would not analyze func1. Optimizing polynomial functions --------------------------- Optimizing a polynomial function can be a good way of making the program run faster. To optimize a polynomial function, precede the definition of the function with "OPT" (case-insensitive). In the example Input1.txt, one could replace the definition of A with "opt A = x[0] + x[1] * x[2]". FPeriod optimizes the polynomial by precomputing the value of the function for all possible input x[i] values and storing the results in a table. This allows the function to be evaluated very quickly later on. It is almost always a good idea to optimize polynomial functions, but there are instances when optimization is inadvisable. Consider the function "opt func2 = x[0] + x[1] + . . . + x[99] + x[100]". This function has 100 distinct x[i]'s. Supposing FPeriod was run with N = 2, precomputing the function would require storing 2^100 values, far more than the capacity of any computer in existence. As a rule of thumb, precomputing and storing up to a million values is probably fine as this would require memory in the range of megabytes or dozens of megabytes. Much more than that is not advised. Also be aware that only the number of distinct x[i]'s is important and not the span. For example, "func3 = x[-1000] + x[1000] + x[1000]^2" has only 2 terms and is easily optimized. NOTE: preceding the definition of a lookup table function with "OPT" does nothing.