Re: LOGO-L> factorials, once more

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

Erich Neuwirth wrote:

hello yehuda and george,

this time, i can't resist.

i have been following your factorials discussion, issues of speed
and so on.

the main speed issue in this projects is not programming related,
but simple math.

7!=5040

so there i no use in trying any digits above 6.

so instead of 
899 tests,
only

6*7*7 = 294 tests are needed.

so we have reduced the runtime to 1/3 before
writing the first line of code.

of course, with this method, a simple for loop
is infeasible,
instead,

(crossmap [list ?1 ?2 ?3] iseq 1 7 iseq 0 7 iseq 0 7)
creates the digit sequences of length 3.

for any list of 3 digits we want
factval (sum of factorials)
equal numval
(numeric vale)

filetre selects these triplets nicely.

so, enclosed is the code.

could you please compare runtime with your solutions?

just do

make.factlist 6
solve



here os my code

-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

to fact :n
output item :n + 1 :factlist
end

to factlist.helper :n
if :n = 0 [output [1]]
local "shorterlist
make "shorterlist factlist.helper :n - 1
output fput  :n * first :shorterlist :shorterlist
end

to factval :l
output apply "sum map [fact ?] :l
end

to iseq :a :b
if :a > :b [output []]
output fput :a iseq :a + 1 :b
end

to make.factlist :n
make "factlist reverse factlist.helper :n 
end

to numval :l
if emptyp :l [output 0]
output (last :l) + 10 * numval butlast :l
end

to solve
output  filter [[x] equalp factval :x numval :x] ~
  (crossmap [(list ?1 ?2 ?3)] iseq 1 6 iseq 0 6 iseq 0 6)
end
-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Erich,

The fact that no digit can be higher then 6, as 7! is already a 4-digit
number - is of course correct. But some times we want the computer do
the thinking for us, even when it means brute force. Here the computer
is at its best (cf. Deep Thought vs Kasparov).

About your above program: It happens, that the original question was a
"rich" one, with several distinct ways of solution.
You use "advanced" commands of the language (map, apply, filter,
crossmap), which are beyond the average student vocabulary. There's of
course nothing wrong with that - it's merely a pedagogic observation.

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