The problem statement from the Ole Miss Problems of the Week page is:

A guy walks into a 7-11 store and selects four items to buy. The clerk at the counter informs the gentleman that the total cost of the four items is $7.11. He was completely surprised that the cost was the same as the name of the store. The clerk informed the man that he simply mutiplied the cost of each item and arrived at the total. The customer calmly informed the clerk that the items should be added and not multiplied. The clerk then added the items together and informed the customer that the total was still exactly $7.11.

What are the exact costs of each item?

Since this is an early problem — in fact, it is the
*first* of the Problems of the Week! — there is a certain
amount of archaism in the wording.
We assume that the costs are expressed in dollars and fractions of
dollars, units are dropped during the multiplication (otherwise the
product would have units dollars to the fourth power),
“cost” is used as a synonym for “price,” the
customer is a “customer” and not a “guy” or
“man” or “gentleman,” and so forth.

So the problem reduces to finding four quantites — P, Q, R, and S, say — such that:

P, Q, R, S are in {0.01, 0.02, ...}

P + Q + R + S = 7.11

PQRS = 7.11

We can rescale this problem to make the units of the prices cents
(units) rather than dollars.
This involves multiplying all the price quantities by 100 — and
multiplying the product of the prices by 100^{4}, or
100,000,000.
Also, without loss of generality, we can assume P is the smallest
price, Q is the next smallest, and so forth.
The revised Diophantine problem is then:

P, Q, R, S in {1, 2, 3, ...}

P __<__ Q __<__ R __<__ S

P + Q + R + S = 711

PQRS = 711000000

If P is the smallest of the prices, then the sum is at least as great as 4P, and the sum is 711, so P can be no larger than 711/4 = 177.75. Since we are limited to integers, P is at most 177. P therefore is between 1 and 177, inclusive. Similarly, Q is the smallest of the three remaining prices, and the three remaining prices add up to 711 - P, so Q is at least P and at most (711 - P) / 3. Similarly, R is at least Q and at most (711 - P - Q) / 2. And S is (711 - P - Q - R).

This is two equations in four unknowns — which is underdetermined. Substituting 711-P-Q-R (from the addition equation) into the multiplication equation yields:

(PQ)R^{2} + (PQ^{2} + P^{2}Q - 711PQ)R + 711000000 = 0

which can be solved for R in terms of P and Q. P and Q are not further determined.

However, these are Diophantine equations — all the quantities involved are integers. Frequently this condition, which is one difficult to handle analytically, is enough to force a solution. There is really not a lot one can do with Diophantine equations other than plug lots of possibilities into the equations and hope some possibility works.

And that sounds like a job for a programmable calculator!

Our program is given below, or as a text file with .CAT file contents. As always, semicolon (“;”) indicates a comment that is not to be entered into the calculator.

Program P042996 (160 bytes):

; Variables: ; A is limit on P ; B is limit on Q ; C is limit on R ; D is computed value of S ; E is attempted value for P ; F is attempted value for Q ; G is attempted value for R ; Symbols: ; -> is assignment arrow ; = is equality comparison relational ; _ is display triangle Int (711/4)->A ; Find limit on P For 1->E To A ; Loop through all possible P values Int ((711-E)/3)->B ; Find limit on Q For E->F To B ; Loop through all possible Q value Int ((711-E-F)/2)->C; Find limit on R For F->G To C ; Loop through all possible R values 711-E-F-G->D ; Find S value so P + Q + R + S = 7.11 If EFGD=711000000 ; Test whether PQRS = 7.11 Then E/100_ ; If so, report P F/100_ ; Report Q G/100_ ; Report R D/100_ ; Report S IfEnd ; [End of test whether PQRS = 7.11] Next ; [End of loop through R values] Next ; [End of loop through Q values] Next ; [End of loop through P values] "Done" ; Report done

We run the program, and about 30 hours later, the calculator reports:

