[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Axiom-developer] linear time algorithm

From: Tim Daly
Subject: [Axiom-developer] linear time algorithm
Date: Wed, 19 May 2004 13:02:14 -0400

In fact I've faced the same issue with my work on the Andrews-Curtis
Conjecture. Simply put, this takes a finite representation of a special
group and applies one of 12 transformation functions iteratively
looking for the identity element.

The initial algorithm is clear but garbage collects like mad (lisp).
The second iteration modifies list storage in place but string-conses.
The third algorithm modifies strings in place but copies on overflow.
The fourth algorithm caches power-of-2 strings (binary buddy).

So the literate program explains the theory and then explains the
first algorithm. Next it explains the problem and its subsequent
refinement. Only the last refinement is extracted but the "thought
processes" leading from the initial implementation up to the efficient
form of the algorithm are presented. 

Simply because the code is highly optimized is no reason not to 
include the theory or the steps across the impedence gap.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]