CLAZY: lazy calling in Common Lisp

#11 06-16-2008, 11:14 AM

John Thingstad wrote:
> På Mon, 16 Jun 2008 16:03:05 +0200, skrev vanekl <vanek@acd.net>:
>
>> This algo appears to be more efficient than John's
>> since it is not recomputing the factorization over and over again for
>> each new test of primality.
>
> Appears being the operative word.
> Goes back to the old saying that Lispers know the value of everything
> and the cost of nothing.
>
> My algorithm can rest in the L1 cache. It doesn't need to access memory.
> (no consing)
> Although there are fewer iterations each step is sufficiently expensive
> that you still loose.
> For bigger primes there are more efficient algorithms also so that one
> is never optimal.
>
> --------------
> John Thingstad

Agreed. From a high-level analysis, I like the lazy algo better.
Of course implementation details can totally destroy an algorithms
effectiveness, even if the algo has good big-O qualities. The virtual
machine ultimately has the last say, when running the algo in the
real world. However, this doesn't preclude the possibility, in the future,
for the lazy algo to come out faster if the virtual machine this is
run on has different optimizations.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode