-In general, we formulate the problem of extracting n-th order roots from a language as follows: for a given language A and a given nN it is required to find all the languages B, such that A = Bn. This theoretical problem is closely related to the practical task of decoding messages, where it is necessary to find a partition of the encoded message into elementary codes that correspond to certain characters of the original alphabet. We previously found a solution to the problem of extracting n-th order roots for languages of a special kind, which is containing all the possible words of the length from nn1 to nn2 (n1 n2). We reduced the problem under consideration to a knapsack problem and solved it by the method of software implementation of the algorithms proposed in the article. We found out that the number of roots depends on the values of n and k, where k is the cardinal number of the set {n1, n1+1,..., n2}. We obtained quantitative estimates of the number of n-th power roots for different values of n and k. For n = 2, the sequence of the number of square roots from the language coincid with the sequence published on the website of the online encyclopedia of integer sequences http://oeis.org/ A191701. In binary lunar arithmetic, this sequence is the number of binary numbers x of length k such that x2 has no zeros. In the article, we established and theoretically proved the correspondence between operations in binary lunar arithmetic and in the ring of polynomials with integer coefficients. Based on the established correspondence, we developed algorithms that allows us to solve both the special problem of finding roots from a language and the more general knapsack problem using operations in binary lunar arithmetic. We compared the software implementation of the proposed algorithm with the well-known classical alternative solutions to the knapsack problem. Using the discrete Fourier transform, we were able to improve the asymptotic complexity of the original algorithm.
American scientists D. Applegate, M. Lebrun, and N. J. A. Sloane introduced the concept of “lunar arithmetic” in [1], and originally they used the term “dismal arithmetic”, subsequently replacing it with a less pessimistic “lunar arithmetic”.
In the so-called lunar arithmetic, we replace the addition and multiplication of numbers by the operations of calculating the maximum and minimum, respectively. For example, 2 + 7 = 7, and 27=2. With multi-digit numbers, the addition operation is performed by columns, i.e., a maximum is selected in each column. For instance 6179 + 348 = 6379. The rule for multiplication of two multi-digit numbers is that the first number multiplies every digit of the second number and then the results are added together, i.e., we select the maximum in each digit (column): 3 3
X
You can learn more about the features of lunar arithmetic in [1]. We are most interested in the binary case when operations on numbers are performed according to the rules formulated above, but the numbers belong to the set {0, 1}.
In the past, in [
Let us introduce the necessary notations. Let М be a finite subset of the set of natural numbers, let - be an alphabet, possibly infinite. We consider languages of the form (М) containing all the i-digit long words over the alphabet , where iМ. We call the set М, defining the language (М), the set of indices. The solution to the problem of extracting all the roots was obtained for languages А=[t1;t2], containing all the words of length from t1 to t2 (t1 t2). Let us show two examples.
Example 1. Let be an arbitrary alphabet. We can extract 5 square roots from the language А=[2;14] with sets of indices {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 4, 5, 6, 7}, {1, 2, 4, 6, 7} and {1, 2, 3, 5, 6, 7}.
Let’s consider, for example, the language B=(М), where М={1, 2, 4, 6, 7}. We can show, that B2=A. The multiplicative operation here is concatenation. Since language B contains all 1-digit long words, language В2 contains concatenations of 1-digit long words, that is, all 2digit long words. Similarly, language В2 contains all words of length 4, 8, 12, and 14. We can get all the 3-digit long words by concatenating words of length 1 and 2 (1, 2М), we can get all the 5-digit long words by concatenating words of length 1 and 4 (1, 4М), and so on for the remaining natural numbers from the interval [2, 14].
Example 2.
Let us find all the cube roots from the language А=[27;42].
Obviously, the set M1={9, 10, 11, 12, 13, 14} defines a cubic root В=[9;14] from А. Similarly to the example 1, we can verify that the set М2 = {9, 10, 13, 14} defines another cube root from the language А. Therefore, the roots will be also two other languages with sets of indices M3={9, 10, 11, 13, 14} and M4={9, 10, 12, 13, 14}.
In general, the n–th root from the language А=[t1;t2] is extracted successfully if and only if t1 and t2 are divisible by n. Let M be a subset of the set of natural numbers {n1, n1 + 1, …, n2}, where n1=t1/n, n2=t2/n. The language B=(М), containing all words of length aj, ajМ, is an n‒th root from the language А if and only if the condition is satisfied: + (i) (n n1 i n n2 i = a1 + a2 + … + an), (1) where a1, a2, …, an are some elements from М (not necessarily different).
The task of checking condition (1) is equivalent to the specific case of the unlimited knapsack problem. We can solve this problem by the method of dynamic programming, finding the answer in polynomial time. Condition (1) is obviously satisfied for the set {n1, n1 + 1, …, n2} and corresponds to the trivial root В=[n1,n2], containing all words of length from n1 to n2. Verification of condition (1) for other subsets of the set {n1, n1 + 1, …, n2} was carried out by the method of a software implementation of well-known algorithms for solving the unlimited knapsack problem. Table 1 shows the results of the program, i.e., the number of n-th roots from languages of the form А=[t1;t2] for some n and k (k = n2 – n1 + 1). For k from 1 to 3, the values are 1. In binary lunar arithmetic, this sequence is the number of binary numbers x of length k such that x2 has no zeros. In this paper, we will establish the reason for this coincidence, interpret our results in terms of lunar arithmetic, and apply the established relation to solve the knapsack problem.
Let the initial set be {0, 1}. In the binary case, the lunar addition (finding a maximum) corresponds to the disjunction, and the multiplication (finding a minimum) corresponds to the conjunction. Let us consider lunar operations over multidigit binary numbers. When adding in each column, select the maximum: 1011 + 101 = 1111. When multiplying, we follow the rule of multi-digit numbers multiplication in the lunar arithmetic shown above.
Thus, 1011 101= 101111 (when summing by columns we find the maximum).
We see that the original vector 1011, when multiplied by 1, remains unchanged, shifting to the left by the position of this bit. This multiplication is similar to a multiplication in the ring Z[x] of polynomials. If the original polynomial f(x) is multiplied by xi, then all its coefficients will remain unchanged, only i zeros will be added to the right, which corresponds to a shift of the coefficient vector f(x) by i positions to the left. We associate the binary vector 1011 with the polynomial x3+x+1 and vector 101 with the polynomial x2+1. We get:
(x3+x+1)1= x3+x+1=1011 (x3+x+1) x2= x5+x3+ x2=101100
Adding the coefficients at the equal powers, we have x5+2x3+x2+x+1=102111. In the polynomial ring, when calculating the coefficients at the equal power, we perform the usual addition, and in the lunar binary arithmetic if there is 1 in the column, the result is 1, if all the numbers are zeros, the result is 0. Thus, the following theorem is true.
Theorem 1. Let us compare the polynomial
anxn+an-1xn-1+…+a1x+a0 to the binary vector (an,an-1,…,a1,a0). When the mapping is set in this way, operations in binary lunar arithmetic correspond to operations on polynomials in the ring Z[x] with subsequent replacement of non-zero coefficients by 1.
Proof.
Without loss of generality, we consider two binary vectors a=(an,an-1,…,a1,a0) and b=(bn,bn-1,…,b1,b0) of the same length. Otherwise, we can add to the shorter vector zeros on the left. Then a+b=(an bn, an-1 bn-1,…,a1 b1, a0 b0) and 0 will be in the i-th position if and only if ai= bi=0. On the other hand, for the polynomials a(x)=anxn+an-1xn1+…+a1x+a0 and b(x)=bnxn+bn-1xn-1+…+b1x+b0, we have a(x)+ b(x)= (an+ bn) xn+(an-1+bn-1 )xn-1+…+ (a1+b1 )x+a0+b0 Since the initial vectors a and b are binary, the coefficients of the polynomial a(x)+ b(x) belong to the set {0,1,2}, moreover the coefficient xi equals 0 if and only if ai= bi=0. For this reason, after replacing all nonzero coefficients by 1, the coefficient vector of the polynomial a(x)+ b(x) is equal to the vector a+b.
The corresponding results for multiplication can be derived similarly.
We found the sequence for n = 2 on the website http://oeis.org/A191701, which, in turn, refers to the work [1]. D. Applegate, M. Lebrun and N. J. A. Sloane obtained this sequence for k from 1 to 41:
1, 1, 1, 1, 2, 3, 5, 9, 15, 28, 50, 95, 174, 337, 637, 1231, 2373, 4618, 8974, 17567, 34387, 67561, ... (2)
III.
BINARY LUNAR ARITHMETIC AND THE PROBLEM OF FINDING ALL THE ROOTS OF THE LANGUAGE
Next, we interpret the content of the sequence (1). According to the author’s terminology, this sequence represents the number of k-digit long binary vectors. The lunar squares of these vectors consist of all ones. The lunar square is the result of multiplying the vector by itself.
Example 3. Lunar squares of the following 5 vectors with the same length k = 7: 1111111, 1111011, 1101111, 1101011 and 1110111 are 1111111111111=1(13), therefore, the seventh term in the sequence (1) is 5. For all other 7-digit long binary vectors, the lunar square will contain zeros.
Let us move to the polynomial operations.
For instance, we associate the polynomial a(x)=x6 + x5 + х3 + х + 1 with the fourth vector a=1101011. After multiplying the polynomial with itself, we get (x6 + x5 + х3 + х + 1) (x6 + x5 + х3 + х + 1) = =c12x12 + c11x11 +c10x10 + c9x9 + c8x8 + c7x7 + c6x6 + + c5x5 + c4x4 + c3x3 + c2x2 + c1x + c0.
Following the rule of theorem 1, we consider all non-zero coefficients equal to 1.
c0= a0 a0=1, c1= a0 a1+ a1 a0=1+1=1, c2= a0 a2+ a1 a1+ a2 a0=0+1+0=1, and so on.
We get c0= c1=…= c12=1.
The power xi can be represented as the sum of the powers of the factors, that is as a sum of powers of a polynomial a(x), if and only if this power is present in the product a(x)a(x). For some, not necessarily different, j and k we obtain i=j+k, where j, k{0, 1, 3, 5, 6}.
In the polynomial a(x)a(x), all the coefficients ci are nonzero, hence any i from 0 to 12 can be represented as the sum of two (not necessarily different) numbers from {0, 1, 3, 5, 6}.
Let us recall that the problem of extracting all the roots from the language А=[t1;t2] is reduced to the same question. In the example 1 we extracted 5 square roots from the language А=[2;14] with the sets of indices: {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 4, 5, 6, 7}, {1, 2, 4, 6, 7} and {1, 2, 3, 5, 6, 7}. We associate these subsets of the set {1, 2, 3, 4, 5, 6, 7} to its binary characteristic vector (1, 2, …, 7), so we obtain 5 binary 7-digit long vectors from the example 3.
Let us interpret the results obtained in Table 1 in terms of lunar arithmetic.
It is not difficult to verify that the second sequence of the number of cubic roots from languages of the form А=[t1;t2] coincides with the number of k-digit long binary numbers, whose lunar cubes consist of ones.
In particular, for k = 6, the lunar cubes of four vectors: 110011, 111011, 110111, and 111111 give a unit vector (it will be 16 -digit long). These vectors are characteristic vectors for the sets of indices from Example 2.
In the general, the following theorem is true.
Theorem 2. Let be an arbitrary alphabet. Let k be the cardinal number of the set {n1, n1+1,..., n2}, i.e. k = n2 – n1 + 1. Let M be a subset of the set {n1, n1 + 1, …, n2}, and = (1, 2, …, k) be the binary characteristic vector of the subset M. The language В=(М) is a n‒th root from the language А=[nn1;nn2] if and only if in binary lunar arithmetic n has no zeros.
The Theorem 2 provides another method to verify whether a subset М is a set of indices for some root from a language of the form А=[t1;t2].
IV.
THE KNAPSACK PROBLEM
The classical knapsack problem in general can be formulate as follows: given a set of items, each with a weight and a value, select a certain subset of objects so that we get maximum total cost, subject to the restrictions on the total weight.
The unlimited knapsack problem is a generalization of the classical problem when any item can be taken any number of times. We consider a special case of this problem when the value of the item is a natural number, and equal to its weight. Therefore, we may not take into account the cost of items, but only their weight. We also add the condition that the taken items must be equal exactly M. We formulate this problem in mathematical language.
The knapsack problem 1. Given N items. The capacity of the knapsack is W, M - the number of items to be taken, and the natural numbers w1, w2, …, wN. - are weights corresponding to the items. Find a set of values x1, x2, …, xN, where xi is the number of taken items of a certain type, and such that: 1. x1 w1 + … + xN wN ≤ W; 2. x1 + … + xN = M; 3. x1 w1 + … + xN wN has a maximum.
Note. All the weights of objects are different. If there are any objects with the same weight, then we will always take from them only some specific one. Such an assumption will not change anything in problem 1, since any item can be selected any number of times.
Algorithm
Step 1. Create a polynomial = 1 + 2 + ⋯ + according to the selected set of weights ŵ= {w1, w2, …, wN}.
Step 2. Associate the polynomial y with the binary vector u of its coefficients. Then, in the vector u, for all ui, the following condition holds ui=1, if i ŵ; otherwise ui=0.
Step 3. Raise the vector u to the power M in the lunar binary arithmetic. We get the binary vector z = uM.
In the vector z, all nonzero zk denote that there exists a set of exactly M objects, not necessarily different, whose sum of weights is k. This statement justifies the next step.
Step 4. Choose the maximum number k satisfying the conditions: k W and zk≠0.
Step 5. Find the linear combination methodx1 w1 + … + xN wN=k using the backstepping.
Example 4. Given 4 items with weights 2, 3, 6, 7, and the capacity of the knapsack W=17. Find exactly 3 items.
Step 1. Create the polynomial = 2 + 3 + 6 + 7.
Step 2. Associate the polynomial y with the binary vector u=(11001100) of its coefficients.
Step 3. Compute u3 in the lunar arithmetic, we obtain: u2= (111011101110000), or (by the theorem 1) 2 = 14 + 13 + 12 + 10 + 9 + 8 + 6 + 5+ 4. u3= (111111111111111000000) = (11606).
Step 4. k=17.
Step 5. 17=10+7; 10=7+3. Hence, 17=7+3+7, so that we need to choose 2 items weighing 7 and one item weighing 3.
There is a second solution 17=14+3; 14=7+7. Hence 17=7+7+3, which, in fact, coincides with the first solution.
We evaluate the asymptotic complexity of this algorithm. Let us denote by wmax = max{ wi | 1 ≤ i ≤ N} the weight of the heaviest item, that is, the maximum power of the polynomial y. Then wmax ∙ M is the maximum power of the polynomial yM=z. The latter operation can be implemented in a naive way, which involves sequentially calculating the powers of y from 2 to M, or using the “binary power raising” technique, which allows raising any number to the power of n in O (log n) multiplications instead of n multiplications in the usual sequential multiplication. Using this technique, the asymptotic complexity of this algorithm is O ((wmax ∙ M )2 ∙ log (M )), where ( wmax ∙ M )2 is the algorithmic complexity of multiplying two polynomials, log M is the algorithmic complexity of binary exponentiation.
We can use the Fast Fourier Transform algorithm (FFT) [4, 5] to multiply two polynomials. To multiply two polynomials in binary lunar arithmetic, based on Theorem 1, it suffices to multiply the polynomials over the standard complex field and, after obtaining the resulting polynomial, change the coefficients that are greater than one by one. Multiplication of polynomials in binary lunar arithmetic using FFT has asymptotic complexity O (wmax · log(wmax)). Thus, it turned out to improve the asymptotic complexity of the original algorithm to O (wmax · log(wmax) · log(M)). We also note that FFT can be implemented using the parallel algorithm from [6].
V. COMPARATIVE ANALYSIS OF SOLUTIONS TO THE
KNAPSACK PROBLEM
A comparative analysis of the program execution time among various solutions to the problem 1 on the knapsack problem was carried out by the 2nd year master specialized in 01.04.02 “Applied Mathematics and Computer Science” A. I. Chesnokov. Testing was carried out on computing M-th power of random polynomials of power N. There are the restrictions on N and M in experiments:
Test 1 – N = 500, M = 500; Test 2 – N = 500, M = 1000; Test 3 – N = 1000, M = 500; Test 4 – N = 1000, M = 1000; Test 5 – N = 1500, M = 500; Test 6 – N = 1500, M = 1000; Test 7 – N = 2000, M = 500; Test 8 – N = 2000, M = 1000.
There were 7 different solutions to the knapsack problem 1 [7,8].
- Solution A is a solution using dynamic programming; - Solution B is a solution using dynamic programming using bitmasks;
- Solution C is a solution using the product of polynomials in lunar arithmetic. The product of polynomials is computed using the fast Fourier transform. The M-th power of a polynomial is computed in a naive way;
- Solution D is a solution using the product of polynomials in lunar arithmetic. The product of polynomials is produced using the fast Fourier transform. The M-th power of a polynomial is computed using binary exponentiation; - Solution E is a solution using the product of polynomials in lunar arithmetic. The product of polynomials is produced using the fast Fourier transform. The M-th power of a polynomial was raised using binary exponentiation. The parallel FFT algorithm was used [6]. Calculations are made on 2, 4, or 8 processors.
Testing was conducted on a cluster of CAFU, which has the following characteristics: - 20 computing nodes; - on each node there are 2 ten-core Intel Xeon processors and 64 GB of RAM;
- additionally installed mathematical coprocessors Intel Xeon Phi 5110P on the eighth node;
- The internal computer network for computing: Infiniband 56 Gb / s;
- FEFS network file system (Fujitsu Exabyte File System) with a capacity of more than 50 TB and a bandwidth of 1.67 GB / s (13.36 GB / s);
- cluster performance on the CPU in the LINPACK test 8.02 Tflops; on CPU + Xeon Phi 7.68 Tflops, cumulative 15.7 Tflops;
The results of the execution time of the programs are presented in table 2.
According to table 2, we can make a conclusion that the solution to problem 1 using FFT in binary lunar arithmetic and binary exponentiation is faster than the other solutions. The speed of the parallel FFT algorithm in all the tests increases noticeable, especially with the increasing number of threads (in some cases, significantly).
Let us summarize the results. In the theoretical part of the work, we established a relation between operations in binary lunar arithmetic and in the ring of polynomials with integer coefficients (Theorem 1). We also created an association between binary numbers x of length k for which xn does not contain zeros in binary lunar arithmetic and sets of indices of roots of the n-th power from a language of a special form (Theorem 2). A generalization of the problem of extracting the n-th root from a language of a special kind is a mathematical model of a special case of the problem of an unbounded knapsack problem (Problem 1). To solve this problem, we developed an algorithm based on lunar binary arithmetic.
We made the software implementation of the proposed algorithm in several variants, using optimization methods of calculations and parallel technologies. Table 2 gives us a chance to compare the solution obtained by the authors with other known solutions (solution A and solution B) of the unbounded knapsack problem.
The knapsack problem belongs to the class NP‒complete problems. This means that there is no polynomial algorithm to obtain the exact result (solution). The results presented in table 2 demonstrate that, despite this pessimistic fact, in some cases, a solution to such a problem can be obtained in seconds.
The results obtained in this research can be applied to solve
many problems related to the knapsack problem. In particular,
the problem of estimating the number of different cyclic codes
with given parameters was solved in [9] using this method.
Some additional algorithms were proposed in [
S.Yu. Korabel’shchikova, A.I. Chesnokov and A.G. Tutygin, “On primitive roots from languages of a special type,” Proceedings of the