5. Service on-line
In the final section, let's consider the attached online service. The service programs allow you to calculate a single element of the Motzkin Row (hereinafter simply sequence) or a group of items in an arbitrary range. The program complex handles the elements with indices up to 1011. The technology of searching for Motzkin words is characterized as follows:
- the use of a direct enumeration of the sequence elements in a limited interval and in the chosen direction (bottom-up or top-down);
- the application of methods for accelerating the search procedures that implement the described operations on the sequence elements.
The reader can display here a group of elements in an arbitrary range, specifying the initial index and the number of items. A natural restriction is an allowable time frame. The program allows you to enter numbers in a convenient format. For example, you can separate by spaces or points of a triple of digits (thousands, millions, etc.). The information is displayed in a tabular form in a separate browser tab. The number of columns varies depending on the length of Motzkin words. For a better orientation, the elements of the first column are indexed. Indices are also given for maxima, Motzkin numbers; in addition, these table cells are highlighted by a different background color.
The other programs allow here and here to calculate an arbitrary element of the sequence. In the first case, the index of the given element is determined, in the second, the word Motzkin is found at the given index. In long codes, the user can split the item blocks by spaces or "cut" into portions of the group of zeros. It is desirable to limit the Motzkin word to 30 characters (the index is about 1011). In the case of long calculations, intermediate results are given, which can later be used after an abnormal termination of the calculations.
Interactive service programs for speeding up calculations use a directory that contains about 200 elements, reference points of the sequence. In the directory, there are the first 30 maxima and some calculated elements, including the derivative Motzkin words. Calculations are carried out in several stages:
- In the sequence, the minimum possible interval is selected such that, firstly, the given element is located inside the interval and, secondly, the lower and upper boundaries of the interval are the directory items closest to the given elements.
- Further, the position of the element relative to the interval center is determined in order to choose the optimal direction of the search: from smaller indices to large ones (from below to top) or from large indices to smaller ones (from top to bottom). If a bracket set is specified to find the index, then the interval center is determined roughly by the first symbols both in the given set and in the boundary elements.
- At the last stage, a direct search of the given element is performed. If the required element exceeds the reference points of the directory, then the upper limit of the interval will not be. Later such an element is included in the directory (the author's details are below)
During the calculation, programs can perform jumps along the sequence, this greatly speeds up the search procedures. A jump is performed if the Motzkin word, usually an intermediate item of the sequence, ends with either a zero fragment or a group of adjacent parentheses (like a maximum). A zero fragment can be used as the starting point for jumping up the sequence. The maximum fragment gives an opportunity for bouncing down the sequence.
For example, let a be an intermediate item, ending of k zeros. In this case, we can jump up on the sequence if we replace the zeros in a by the fragment ()()...() (the last zero remains if k is odd). As a result, we get a new element b ∈ S; in fact the following operations are performed:
The value of the jump can be adjusted by selecting the length of the zero fragment. Similarly, a descent along the sequence is carried out, but with the use of the ⊖ operation. We can write the last expression in the following form:
In conclusion, we note that the interactive service software does not use the server part. To speed up the calculations it was decided to abandon the file processing and databases, so the directory with the reference elements is designed as a script that connects to the programs during calculations.