Chapter 2

Search Algorithms

I have developed two recursive algorithms for use in searching for Euler representations. The first tries to find any representation, with an upper limit on the length, and will immediately halt as soon as it finds one, though this may not be an Euler representation. The second performs an exhaustive search for Euler representations. This means that a solution is guaranteed to be found, though the execution time may be prohibitive.

Decomposition Algorithm

This algorithm tries to decompose a number into a sum of powers of maximum allowable length, and is guaranteed to find a solution if it exists. It is preferable to any other method for low powers up to about 12.

The decomposition algorithm BREAKSUM has 4 parameters k, t, z and d that change with each step of the recursion. Additionally there are global variables n, s and l. BREAKSUM is used to find a representation of t as the sum of at most k powers with exponent n. The variable z is largest integer that may be used in the representation at a particular level, d is the recursion level, or depth, and l is an optional value at which to start the first integer variable. The variable global s is the indicator of success.

The initial value of s is 0, as is the seed value of d. The main tactic is to run through the possibilities for the largest element in a solution, subtract this from the running total t, and then try to decompose the remainder into k-1 powers, repeating this recursively until we bottom out at k = 1 or find a solution earlier. It is a feature of the algorithm that the sequence of elements is monotonically decreasing, except perhaps for the last element, as we shall see. The value of z at any step of the recursion is the maximum value allowed for the largest element, and is just the current value of the previous recursion. The seed value of z depends on the situation. In the case that t = bⁿ for some base b, z would normally be set to b-1, and in the case that t is a general integer, z would normally be set to [].

The algorithm, in generic pseudocode, is as follows.

procedure BREAKSUM(k, t, z, d)

endprocedure BREAKSUM

The first part of the algorithm deals with the end point of the recursion when k = 1 and either t is an nth power or not. If so, then the success switch s is set to 1. Either way, control is immediately passed back up to the previous level of recursion. It is also possible that at some intermediate depth, t will be an nth power. Again, s is set to 1 before backing up the recursion. At each recursion level, the algorithm loops through the range of possibilities for the largest element. In the above code, the loop counter z1 is incremented only if we have not yet found a solution. The condition here is not important to the performance of the algorithm but is left in for completeness.

Where I have used the phrase ‘store z1 at position d’, there are two possibilities in actual implementation. The first is to store z1 at position d in a solution table or array, so that if a solution is found, the elements of this array may be inspected or displayed. The other possibility, which is useful to viewing the progress of the algorithm, is to display z1 at position d on a screen. When k is large, it is often sensible to display z1 only if d is small. Since every set of seed values will perform slightly differently, the limit on d for display purposes may be built in as a separate global variable.

The decomposition algorithm is "bottom-up" as it searches for the sequentially smallest possible representation first. The next algorithm uses a "top-down" approach.

Construction Algorithm

The basic version of this algorithm is guaranteed to find an Euler representation for any input power in terms of sum of lesser like powers. It consists of an enhanced exhaustive search, using intermediate values as effective loop cut-offs. However, by its nature, it is impractical for all but the smallest bases, and it is more widely effective in modified form as a provider of estimates to restrict further searches by other means. In certain circumstances, these estimates are sometimes very tight, or even best possible, and taking only a tiny fraction of the time that the unmodified algorithm would be expected to take.

The general approach is to consider x^m as a sum of the form

x^m = n_x-1 (x-1)^m + n_x-2 (x-2)^m + ..... + n₂ 2^m + n₁ (2.1)

so that a recurring formula may be used with an iterative loop on the ni that begins at the largest possible value and drops to 0. The recurrence is halted at i = 2 since we can directly calculate the best representation using only twos and ones. There are several different ways to introduce modifications, one of which is the early abort strategy mentioned in Chapter 1. I will expand on these after presenting the algorithm.

