LOGO-L> Re: factorials

[Erich Neuwirth <neuwirth@smc.univie.ac.at>]

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.

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.

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.

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.

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.


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


--
Erich Neuwirth <neuwirth@smc.univie.ac.at>
Computer Supported Didactics Working Group, University of Vienna
Currently Visiting Professor at the 
National Institute of Multimedia Education, Chiba, Japan
Visit our SunSITE at http://sunsite.univie.ac.at
---------------------------------------------------------------
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.