According to Wikipedia, "the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations". Another, more informal, explanation of what the factorial number system is, is the following: whereas other number systems have a constant base, or radix, (like binary - base 2, or decimal - base 10), this system has a "variable base" that depends on the position the digit occupies in the number. For example, the numeral 1110 represents different numbers depending on the number system:
_one-thousand one hundred and ten_ in base 10: 1*10^3 + 1*10^2 + 1*10^1 + 0*10^0
_fourteen_ in base 2: 1*2^3 + 1*2^2 + 1*2^1 + 0*2^0
_nine_ in the factoradic system: 1*3! + 1*2! + 1*1! + 0*0!
As it has been mentioned, the radix each digit is mulitplied with depends on its position in the numeral: if a digit occupies position i it is mulitplied by i!. Also, while in fixed-base number systems all digits have the same maximum value (one in base 2, nine in base 10), the maximum value of a digit in the i-th position of a numeral in the factoradic system is i-1. Notice that any numeral representing a factorial value (f!, for any natural number f) is the number 100..00 (a 1 followed by f zeroes).
This repository aims at offering a series of algorithms to perform basic arithmetic operations between two numbers in this number system, in the form of a simple interactive calculator (see code). This calculator supports a series of commands, listed in the section "Commands available for the calculator" of this README.
C++ offers a function called next_permutation which "rearranges the elements" (of a given list) "into the next lexicographically greater permutation" (of that list). If we wanted to process the permutations of a list using several threads, we would need to "place" each thread at a starting permutation of that list. In order to have the best distribution of the work possible, the i-th thread of the k threads processing N! permutations will have to start at the (N!/k)*i permutation and will have to process N!/k permutations. Although the function provided by C++ is very useful (as it alleviates quite some work), it does not allow an easy parallel processing of the permutations of a list since, since it does not allow obtaining the j-th permutation of a list. This is where the factoradic number system comes into play: in very few words, this system allows an easy generation of such j-th permutation of an arbitrary long list of elements.
In this file, you will find a minimal piece of code to process all permutations of a list of N elements in parallel (using OpenMP). The code processes all permutations of a list of N numbers and performs a very simple operation on it. Although it is not likely to be needed, this software allows arbitrarily large values of N. (An older version of the minimal code is this file).
The GMP and the OpenMP libraries are needed to compile this project. OpenMP library is only needed to generate the executable that processes permutations in parallel.
Compiling requires the 'make' tool, and a compiler (g++) that supports the flag -std=c++11.
There are two modes of compilation: debug and release. These two modes will create, respectively, a bin-debug/ and a bin-release/ directories. From within the build/ directory, issue the following commands for each mode:
make -f Makefile debug
make -f Makefile release
Two executable files will be generated after all the code has been compiled. The calculator has an interactive mode and another that allows the loading and execution of a program.
In order to use the interactive mode, issue the command:
./calculator -i
The list of all the commands supported can be obtained by entering the "help" command (without the quotes in the interactive mode of the calculator).
If the other mode is preferred then issue the following command:
./calculator -l /path/to/dir/file_name
where /path/to/dir/file_name contains the path (absolute or relative) and the name to the file that is to be executed.
If one wants to run the demo to process the permutations of a list in parallel issue the following command:
./process_permutations N t
where N is the length of the list of elements to be permuted, and t is the number threads. For example, in order to process all permutations of a list of N=10 elements with t=8 threads issue the following command:
./process_permutations 10 8
These are all the commands available for the calculator (this list may not be up-to-date with the actual commands supported - see the result of "help" in the interactive mode of the calculator for a full and up-to-date description of all of them):
> var v s: stores in memory a variable with name 'v' and contents
's', where 's' is a number in base 10.
> op s1 X s2: operates contents of s1 and s2 with operator X.
The operators supported are +,-,*
s1 and s2 must be either a variable name or a number in base 10
> def varname s1 X s2: creates a variable with name 'varname'
with contents the result of operating the contents of s1
and s2 with operator X.
s1 and s2 must be either a variable name or a number in base 10
> cmp s1 C s2: compares the contents of s1 and s2 with C.
The comparisons supported are >,>=,==,<=,<
s1 and s2 must be either a variable name or a number in base 10
> inc v: apply ad-hoc algorithm to increment by 1 the contents of v.
v must be a variable name
> dec v: apply ad-hoc algorithm to decrement by 1 the contents of v.
v must be a variable name
> double v: apply ad-hoc algorithm to double the contents of v.
v must be a variable name
> halve v: apply ad-hoc algorithm to halve the contents of v.
v must be a variable name
> square v: apply ad-hoc algorithm to square of the contents of v.
v must be a variable name
> even v: checks if the contents of v is even.
v must be a variable name
> factorial v n: compute the factorial of n and store in v.
v must be a variable name
n must be a number in base 10
> make-permutation i n s_1 s_2 ... s_n: computes the i-th permutation of
the list of 'n' elements (s_1,...,s_n).
i must be either a variable name or a number in base 10
n must be a number in base 10 that fits in a 64-bit number
> permutation-index n s_1 s_2 ... s_n a_1 a_2 ... a_n: computes the index of
the permutation (s_1,...,s_n) of the list (a_1,...,a_n).
The index is given as a number in base 10.
n must be a number in base 10 that fits in a 64-bit number
> repeat n OPTION: repeats the given COMMAND n times.
n must be a number in base 10
> { COMMAND_1 COMMAND_2 ... COMMAND_N }: allows defining a block of instructions.
This can be useful to repeat a list of options in block
> // ... //: this is a comment. The contents of '...' may be arbitrarily long.
> shrink: removes all leading zeros from all variables in order to save space
> shrink-var: removes all leading zeros from all variables in order to save space
> del-var v: delete variable with name 'v'
> del: removes all all variables
> verbose: activate/deactivate printing execution times
> endlines: activate/deactivate printing leading and trailing endlines
> ls: lists all variables and their content (in factorial base)
> ls-dec: lists all variables and their content (in base 10)
> print v: prints the contets of variable v (in factorial base)
> print-dec v: prints the contents of v (in base 10)
> exit: leave the program ('CTRL + D' is also valid)
> help: print this message