1.2 1.25 1.5 3.16

About an hour after that, the calculator reports:

Done

So the prices are $1.20, $1.25, $1.50, and $3.16, and that is the only set of prices that will work.

Just out of curiosity, we decide to benchmark the calculator against a PC. We can write the same search algorithm in the C language as follows:

# include <stdio.h> # include <stdlib.h> # define iMAGIC 711 int main (void) { int iA, iB, iC, iD; long lProd; for (iA = 1; iA <= iMAGIC / 4; iA ++) { for (iB = iA; iB <= (iMAGIC - iA) / 3; iB ++) { for (iC = iB; iC <= (iMAGIC - iA - iB) / 2; iC ++) { iD = iMAGIC - iA - iB - iC; lProd = (long) iA * (long) iB * (long) iC * (long) iD; if (lProd == 711000000l) { fprintf (stdout, "%d %d %d %d\n", iA, iB, iC, iD); } } } } fprintf (stdout, "Done.\n"); return EXIT_SUCCESS; }

This program, compiled with the Borland’s Turbo C++ version 3.0 (a real mode DOS C compiler), gives the same answers:

120 125 150 316 Done

The numbers here are the prices in cents, so we interpret these prices as $1.20, $1.25, $1.50, and $3.16. The answers are the same as before. However, these answers are produced in about one second on a 300 MHz Pentium II computer.

Hmm. Thirty hours on the calculator, one second on the computer. That is a factor of about 100,000 difference in speed between the calculator and a not particularly powerful computer. From this comparision, we learn something very important: we learn to never again benchmark the calculator against a real computer.

Still, even though we have our answer twice, there is something inherently unsatisfying about a simple search that takes 30 hours on the calculator. There must be some more clever way of solving this problem that takes less time.

There are two constraints that we need to meet simultaneously. The first is that sum of the four numbers is 711. The second is that the product of the four numbers is 711000000. We generated numbers which met the first condition, and then checked to see whether they met the second condition. Suppose we generate instead numbers which meet the second condition, and check to see whether they meet the first condition.

We can factor 711000000 easily enough.
We get 711000000 =
2^{6}3^{2}5^{6}79^{1}.
Any subset of these factors will divide 711000000; and if we use
all of these factors among four divisors, we will have four divisors
whose product is 711000000.
So we can generate divisors by taking these factors and arranging
them into four groups.
Each divisor will be the product of the factors in its group.

What we can do, then, is to generate groups of known factors.
This is similar to generating a partition of an integer —
splitting an integer into groups which sum to the integer.
We need to split the six 2s, for example, among the four groups.
Similarly, we need to split the two 3x, six 5s, and one 79.
The various 2s are indistinguishable.
It does not matter which 2s go into any group, only the number of 2s
matter.
Also, the various groups are not ordered.
Putting, say, 2^{3}5^{1} into the first group
and 3^{1}79^{1} into the second group is the same as
putting 3^{1}79^{1} into the first group and
2^{3}5^{1} into the second group.
We need to represent these various combinations of factors, and settle
on an order so we can avoid duplication through reordering.

An obvious way to represent the factors in a group is with a four
digit number.
The digits will represent, in order, the number of 2s, 3s, 5s, and 79s
in the divisor.
We list divisors in decreasing order by their four digit number
representations.
We will call this four digit number the *factor pattern* of the
divisor.

We will generate the divisors from the first to the fourth, and backtrack when we find we have generated a set that does not work. For each divisor, we keep the factor pattern for the factors we need to accommodate in that and following divisor, and the factor pattern actually accommodated in that divisor. We also keep the value of the divisor.

