Re: LOGO-L> Factorials

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

George Mills wrote:
> 
> Yehuda Katz wrote:
> >
> > George Mills wrote:
> > >
> > > Changing to FOR may be a tad slower than REPEAT but the bulk of
> > > the time is now simply fetching the correct precalculated value from
> > > the "factorial cache".
> >
> > If speed is the main concern, maybe it would be better to calculate the
> > factorials by an iterative procedure instead of a recursive one. You
> > might want to check this.
> >
> 
> Don't forget who brought up the subject of speed wondering how fast
> your new (I mean my new) computer would run your original post :-)

George,
My sclerosis is really in an advanced state, but I didn't forget that.

 
> However if you kept your original code without the cache then removing
> the recursion might help. But now since your only doing 10 factorials
> instead of 899 the difference is going to be neglagible in trying to
> improve
> fact_real any further. The whole routine now is purely limited to how
> fast
> it can extract the value from the cache. Try timing compute_facts, it's
> probably about 1/10 of second.
> 
> The reason I say might help is for 2 reasons. One is UCBLogo/MSWLogo's
> tail recursion. Second is UCBLogo/MSWLogo's speed is dominated by
> parsing not by the actual execution. In a compiled language it would
> certainly help.
> 
> >
> > Instead of using an array, I tried creating a *list* of those 10
> > factorials. It appears that the list gave slower performance, but that's
> > only my impression.
> >
> 
> That's the problem with lists, they are terribly inefficient.
> But at times they are terribly elegant too.

Agree. I would say: extremely elegant.
 
<snip>
> 
> A good programmer always has performance in the back of his mind.
> Not that he has to exercise it but at least question it.

One of the best things I find in Logo is, that because its relative low
speed, I MUST find efficient algorithms to solve problems, so to have a
reasonable execution time. I might apply later those algorithm on other
(faster) languages.

> Who will use this function?
> How often will this function be used?
> Will it be used by higher order functions?
> Are the optimizations worth the risk of increased bugs?
> Are the optimizations worth making the code less maintainable?
> Will I meet my deadline?
> Whats the cost of other resources (memory)?

As a teacher, deadline (and other) considerations are away from me, but
it's interesting to see the rationale of a profesional programmer.


> > > If things were real large and less predicatable you can also Fill
> > > the "cache" on demand. You do this by "tagging" each entry as to
> > > its validity.
> >
> >
> > How you do that?
> >
> 
> In this case it's easy.
> 
> Fill the array with -1's (invalid tag).
> Now in FACT check if the entry is -1. If it is -1 (invalid) go do the
> FACT_REAL. Now put that result into the "factorial cache" and
> also output it. Next time you call for that factorial the "cache"
> entry will be valid (not -1). So you simply output the entry like you
> do now.
> 
> If you can not use the data itself as the "validity tag" then you'd
> simply use a list pair [tag data] for each item in the array (cache).
> 
> This way you don't calculate unnecessary factorials but at the cost of
> a slower FACT (testing the tag). Since you know which factorials you'll
> need it's not needed in this case but in other situations it
> is. Because you may have a 1000 "expensive" operations to cache
> and you can't afford to calculate them all up front.

Now I rememeber that in BASIC I found, that re-assigning values to the
elements of a given string worked faster than creating that new string
from scratch with the desired values.

> But again many of these performance tricks backfire in Logo
> because of the dominance of parsing. Often I've seen "Cosine and Sine"
> caches. This would be useless in Logo because Sine takes about as long
> as Minus !!!
> 
> to xxx
> make "start timemilli
> repeat 10000 [make "x sin 45]
> show (timemilli - :start) / 600
> make "start timemilli
> repeat 10000 [make "x minus 45]
> show (timemilli - :start) / 600
> end
> 
> 2.415
> 2.14
> 
> Just one added instruction in Logo to make things smarter for Sine
> would kill any performance gain.
> 
> Note, a COMPILER is a preparsed CACHE of your program.
> 
> > > Since now you won't be needing the P266 I'll give you an address
> > > you can forward it to :-).
> >
> > I'll consider you generous offer, but then - how shall I be able to
> > redraw FAST those PhotoShop graphics on my screen?
> 
> I'll pay for shipping !!!

Mommy taught me not to do business with friends.

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