Re: LOGO-L> Factorials

[Yehuda Katz <yehuka@beitberl.beitberl.ac.il>]

George Mills wrote:
> 
> 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




Hello George,

Thank for your nice tip. It can serve as a nice introduction to the
subject of arrays in Logo, and I'm going really to use it.

I modified your program a little bit, probably at the cost of some
slower performance, by trading REPEAT with FOR (in compute_facts).

=======================================
to do
compute_facts
for[num 100 999][
   if equalp :num(sum fact item 1 :num
                      fact item 2 :num
                      fact item 3 :num)
   [pr :num]]
end

to compute_facts
make "factarr(array 10 0)
for[i 0 9][
      setitem :i :factarr fact_real :i]
end

to fact :n
op item :n :factarr
end

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

Regards...

[[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.