Suppose we know that factor pattern, *abcd* (which represents
2^{a}3^{b}5^{c}79^{d}),
needs to be allocated among a set of divisors, and the factor pattern
actually chosen for the first divisor is *efgh*.
Then *a*-*e* 2s need to be allocated among the remaining
divisors, *b*-*f* 3s need to be allocated among the
remaining divisors, and so forth.
We want to subtract the individual digits of the two factor patterns
from one another to get the factor pattern of the factors remaining.
We note, however, that there will be no carries: a carry would mean
we are using more of a factor in a group than we needed, and we will
not do that.
As there will be no carries, we can simply subtract the two numbers:
*abcd*-*efgh* is the factor pattern that need to be
allocated among the remaining divisors.

However, we cannot necessarily use the difference as the factor
pattern for the first of the remaining divisors.
We want to make sure the factor patterns are in decreasing order.
So if *ijkl* is the factor pattern to be allocated among a set
of factors, and the previous factor pattern is *efgh*, the
greatest factor pattern we can use is the leading digits of
*efgh* and the trailing digits of *ijkl*.
We can switch from the *efgh* digits to the *ijkl*
digits when the first *ijkl* digit is strictly less than the
corresponding *efgh* digit.

That sounds like a relatively complicated operation, so we put it into a subroutine.

Program P042996A (125 bytes):

; Variables: ; A is the factor pattern of the previous divisor (input, destroyed) ; B is factor pattern for factors to be allocated starting with the ; current divisor (input, destroyed) ; C is the largest possible factor pattern for the current divisor ; (output) ; D is a digit counter (destroyed) ; Symbols: ; -> is assignment arrow ; >= is greater than or equal relational ; / is division operator 0->D ; Zero the digit counter While A>=1 Or B>=1 ; Loop while there are any digits of any input 1+D->D ; Increment the digit counter A/10->A ; Shift the digits to the right B/10->B ; of the decimal point WhileEnd ; [End of loop while there are any digits] 0->C ; Zero the resulting pattern While D>0 ; Loop through the digits to generate 10A->A ; Shift the digits of the two inputs 10B->B ; to the left of the decimal point 10C->C ; Make room in the resulting factor pattern If Int A>Int B ; If the allocation is less than the previous Then B->A ; then shift over to using the allocation IfEnd ; [End of allocation vs previous test] C+Int A->C ; Put in the appropriate digit Frac A->A ; Remove the digits from the Frac B->B ; two inputs D-1->D ; Note a digit has been handled WhileEnd ; [End of loop through digits to generate]

Now, when searching for the factors to put into a divisor, we can either start with no factors and include them until we have reached the maximum set, or start with the maximum set and then take them away until we reach no factors. The program above tells us what the maximum set is. However, we are also generating factor sets in decreasing order, so starting with no factors means all subsequent factors will also have no factors. Starting at a place that cannot possibly be the solution seems a poor idea, so we will start each divisor with a maximum set of factors, then remove them (that is, push them into the following divisors). We therefore need a way get the next lower factor pattern from a given factor pattern, where the set of factors available is given by another factor pattern. Basically, we want to subtract 1 from the factor pattern.

If the lowest digit of the factor pattern is non-zero, we can indeed subtract 1. If it is zero, however, we want to do the same thing as we do in decimal arithemetic: set it to its maximum value, and subtract 1 from the next digit over. If the next digit over is also zero, we set it to its maximum and subtract 1 from the next digit over, again. The maximum value, though, is not 9 as it is in decimal arithemetic. Instead, the maximum value is given by the factor pattern of the available factor patterns. What we wind up with is a factor pattern that decreases the rightmost non-zero digit of the original factor pattern by 1, and copies the digits from the factor pattern of available factors into what was the rightmost zero digits.

We also do not want to change the number of digits in the factor pattern when we “subtract one.” We are generating factor pattern in decreasing order, and removing the leftmost factor from a divisor would mean no following divisor could have that factor, and so the factor would never be handled.

This, too, sounds like a fairly complex operation, so we put it into a subroutine.

Program P042996B (96 bytes):

