Re: LOGO-L> Factorials

[George Mills <mills@softronix.com>]

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 :-)

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.

Performance problems can sneak up on you when you don't expect it.
For example I now use MSWLogo's ARC function to build 3D Spheres
by rotating ARCs. If ARC was slow a Sphere would be impractical.

Performance problems sneak up on you a LOT with graphics, especially
in Logo. Someone draws one thing in Logo and the next thing they want
is to draw a 100 of them.

A good programmer always has performance in the back of his mind.
Not that he has to exercise it but at least question it.

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)?

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

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 graphics on my screen?

I'll pay for shipping !!!

> 
> [[Yehuda]]

-- 
===============================================================
George Mills
email: mills@softronix.com
http://www.softronix.com
The www page contains some very powerful educational software.
Our single most important investment is our kids.
---------------------------------------------------------------
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.