LOGO-L> Re: factorials

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

Erich Neuwirth wrote:
> 
> hi george and yehuda
> 
> just a few remarks
> my code is slower mainly because i calculate the sum of the 
> factorials and the numeric value with apply or recuresively.
> 
> whe i change that (see enclosed code) the runtimes goes down to 50% 
> and i am "back to normal"
> 
> i also changed the cache for the factorials from a list to an array,
> that had almost no influence on runtime.
> 
> i know that using apply and similar constructs slows down things.
> 
> BUT
> 
> i think the real power of a part of logo lies in these constructs.
> 
> we are selecting elements with certain properties from a basic set of > elements we create.
that is a fundamental pattern, and filter exists > just to be able to
express this fundamental
pattern.
> 
> in fact, i teach my students (beginning university students) in the > third unit of a logo
course about filter an map
> 
> filter and map combined are empirical equations solving: find all the > ellemenents of a base
set fulfilling a certain euqation!
> 
> so i think it is true but sad that most students working with logo 
> never meet these parts of the language.



Hello Erich,

I perfectly agree with your last point. Could you demonstrate a number
of //simple// procedures using those functions? I'm sure that there are
more members on this list who might find interest in that.

> if i remember correctly, both of you are splitting the a number
> into digits with the item function. this is something i would 
> discourage my students to do.
> 
> item is essentially a list and string function, so using item for 
> gettibg digits uses implicit type conversion between integers and > strings, and that also
costs time.
> besides, i think it is porgramming style that sometimes
> can be useful but should be discouraged.

I'm afraid that I don't agree with you in this point: Cost of run-time
is not a prime consideration in my teaching process. If so, you should
discourage your students using FOR, as well as other library procedures.

ITEM is very user-friendly, and I don't care if it takes a fraction of a
milisecond to convert string-elements to integers. Much of the power of
Logo lies in the fact that the user can ignore "types".
 
> of course, using crossmap to create the digit lists also is not 
> extremely efficient. but it is a natural consequence of the way i 
> structured the problem. i did not view the numbers to be tested as a > linear sequence of
integers. just taking the numbers from 100 to 999
> is, i think, the reason that you overlooked ths possible 
> simplification that digits above 6 cannot be used.

I overlooked the fact that it's wiser to build an array, to reduce the
number of factorial calculations. George the programmer brought it to my
attention.
I also overlooked that no digit above 6 can be a member of the solution.
You the mathematician brought it to my attention.
Of course I thank you both for that.

> so inherently, i am using lists of digits as my findamental data
> type, from this representation i am calculating the factval and the 
> numval.
> 
> additionally, since i am using this representation, i can change my 
> code very quickly to deal with the same problem in a different number > base like which 3
digit hexadecimal numbers have their value equal
> to the sum of their digit factorials.
> 
> all i have to change is the iseq's in crossmap and numval.
> 
> of course, my numval can easily be extended to take the number base 
> as a parameter, and then i can deal with the problem in any number 
> base.
> 
> using apply for factval and the recursive formulation for numval as i > did in my original code the immediately allows me to reuse the code
> for numbers with any given number of digits in any number base 
> system.
> 
> i tend to show my students to write easily generalizable programs.
> of course, the price you pay for a general solutions is that in 
> specific situations there are faster specific solutions.
> 
> but after all i am a mathematician, and i like general solutions.
> and i am willing to a factor of 2 in runtime of the code is much more 
> general.
> 
> additionally, with our problem here, the questions is 1 second or 2 
> seconds.

That's right. The important issue in CS teaching, I think, is not the
gain or loss of 1 second, but inventing a diversity of algorithms. AFTER
that, it might be interesting or valuable to compare them for speed.
We are all teaching Bubble Sort in Logo, *despite* the fact that it's an
inefficient sort algorithm.
 
> if the program is run only a few times, making it faster does not pay 
> off compared to the
time needed to create the faster version. 
> and with a problem like ours, you only need the code to run it once.
> so, if you have a structured program giving you the solution in 
> reasonable time ans allowing you to study similar problems, you 
> should think twice before trying to make it faster for just one 
> special problem.

There's here a slight mix of *economical* reasoning with that of a
theoretical one. In Logo at least, *economical* reasoning is secondary.
 
> p.s.: the enclosed code which is somewhat optimized for speed
> by working only for 3 digit numbers can be made a little bit faster 
> by using explicit lookup in factval instead of encapsulating the 
> lookup in the function fact
> 
> so the program becomes faster if we define
> 
> to factval :x1 :x2 :x3
> output (item :x1 :factlist) + (item :x2 :factlist) ~
>    + (item :x3 :factlist)
> end
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==
> 
> to fact :n
> output item :n :factlist
> end
> 
> to fact1 :n
> output ifelse :n = 0 [1] [:n * fact1 :n - 1]
> end
> 
> to factval :x1 :x2 :x3
> output (fact :x1) + (fact :x2) + (fact :x3)
> end
> 
> to iseq :a :b
> if :a > :b [output []]
> output fput :a iseq :a + 1 :b
> end
> 
> to make.factlist :n
> make "factlist (array :n + 1 0)
> foreach iseq 0 :n [setitem ? :factlist fact1 ?]
> end
> 
> to numval :x1 :x2 :x3
> output 100 * :x1 + 10 * :x2 + :x3
> end
> 
> to runsolve
> local "start
> local "result
> make "start timemilli
> make "result solve
> show timemilli - :start
> show :result
> end
> 
> to solve
> output  filter [[x] equalp first :x first butfirst :x] ~
>   (crossmap [list factval ?1 ?2 ?3  numval ?1 ?2 ?3] iseq 1 6 iseq 0
> 6 iseq 0 6)
> end
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==


About your above program let me please remind you that you have ISEQ
and LOCALMAKE in the library.


Now, here's a revised program, utilizing your and George's comments. 
I didn't eliminate ALL digits higher then 7, only limited the candidate
number to 100-666.

It runs now in less then a second (but that's George, on my P-266 !!):

=======================================
to main ; factorials
compute_facts
for[num 100 666][
   if equalp :num(sum fact item 1 :num
                      fact item 2 :num
                      fact item 3 :num)
   [pr :num]]
end

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

to fact :n
op item :n :fact_array
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.