challenge for programmable calculators

[Gerson W. Barbosa]

(12-24-2013 06:38 AM)kakima Wrote:  Ah, excellent use of the stack to get rid of the local variable. You can also replace the two ZERO_DO instructions with ONE_DO since if any of the digits are zero then (a+b+c)*a*b*c is zero. That cuts the time down to about 2.2 seconds on a real 50g.

Assuming c = 1 (the lowest possible integer value for c) we can see by the table that b cannot be greater than 7 when a ranges from 1 to 9 (or, conversely, if b ranges from 1 to 9 a will not be able to be 8 or 9, otherwise the result will exceed 999).

a | b | a*b*c*(a + b + c)
--+--+------------------
9 | 9 | 1539
9 | 8 | 1296
9 | 7 | 1071
9 | 6 | 864
8 | 9 | 1296
8 | 8 | 1088
8 | 7 | 896
7 | 9 | 1071
7 | 8 | 896
...
Thus, we can limit either loop to 7. For instance:

Code:

%%HP: T(3)A(D)F(.);
\<< 1. 7.
  FOR a 1. 9.
    FOR b a SQ b * a b SQ * + 1. - NEG DUP SQ a b * 4. * a 100. * b 10. * + * + \v/ + a b * 2. * / DUP FP NOT NOT { DROP } { DUP 10. < { a 100. * b 10. * + + } { DROP } IFTE } IFTE
    NEXT
  NEXT
\>>

TEVAL

3: 135.
2: 144.
1: s:2.2434 (Real hp 50g)

Comparing with a plain brute-force solution:

Code:


%%HP: T(3)A(D)F(.);
\<< 1. 9.
  FOR a 1. 9.
    FOR b 1. 9.
      FOR c a b * c * a b + c + * a 10. * b + 10. * c + - NOT { 100. a * 10. b * + c + } IFT
      NEXT
    NEXT
  NEXT
\>>

TEVAL
3: 135.
2: 144.
1: s:14.3193

That is, the first program performs 63 trials in the same time the second program does about 114 tests, which means the more complicated inner loop involving root extraction requires about 81% more time to execute. All in all, not so bad at all...