; Variables: ; A is factor pattern for factors to be allocated starting with the ; current divisor (input) ; B is factor pattern for current divisor (input), new factor ; pattern for current divisor (output) ; C is digit mask (destroyed) ; Symbols: ; -> is assignment arrow ; (-) is unary negation operator ; / is division operator ; = is equality relational If B=0 ; If the factor pattern is empty Then (-)1->B ; note there is no lesser value Else 1->C ; Otherwise, initialize shift factor While 0=Frac (B/(10C));While the low order digits are zero 10C->C ; increment the shift factor WhileEnd ; [End of while the low order digits are zero] If B=C ; If the factor pattern is just a 1 somewhere Then (-)1->B ; there is no lesser value desired Else B-C+CFrac (A/C)->B; Otherwise, generate the factor pattern IfEnd ; [End of factor pattern is just a 1 test] IfEnd ; [End of factor pattern empty test] B ; Return value in Ans also

We will want to check that the sum of divisors is 711. This implies the need to know not only the divisors’ factor patterns, but their values. We can compute the value of a divisor from its factor pattern relatively easily, but this operation, too, sounds like a good candidate for a subroutine.

Program P042996C (110 bytes):

; Variables: ; A is the factor pattern for the divisor (input, destroyed) ; B is the divisor value (output) ; C is exponent (destroyed) ; Symbols: ; -> is assignment arrow ; / is division operator ; ^ is exponentiation operator 1->B ; Initialize divisor value A/10->A ; Extract exponent for 10Frac A->C ; powers of 79 (79^C)B->B ; Multiply in powers of 79 (Int A)/10->A ; Extract exponent for 10Frac A->C ; powers of 5 (5^C)B->B ; Multiply in powers of 5 (Int A)/10->A ; Extract exponent for 10Frac A->C ; powers of 3 (3^C)B->B ; Multiply in powers of 3 Int A->C ; Extract exponent for powers of 2 (2^C)B->B ; Multiply in powers of 2

Part of our search for a solution will be recognizing and reporting the solution. When the sum of the divisors is 711, we will report the solution. In order to recognize that the sum of the divisors is 711, however, we need to know where the divisors are. We need three related sets of values: factors to be allocated, factors actually used, and divisors resulting from factor use. We decide to put the factor patterns of the factors to be allocated into List 1, the factor patterns of the factors actually used into List 2, and the divisor values into List 3. Recognizing and reporting the solution then becomes a straightforward subroutine.

Program P042996D (67 bytes):

; Variables: ; List 3 is the divisor values ; A is the divisor value index (destroyed) ; Symbols: ; = is equality relational ; -> is assignment arrow ; _ is display triangle If Sum List 3=711 ; If this is a solution Then "Solution" ; then label it so For 1->A To Dim List 1;Loop through divisors List 3[A]_ ; Report the divisor Next ; [End of loop through divisors] IfEnd ; [End of solution test]

Finally, it is wise to abandon a search pattern as soon as we know it cannot provide a solution. (We already applied this logic when finding the “next lower” factor pattern: if a needed factor would disappear, we reported no “next lower” factor pattern.) We know a divisor pattern where the first few divisors exceed 711 cannot possible succeed. So we put this test, too, into a subroutine:

Program P042996E (44 bytes):

; Variables: ; List 3 is the divisor values ; A is set to 1 if the sum of divisors is possible, 0 otherwise ; B is the sum of the divisor values (destroyed) ; G is the number of divisors (input) ; Symbols: ; -> is assignment arrow ; <= is less than or equal to relational Sum(List 3[A],A,1,G,1)->B ; Sum the first few elements of the list B<=711->A ; If it is less than or equal to 711, okay

Finally, now, we are ready to write our program. There are three major things the program needs to do: given divisors 1 through G, generate the initial value for divisor G+1; given a divisor, generate the next divisor; and test whether it is done. The resulting program is as follows.

Program P0429961 (355 bytes):

