Software Developer Notes for Braid version 28.0
This document is intended as an initial guide to the source code published with the braid programme, it contains information not included in the user documentation that is relevant only to those wishing to extend, customize or otherwise modify the code. It is not a detailed design spec, but contains various comments and definitions on the following topics:
Version 11.1 introduced a structured debug subsystem across classes and the main braid function. Prior to this, various booleans controlled debug output but only a subset of them were accessible from the command line. The debug subsystem allows full debugging control as well as default debug options in a flexible and extensible manner.
Debug information is requested using the # option, followed optionally by a debug specification enclosed in square brackets []. The debug specification is a list of options, separated by colons; an option may be followed by one or more option parameters, enclosed in braces {} and also separated by colons. No spaces are permitted in a debug specification. Thus the general format is of the form:
braid -#[option:option{parameter:parameter}:option]
If no debug specification is given then the default programme debug options are set.
The available debug options can be displayed by running the braid programme with the both the debug option and the hidden help option described above:
[bart@wormwood current]$ braid -#H!
debug options may be specified using the syntax -#[option:option{parameter:parameter}:option]
supported options and parameters:
bigint{san:+:-:*:/:%:rs:ls:bc:==:gt:out:in:sum:diff:num_len:gcd:all}, bitmap: no default
matrix{det:inv:*:all}, bitmap: no default
poly{no-gen:san:+:*:/:in:gcd:all}, bitmap: general debug included unless no-gen specified
rational, boolean
quaternion, boolean
braid{summary|1:basic|2:intermediate|3:detail|4}, integer: default 0=off, no parameters sets summary
vogel, boolean
default options set by omitting [...]
default options:
braid{summary}
Each option corresponds to a class (bigint, matrix, etc.) or a functional area of the programme (braid, vogel). As can be seen from the above output, there are currently three different types of debug control used by the debug options: bitmap, integer and boolean each of which is described below. The option parameters for each of the classes are set by the function set_debug_option_parameter in the file debug.cpp and for the braid programme specific options by set_main_debug_option_parameter in the file main.cpp.
A bitmap debug control variable requires parameters to specify what debug information is required, as an example the bigint_control structure is defined as follows:
struct bigint_control
{
static unsigned int DEBUG; //bitmap
enum parameters
{
general = 0x00000001, // unused
sanitize = 0x00000002,
add = 0x00000004,
subtract = 0x00000008,
multiply = 0x00000010,
divide = 0x00000020,
remainder = 0x00000020,
equal = 0x00000040,
greater = 0x00000080,
output = 0x00000100,
input = 0x00000200,
sum = 0x00000400,
diff = 0x00000800,
num_len = 0x00001000,
r_shift = 0x00002000,
l_shift = 0x00004000,
bool_conv = 0x00008000,
gcd = 0x00010000,
// 'all' also supported
};
};
An integer debug control variable defines different levels of debug information to be provided, as in the case of the braid programme's debug control structure:
struct braid_control
{
enum level {OFF, SUMMARY, BASIC, INTERMEDIATE, DETAIL};
static int DEBUG;
static bool VOGEL_DEBUG;
};
Finally, a boolean debug control variable, the simplest form of debug control, requires no parameters an example being VOGEL_DEBUG in the braid_control structure above. The debug control subsystem is mainly coded in the separate source file debug.cpp, though the braid programme specific debug information is contained in main.cpp.
Debug output is written to the file braid.dbg in the current directory, it is formatted as a list of records that indicate the source of the debug information. Here is a sample debug output when reading the string 2x-1 into a polynomial<quaternion<scalar> > using the biging scalar variant, the debug option used to generate this output was -#[poly{in}:bigint{in}:quaternion].
debug: setting debug option polynomial_control::general
debug: setting debug option polynomial_control::input
debug: setting debug option bigint_control::input
debug: setting debug option quaternion_control::DEBUG
polynomial<T,U>::>>: presented with string: (2x-1)
polynomial<T,U>::>>: polynomial begins with '(', checking for parentheses
polynomial<T,U>::>>: open parentheses detected
polynomial<T,U>::>>: close parentheses detected
polynomial<T,U>::>>: input buffer after removal of parentheses: 2x-1
polynomial<T,U>::>>: number of variables = 1
polynomial<T,U>::>>: variable characters: x
polynomial<T,U>::>>: variable degrees: 1
polynomial<T,U>::>>: length of virtual pterm list = 4
polynomial<T,U>::>>: reading term 1:
polynomial<T,U>::>>: implicit sign = 1
quaternion::operator >> : initial character from istream: (
bigint::operator >> : initial character from istream: 2
bigint::operator >> : putting back digit 2 for main loop execution
bigint::operator >> : next character from istream: 2
bigint::operator >> : a = 2
bigint::operator >> : final value of a = 2
quaternion::operator >> : no comma found after reading real part setting all other quaternionic parts to zero
polynomial<T,U>::>>: absolute coefficient = 2
polynomial<T,U>::>>: coefficient value = 2
polynomial<T,U>::>>: read variable x
polynomial<T,U>::>>: index = 0
polynomial<T,U>::>>: set expoenent = 1
polynomial<T,U>::>>: term place = 2
polynomial<T,U>::>>: reading term 2:
polynomial<T,U>::>>: explicit sign = -1
quaternion::operator >> : initial character from istream: 1
quaternion::operator >> : no opening '(' detected
quaternion::operator >> : digit found, putting 1 back into istream ready to read real part
bigint::operator >> : initial character from istream: 1
bigint::operator >> : putting back digit 1 for main loop execution
bigint::operator >> : next character from istream: 1
bigint::operator >> : a = 1
bigint::operator >> : final value of a = 1
quaternion::operator >> : setting all other quaternionic parts to zero
polynomial<T,U>::>>: absolute coefficient = 1
polynomial<T,U>::>>: coefficient value = -1
polynomial<T,U>::>>: term place = 0
polynomial<T,U>::>>: final polynomial value: 2x-1
polynomial<T,U>::>>: final polynomial structure:
polynomial located at 0xbfba4588
number of variables = 1
variable characters = x
variable degrees = 1
number of virtual pterms = 4
polynomial pterms: 2 present
1 0x8cd2670: x^0
pterm.n = -1
pterm.pl = 0 pterm.prev = NULL pterm.next = 0x8cd1358
2 0x8cd1358: x^1
pterm.n = 2
pterm.pl = 2 pterm.prev = 0x8cd2670 pterm.next = NULL
Polynomials are defined here to be doubly-linked lists of pterm structures, headed by a polynomial structure that points at the start of the list. Each pterm structure corresponds to one term of the polynomial, with only non-zero terms being stored, the number of terms currently held is recorded in the length field of the polynomial structure that points to this list
The polynomial structure also contains information about the number of variables in the polynomial, and the variable characters used and whether those variables are mapped to another object. These definitions do not limit the number of variables, nor the particular choice of variable characters, but the characters i,j,k,I,J,K should be avoided since polynomials may involve quaternions.
The actual definitions are:
template <typename T, typename V=string, typename U=int> class polynomial
{
int nv; /* number of variables */
char* vc; /* string of variable characters */
int* vd; /* array of (maximum absolute) variable degrees */
map<char,V> vm; /* variable map */
U l; /* length of virtual array of pterms */
pterm<T,U>* p; /* pointer to first term of polynomial */
static polynomial<T,U> add_pterm (polynomial<T,U>&, pterm<T,U>*);
/* operators etc */
};
template <typename T, typename U> struct pterm
{
T n; /* coefficient */
U pl; /* place in canonical order - counted from zero */
pterm* prev; /* pointer to previous term */
pterm* next; /* pointer to next tern */
};
Polynomials are taken here to be elements of the ring of Laurent polynomials with coefficients in the ring indicated by T, generated by the stated variables and their inverses. The coefficients may be a built in ring type (int, long, complex etc.) or one of the scalar classes implemented by the braid programme code.
Optionally, variables within a polynomial may be mapped to an object of type V, allowing polynomials involving variables of arbitrary type to be handled. The motivating cases were the arrow polynomial, which requires variables \Lambda_i and K_i (strings rather than characters) and the parity bracket polynomial, which includes graphical nodes as variables. These non-character variables are mapped to proxy character variables in order that the existing code may be re-used, with the mapped type being used for variable comparison and output.
When two polynomials include variable mappings, their mapped variable objects are used for comparison purposes. The implementation does not require that the character used as a proxy for a mapped variable is always the same. Thus, if in x+y the variable x is mapped to an object V and in y+z the variable z is mapped to the same V, then these two polynomials are considered to be the same. Similarly, the code distinguishes between variables in a polynomial that are unmapped and the same variable character in another polynomial that is mapped. Thus, if P_1 = x and P_2 = x (x mapped to V), then P_1 + P_2 = x + a (a mapped to V). As in this example, mapped variable characters are replaced with others, rather than changing unmapped variable characters.
When writing a polynomial with mapped variable to an output stream, the control boolean SUBSTITUTE_MAPPED_VARIABLES is used to determine whether the proxy characters or the mapped object is displayed. If the boolean is false, then the output of the above polynomial x+y would appear as "x+y (x,V)" to indicate the variable mapping, whilst if the boolean is true, the polynomial would appear as "x+V", using the output operator for the object type of V.
At most one variable in a polynomial may be mapped to a given V, an attempt to map a subsequent variable to the same V replaces the mapping of the existing variable with the new variable.
The polynomial structure stores the absolute degree of each variable, in the same order as the variable characters are stored. Thus, for the polynomial x^2y^-3+xy, the absolute degree of x is 2 and that of y is 3.
The zero polynomial is represented by any polynomial structure with a null list pointer. Unit polynomials have no variables, or degrees.
The pterms also contain a pointer to the previous and next pterm in the list: the first pterm in the list will contain a NULL previous pointer, and the last a NULL next pointer.
The pterms do not store the variables to which the coefficients apply, instead we store the place the pterm has in a virtual array of pterms. This is list of polynomial terms based on a canonical ordering of the variables and which is described below. Many of these terms will be zero, which is why we store the place in the list; it also provides a simple mechanism for determining where in a list a pterm should be stored, which is necessary when we start adding or multiplying polynomials.
The place in the virtual pterm list, and the length of the pterm list is indexed by a unit type U, which defaults to an integrer. This allows us to define very large polynomials involving huge numbers of virtual pterms by setting U to be a bigint.
The canonical order of terms is in increasing order based on the exponent of the variables, which may be either positive or negative. For a single variable polynomial, this order is
x^0, x^-0, x^1, x^-1... x^n, x^-n,
the reason for the -0 exponent is due to the place calculation described below. Stick with it, these horrible looking things are never actually stored, remember we are talking about virtual pterms, we are only interested in the place in the list of the terms we want to store. For a two variable polynomial, the canonical order is:
x^0y^0, x^0y^-0, x^0y^1, x^0y^-1, ...,x^0y^n, x^0y^-n...
x^-0y^0, x^-0y^-0, x^-0y^1, x^-0y^-1, ...,x^-0y^n, x^-0y^-n...
...
x^my^0, x^my^-0, x^my^1, x^my^-1, ...,x^my^n, x^my^-n...
x^-my^0, x^-my^-0, x^-my^1, x^-my^-1, ...,x^-my^n, x^-my^-n...
We are assuming here that the absolute exponent of x is m and the absolute exponent of y is n. A three variable polynomial example will enable us to see how to calculate places, consider an additional variable z of absolute exponent k and think of the number of terms we are writing down.
x^0y^0z^0, x^0y^0z^-0, x^0y^0z^1, x^0y^0z^-1, ...,x^0y^0z^k, x^0y^0z^-k...
[there are a total of 2(k+1) entries in the list to this point]
x^0y^-0z^0, x^0y^-0z^-0, x^0y^-0z^1, x^0y^-0z^-1, ...,x^0y^-0z^k, x^0y^-0z^-k...
...
x^0y^nz^0, x^0y^nz^-0, x^0y^nz^1, x^0y^nz^-1, ...,x^0y^nz^k, x^0y^nz^-k...
x^0y^-nz^0, x^0y^-nz^-0, x^0y^-nz^1, x^0y^-nz^-1, ...,x^0y^-nz^k, x^0y^-nz^-k...
[there are a total of 2(n+1)*2(k+1) entries in the list to this point, which we
shall refer to as the x^0 block, or block 0]
...
[here's the x^-0 block, or block 1]
x^-0y^0z^0, x^-0y^0z^-0, x^-0y^0z^1, x^-0y^0z^-1, ...,x^-0y^0z^k, x^-0y^0z^-k...
x^-0y^-0z^0, x^-0y^-0z^-0, x^-0y^-0z^1, x^-0y^-0z^-1, ...,x^-0y^-0z^k,
x^-0y^-0z^-k...
...
x^-0y^nz^0, x^-0y^nz^-0, x^-0y^nz^1, x^-0y^nz^-1, ...,x^-0y^nz^k, x^-0y^nz^-k...
x^-0y^-nz^0, x^-0y^-nz^-0, x^-0y^-nz^1, x^-0y^-nz^-1, ...,x^-0y^-nz^k,
x^-0y^-nz^-k...
...
[ending with the x^m and x^-m block, blocks 2m and 2m+1 ]
x^my^0z^0, x^my^0z^-0, x^my^0z^1, x^my^0z^-1, ...,x^my^0z^k, x^my^0z^-k...
x^my^-0z^0, x^my^-0z^-0, x^my^-0z^1, x^my^-0z^-1, ...,x^my^-0z^k, x^my^-0z^-k...
...
x^my^nz^0, x^my^nz^-0, x^my^nz^1, x^my^nz^-1, ...,x^my^nz^k, x^my^nz^-k...
x^my^-nz^0, x^my^-nz^-0, x^my^-nz^1, x^my^-nz^-1, ...,x^my^-nz^k, x^my^-nz^-k
x^-my^0z^0, x^-my^0z^-0, x^-my^0z^1, x^-my^0z^-1, ...,x^-my^0z^k, x^-my^0z^-k...
x^-my^-0z^0, x^-my^-0z^-0, x^-my^-0z^1, x^-my^-0z^-1, ...,x^-my^-0z^k,
x^-my^-0z^-k...
...
x^-my^nz^0, x^-my^nz^-0, x^-my^nz^1, x^-my^nz^-1, ...,x^-my^nz^k, x^-my^nz^-k...
x^-my^-nz^0, x^-my^-nz^-0, x^-my^-nz^1, x^-my^-nz^-1, ...,x^-my^-nz^k,
x^-my^-nz^-k
There are a total of 2(m+1)*2(n+1)*2(k+1) entries in the list altogether.
Given a variable place p, in the range 0,...2(m+1)*2(n+1)*2(k+1), by looking at the integer part of p/2(m+1), we can tell which block the variable place lies in, and therefore the power of the variable x. If the block number is odd, the power is a negative one, otherwise a positive one, by dividing the block number by 2 and taking the integral part we determine the power of x of the variable stored in place p.
We now take the remainder of p/2(m+1), which indicates the offset into the block of place p. We can now work recursively, dividing this offset by 2(n+1) to determine the power of y and then finally the power of z.
To calculate the place corresponding to a particular set of variables, simply work backwards through this calculation.
Thus to calculate the exponents from a place pl, we have code of the form:
factor = poly.l;
place = pl;
for (i=0; i<poly.nv;i++)
{
factor /= (2*(poly.vd[i]+1));
if ((place/factor)%2)
negative_exp = TRUE;
else
negative_exp = FALSE;
power = place/factor/2;
if (negative_exp)
power *= -1;
aexponent[i] = power;
place %= factor;
}
and to calculate a place:
place = 0;
factor = l;
for (i=0; i<poly.nv;i++)
{
factor /= 2 * (poly.vd[i]+1);
block_num = 2 * abs(exponent[i]);
if (exponent[i] < 0)
block_num++;
place += block_num*factor;
}
As the code has evolved, local classes for things like quaternions, rationals, matrices big integers and big-rationals have been developed. These have been written because "standard" implementations were not available, to ensure I had control over the code, or just as an exercice. However, I have made no attempt to replace them with "standard" implementations as they have become available, to minimize risk in making code changes.
In particular, the local scalar class has been developed to allow run-time selection of an object's type. This class is documented on the scalars page of my website.
I lay out my code in a way that I find easy to read, quick to debug and aesthetically pleasing (to me). It is not quite standard but it is, I hope, clear. My style of writing evolved from working with ALGOL68 many moons ago, so as an example, I always write
char* foo;
char** bar;
rather than
char *foo,**bar;
because ALGOL68 would write
REF CHAR foo;
REF REF CHAR bar;
and I like the ability to look down the left side of the page and see what type of variable I have. Also, as in all the above code snippets, I do not open clauses with a brace at the end of a line, rather I always put delimiting braces on their own line. This is again motivated by ALGOL68 and I find it easier to look down code whose indentation delimiters are vertically aligned. Sorry if you find this weird.
You will find lots of comments in my code, which I hope will be useful if you use any of it for your own work. I would be very happy to provide assistance to anyone trying to understand what I've done, provided I have the time. Email me here if you are experiencing problems understanding what I've done.
You are very welcome to use any of my source code in your programmes, but bear in mind that although it is provided in good faith and to the best of my knowledge the code is accurate, if you decide to use this software then I accept no responsibility for the consequences of any errors it may contain. That said, it would be nice if you included a comment to say where you got it, and sent me an email to say you've used it, just so I get some feedback regarding how useful it actually is!