The procedure BUILDSUM has 3 parameters a, b and c that change with each step of the recursion. In this case, rather than only manipulating these parameters, the procedure returns a value, which is basically the Euler length of an intermediate value. Additionally, there are global variables n and d. Optional global variables are f and g. There are also a number of local variables. BUILDSUM is used to find Euler representations of a with powers of exponent n. The variable b is the current base value, i.e. x-1, x-2, etc. above and c is the running total of the n_i. The variable d is the current best estimate for the Euler length, and if the algorithm is implemented in an interactive environment such as UltraBASIC, its value can be queried at any time. The variable f is a fixed value at which we wish the algorithm to halt and g is a loop iteration cap whose use will be explained shortly. The initial value of d is set to t as a first (and very bad) estimate, the seed value for b is x-1 and for c is 0.

The algorithm in pseudocode is

procedure BUILDSUM(a, b, c)

local i, j, k, l, m

if b = 1 then

endif

i = trunc(a / bⁿ)

if b = 2 then

endif

k = a

if c > d then

endif

if i > (d - c) then

endif

* m = 1

while i ³ 0 * and m £ g

endwhile

return(k)

The basic algorithm consists of every line above that is neither in square brackets nor marked with an asterisk.

The first part of the algorithm deals with the end point of the recursion at b = 2, for which there is only one possible Euler representation, obtained by using as many powers of 2 as possible and then adding in the difference as powers of 1. The pathological case b = 1 is included for completeness.

In the basic method, the sum of the ni is passed down through each recurrence and used to compare against the absolute current best estimate. If this sum c is in excess of the current best d, there is no need to continue with that particular level of recursion, and if not, then the value d-c may be used as a loop cap. Possible paths through the search space ignored in this way would never have yielded an improved result.

The early abort is introduced by the code segment s4 and occurs when the current estimate within the loop is poorer than the previous. The while loop is then exited and no other smaller ni is considered. A slight amendment consists of halting each while loop at the value 1 instead of 0. This can often, though not always, substantially speed up the algorithm. Since the set of possible paths is altered, in particular reduced in size, in most cases the results obtained here are the same or poorer than before. However, there are occasional successes, and the improvement in speed justifies its use. It should be noted that the amendment only works to a given limit on x for each power m, since the requirement that every number less than x is involved at least once becomes too restrictive eventually.

An additional restriction, which again alters the set of possible paths and which can be applied with or without the early abort, is to place a cap value on the number of iterations of the loop, namely variable g. The code associated with this is identified above with an asterisk. The value of this cap is subject to trial and error, but a reasonable maximum, above which execution times are poor, is + 1. For small x (dependent on m), this restriction can be used without the loop abort mechanism to give improved estimates, as is shown in Appendix B. For intermediate x, this restriction will often provide substantial improvements over previous results with the loop abort back in place.

Another variation is provided by removing the loop cap and letting variable i run all the way down from its initial setting of . Although slower than the basic method, it will, when combined with one or more of the suggested modifications, change the search space and occasionally produce an improved estimate.

Since the algorithm is exhaustive, it will not halt when it finds the Euler representation, but will keep looking until every possible path in its search space has been considered. In order to view progress, code segment s1 can be used to display the most significant values of n_i currently being considered. Additionally, code segment s3 dumps intermediate values for inspection. In order to obtain a solution for a particular length f, presuming that the existence of one has been assured by a previous run, code segment s2 can be used to halt processing as soon as the current best matches f. The most significant values of the solution may then be read off the screen. Alternatively, the BREAKSUM algorithm may now be used.

Note that for small powers m, as the base x increases, there comes a point when the bare-bones algorithm for finding Euler representations becomes faster than any of the methods used to obtain estimates.

Also note that the possibility of going up through the iteration loop from 0 upwards, rather than going down, was considered, but ultimately ignored as tests implied that results are generally poorer when this direction is used, and take longer to obtain.

URL : www.glasgowg43.freeserve.co.uk/chapter2.htm