; Variables: ; List 1[k] is the factor patterns of factors that are to be used in ; divisor k and later ; List 2[k] is the factor pattern of factors actually used in ; divisor k ; List 3[k] is the value of divisor k ; A is utility ; B is utility ; C is utility ; D is utility ; G is the index of the divisor being dealt with ; Symbols: ; -> is assignment arrow ; >= is greater than or equal to relational ; => is conditional jump ; = is equal to relational ; <> is not equal to relational ; < is less than relational Seq(0,A,1,4,1)->List 1 ; Initialize factor pattern to be used list List 1->List 2 ; Initialize factor pattern actually used list List 1->List 3 ; Initialize divisor value list 6261->A ; Get factor pattern to be used overall A->List 1[1] ; Make it factor pattern to be used by factor 1 and ; subsequent factors A->List 2[1] ; Start factor 1 at it, also Prog "P042996C" ; Compute the divisor value for it B->List 3[1] ; And set the divisor value of divisor 1 1->G ; Set divisor 1 being used ; ; Label 0 ; Divisors 1 through G have been generated; either test the divisors ; generated, or generate another divisor ; Lbl 0 G>=4=>Goto 1 ; If have 4 divisors, check them out List 2[G]->A ; Get factors actually used in previous divisor List 1[G]-A->B ; Get factors remaining to be used in this and ; subsequent divisors G+1->G ; Increment the divisor count B->List 1[G] ; Set the factors remaining for this and subsequent ; divisors Prog "P042996A" ; Generate the maximum factor pattern C->List 2[G] ; Set the maximum factor pattern as the initial ; factor pattern for this divisor C->A ; Get the divisor value Prog "P042996C" ; for this factor pattern B->List 3[G] ; Store the divisor value Prog "P042996E" ; Check whether the current divisor values are ; already infeasible A=1=>Goto 0 ; If feasible, continue generation G=4=>Goto 2 ; If so, and we have all 4 divisors, decrease the ; factors of divisor 3 (decreasing the factors of ; divisor 4 might make the sum okay, but would ; not make the product okay) Goto 3 ; If we do not yet have all 4 divisors, decrease ; the current divisor (we might catch up on ; factors later) ; ; Label 1 ; Divisors 1 through 4 have been generated ; Factors may remain unhandled ; The sum does not exceed 711, but need not equal 711 ; Lbl 1 List 1[G]<>List 2[G]=>Goto 2 ; Check whether all factors were handled; if not, ; decrease factors in divisor 3 Prog "P042996D" ; See if we have a solution; if so, report ; ; Label 2 ; Divisor G has been exhausted; decrease factor pattern of divisor ; G-1 ; Lbl 2 G-1->G ; Decrease the active level G=0=>Goto 4 ; If we just popped out of all levels, we are done ; ; Label 3 ; Decrease the factor pattern of divisor G ; Lbl 3 List 1[G]->A ; Get factors to be handled at G and later List 2[G]->B ; Get G's current factor pattern Prog "P042996B" ; Decrement B<0=>Goto 2 ; If no further decrement possible, back up by one ; divisor B->List 2[G] ; Put new factor pattern into divisor G B->A ; Compute new divisor Prog "P042996C" ; value for divisor G B->List 3[G] ; Store new divisor value for divisor G Goto 0 ; Search for following divisors ; ; Label 4 ; All factor patterns have been attempted ; Lbl 4 "Done" ; Report done

Now, we run this program, and about two and one half hours later it reports:

Solution 120 316 150 125

Well, from thirty hours to two and a half hours is certainly an improvement. On the other hand, our generation is used to instant answers: the problems of the world solved in half an hour. Two and a half hours is simply too long to wait for this answer. How could we make this quicker?

