Re: LOGO-L> Factorials

[George Mills <mills@softronix.com>]

Yehuda Katz wrote:
> 
> Hi,
> 
> Many years ago, using BASIC, we encountered the following problem:
> Find all 3-digit numbers, that equal the sum of the factorials of their
> digits.
> In other words: We need all 3-digit numbers of the form ABC which
> maintain: ABC=A!+B!+C!
> 
> I wanted to test UCBLogo to see how good it solves that problem.
> Here's one possible solution:
> 
> ========================================
> to solve
> for[num 100 999][
>     if equalp :num(sum fact item 1 :num
>                        fact item 2 :num
>                        fact item 3 :num)
>     [pr :num]]
> end
> 
> to fact :n
> op ifelse :n<2[1][:n*fact :n-1]
> end
> ========================================
> 

Why keep computing the SAME factorials over an over again.
Here is a common performance trick. This NEW code will run
twice as fast on my OLD P133 than your OLD code will run
on your NEW P266 (i.e. it's about 4 times as fast) :-)

A great teacher once told me, a slow algorithm is still slow
on ANY computer.

on a P133

solve_old
145
8.38166666666667

solve_new
145
2.29333333333333

to compute_facts :n
make "myfacts (array :n 0)
repeat :n [setitem repcount-1 :myfacts fact_real repcount-1]
end

to fact :n
op item :n :myfacts
end

to fact_real :n
op ifelse :n<2[1][:n*fact_real :n-1]
end

to solve_new
make "start timemilli
compute_facts 10
for[num 100 999][
    if equalp :num(sum fact item 1 :num
                       fact item 2 :num
                       fact item 3 :num)
    [pr :num]]
show (timemilli - :start) / 600
end

to solve_old
make "start timemilli
for[num 100 999][
    if equalp :num(sum fact_real item 1 :num
                       fact_real item 2 :num
                       fact_real item 3 :num)
    [pr :num]]
show (timemilli - :start) / 600
end

> 
> [[Yehuda]]
> 
> ---------------------------------------------------------------
> Please post messages to the Logo forum to logo-l@gsn.org.  Mail
> questions about the list administration to logofdn@gsn.org.  To
> unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.

-- 
===============================================================
George Mills
email: mills@softronix.com
http://www.softronix.com
The www page contains some very powerful educational software.
Our single most important investment is our kids.
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.