(In reply to
re: Jump Start by goFish)
floor(A/B) for positive integers A,B is just the positive integer
quotient Q obtained using the division algorithm (i. e., long division)
so that A=Q*B+R where 0<=R<B. Hence the "complexity" of
floor is that of long division. However, this complexity is not
what is the bugaboo for this problem. The bugaboo is "long"
sums. The algorithm that fits the hint generates the sum
144-63-18+6+1=70 where each of the numbers in the sum is obtained using
a small number of elementary arithmetic operations. There are 5 terms
in this sum, as opposed to the 23 floored terms in the brute force
original sum (omitting the k=0 term). For this example (a=5,b=17,m=23),
5 is "fast" and 23 is "slow." For bigger a and b, the contrast
can be much more dramatic. The fast algorithm will add up a
number of easily computed terms that is bounded by a multiple of the
number of decimal digits of a, instead of a number of terms equal to m
for the slow brute force sum.
To realize the full impact of the hint, replace 5 by a, 17 by b, 23 by
floor(Kb) and 6 by floor(Ka) where K is any positive real number. That
is, I claim that it is always the case that for general a,b, and K
Sum_{0<=k<=Kb} floor(ka/b) + Sum_{0<=l<=Ka} ceiling(lb/a) = floor(Ka)floor(Kb+1)
permitting you, if you play your cards right, to home right in on the
answer to the original problem in simple stages by using various
decreasing values for a or b (K stays constant).
Correction to formula above applied.
Edited on December 30, 2005, 12:52 pm
|
|
Posted by Richard
on 2005-12-30 03:25:02 |
re(2): Jump Start