Let us review the approaches we have already tried. Our first program, P042996, just generated sets of four numbers for which the sum was 711, then multiplied them together. It used no information about the product to be formed, and so generated numbers which did not divide the product to be formed. Our second program, P0429961 and its various subroutines, used almost the opposite approach: it generated sets of four numbers for which the product was 711000000, then added them together. However, it did use information about the sum required: when the first few divisors in a set of sequences added to more than 711, it abandoned those sequences. Since both sum and product information was used, and used as early in the process as possible, it seems unlikely that a more effective approach could be found. The problem with the second program, therefore, is that its basic operation — the bookkeeping involved with keeping the factors in the various divisors straight — takes too long. There certainly is a great deal of code implementing the various tests and operations involved with the bookkeeping. If we can replace the expensive bookkeeping with faster operations, we can speed the solution.

We can return to the first program’s approach — generating numbers that sum to 711 — and introduce information about the product. As long as we keep ourselves to arithemetic operations, and not moving factors from one divisor to another, the fundamental operations used will be rapid. From the original equations, we have:

P, Q, R, S in {1, 2, 3, ...}

P __<__ Q __<__ R __<__ S

P + Q + R + S = 711

PQRS = 711000000

We know that the equation P + Q + R + S = 711 means P is between 1 and
711/4, and Q is between P and (711-P)/3, and so forth.
But we also have PQRS = 711000000.
Using logic parallel to that in the summation case, we know P is the
smallest of P, Q, R, and S, so PQRS is at least P^{4}.
So P is between 1 and whichever of 711000000^{1/4} and 711/4
is smaller.
Also, P has to divide 711000000, as QRS = 711000000/P.
Similarly, Q is between P and the smaller of (711000000/P)^{1/3}
and (711-P)/3, and Q must divide 711000000/P.
R is then between Q and the smaller of (711000000/(PQ))^{1/2}
and (711-P-Q)/2, and must divide 711000000/(PQ).
Finally, S must be both 711-P-Q-R and 711000000/(PQR).
We can aim for both the proper sum and proper product by taking the
minimum of the upper limits for each iteration; and we can ensure
divisibility with an extra test.

We could once again use lists, this time keeping only the divisor value and the number of known divisors as state. However, the logic of setting and testing the number of known divisors, and taking different actions as different numbers of divisors are known, can be dispensed with by using nested loops. Further, accessing a plain variable is faster than accessing a list element. As we did not come up with an algorithm more deeply exploiting the structure of the problem, but instead are focusing on implementation speed, we will use nested loops with plain variables. We wind up with logic similar to the following pseudocode.

P_{max}:= min (int (711/4), int ((711000000)^(1/4)));forP := 1toP_{max}dobeginif(711000000modP) = 0thenbeginQ_{max}:= min (int ((711-P)/3), int ((711000000/P)^(1/3)));forQ := PtoQ_{max}dobeginif((711000000/P)modQ) = 0thenbeginR_{max}:= min (int ((711-P-Q)/2), int ((711000000/(PQ))^(1/2)));forR := QtoR_{max}dobeginif((711000000/(PQ))modR) = 0thenbeginS_{1}:= 711 - P - Q - R; S_{2}:= 711000000/(PQR);ifS_{1}= S_{2}thenbegin{display solution}endendendendendendend.

We can expect the addition, subtraction, multipication, and division operations to be very quick. The square root and cube root operations will be more expensive, but not exceedingly so. We can expect that a single root operation — figuring the limit beforehand — will be quicker than the alternative, using the power operator (or repeated multiplication) each time through the loop to see if the multiplicative limit has been exceeded. Overall, we can expect this approach to yield a somewhat faster implementation than the divisor approach of the second program. It will clearly not be the order of magnitude improvement that using both areas of knowledge — sum and product — gave us in going from the first program to the second, but it should be a noticeable improvement.

Translating the above Algol-like pseudocode into the CFX-9850G programming language gives us the following program:

Program P0429962 (306 bytes):

