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 ------------- FProbPeriod v3.67 Written by: Bryant Lee (blee3@wam.umd.edu) 8/30/05 last modified: 1/18/06 This document describes how to use the FProbPeriod program. For information on how to compile from source code, see COMPILE.txt. Run FProbPeriod ------------- The FProbPeriod program samples points of a given shift period and determines their period and preperiod under the function f. The purpose is to give some indication of the period and preperiod information of all the points of the given shift period. To run, type: FProbPeriod < 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 out/FP_8_30_2005_ 2 10; 11; [14,16] 1000 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: 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_8_30_2005_. Line 3: N = Number of symbols in the shift. Line 4: 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 5: m = number of points to sample Points are randomly generated by using an implementation of the Mersenne Twister random number generator of Matsumoto and Nishimura; see M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. on Modeling and Computer Simulation Vol. 8, No. 1, January pp.3-30 (1998). This specific implementation was written by Richard Wagner in 2003. 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 FProbPeriod 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 ---------- Running the program on Input1.txt generates four files in the subdirectory "out": FP_8_30_2005_M#A.txt, FP_8_30_2005_M#A_preperiods.txt, FP_8_30_2005_func1.txt, and FP_8_30_2005_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. FProbPeriod 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 multiplicities, while the file with the name of the function (or composition) and with suffix "_preperiods" contains the preperiod multiplicities. 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 are tables of summary information. Note that 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). Similarly, MaxPd is the maximum "eventual" period. Then comes a table of the periods: Mult(#points) is the number of sampled points having the given period as their eventual period. Preperiod file: This file has the table of preperiod multiplicities for 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. 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]". FProbPeriod 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.