; Variables: ; A is work ; B is work ; C is P ; D is Q ; E is R ; F is S1 ; G is upper limit on P ; H is upper limit on Q ; I is upper limit on R ; J is quotient 711000000/P ; K is quotient 711000000/(PQ) ; L is quotient 711000000/(PQR) = S2 ; Symbols: ; / is division operator ; -> is assignment arrow ; sqrt is square root operator ; < is less than relational ; EE is EXP key (enter exponent) ; = is equality relational ; curt is cube root operator ; _ is display triangle Int (711/4)->A ; Get adding limit on P Int (sqrtsqrt7.11EE8)->B ; Get multiplying limit on P If A<B ; If adding limit is more restrictive Then A->G ; then set limit to adding limit Else B->G ; otherwise set limit to multiplying limit IfEnd ; [End of test of which limit is restrictive] For 1->C To G ; Loop through possible values for P Int (7.11EE8/C)->J ; Test if P is a divisor for value, and leave If CJ=7.11EE8 ; quotient in J Then Int ((711-C)/3)->A; If so, get adding limit on Q Int curtJ->B ; Get multiplying limit on Q If A<B ; If adding limit is more restrictive Then A->H ; then set limit to adding limit Else B->H ; otherwise set limit to multiplying limit IfEnd ; [End of test of which limit is restrictive] For C->D To H ; Loop through possible values for Q Int (J/D)->K ; Test if P is a divisor for value, and leave If DK=J ; quotient in K Then Int ((711-C-D)/2)->A; If so, get adding limit on R Int sqrtK->B ; Get multiplying limit on R If A<B ; If adding limit is more restrictive Then A->I ; then set limit to adding limit Else B->I ; otherwise set limit to multiplying ; limit IfEnd ; [End of test of which limit is ; restrictive] For D->E To I ; Loop through possible values for R Int (K/E)->L ; Test if R is a divisor for value, and If EL=K ; leave quotient in L Then 711-C-D-E->F ; Compute S1; L is S2 If F=L ; If S1 and S2 are equal Then "Solution" ; then label the solution C_ ; and D_ ; display E_ ; the F_ ; solution IfEnd ; [End of test S1 and S2 are equal] IfEnd ; [End of test R divides value] Next ; [End of loop through R values] IfEnd ; [End of test Q divides value] Next ; [End of loop through Q values] IfEnd ; [End of test P divides value] Next ; [End of loop through P values] "Done" ; Say we are done

We run this program, and this time, we have to wait only an hour for the results:

Solution 120 125 150 316

and about twenty seconds later, the message:

Done

An hour seems reasonable for this problem, given the intrinsic size of the search space. We brought the limitations inherent in the problem into play as early as possible, and so limited the search space as much as possible. We used rapid operations instead of slow ones. Without a change to the problem, we should not expect much more than the factor of 30 improvement in run times we already obtained.

This problem was actually given twice — once in 1996, and again three years later. The second version of the problem contained what was described as a “small” hint that all prices are at least $1.00. Using this hint in our fastest program — starting the P loop at 100, rather than 1 — yields the solution in about 30 seconds instead of an hour. Some “small” hint.

It is a programming truism that any program can be made twice as fast. While this speed up can be done repeatedly, the effort required to do so goes up exponentially as the cycles are repeated. It is generally more effective come up with a different algorithm that intrinsically takes less work. We used a radical change in algorithm to speed the search up by a factor of 12, then used another, minor, change of algorithm, with a deeper understanding of the problem and exquisite attention to the capabilities of the calculator, to get another factor of 2.5. Finally, a change in the problem itself — limiting the search space to prices of $1.00 and greater — sped the solution by a factor of 120. “Tweaking” the implementation was worth half an order of magnitude; choosing a better algorithm was worth one order of magnitude; and knowing more about the problem was worth two orders of magnitude. This pattern is not unusual. The finest code slinging in the world will never make up for incomplete problem analysis, and the finest problem analysis in the world will never make up for solving the wrong problem.

I think we have beaten this problem just about to death. We have four solutions using three algorithms, we have drawn the programming moral, we are done.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.