Optimizing Lisp May 24th, 2009
Patrick Stein

Paul Reiners recently posted some code to the TC Lispers mailing list. The code began from Paul Graham’s ANSI Common Lisp book. Exercise 13b has you adding declarations to some code so that the compiler can better take advantage of the types involved. Oddly, the code ran more slowly with his typing than it did without it. I had the same experience when I tried this code under SBCL 1.0.23 on Mac OS X.

Here is Paul’s original code which he made available with Creative Commons License the Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

I stripped out the declarations and started adding them in one by one, trying to deal with as many compiler notes as I could figure out in the process. First, in the base case, the following took 22.5 seconds on my computer.

(time (ray-test 8))

After much tweaking, I have gotten it down to just under 11 seconds. Most of that came with declaring the types of the slots in the (defstruct …)‘s and these three declarations:

(declaim (ftype (function (long-float) long-float) sq))
(declaim (ftype (function (long-float
                           long-float
                           long-float) long-float) mag))
(declaim (ftype (function (long-float
                           long-float
                           long-float)
                          (values long-float
                                  long-float
                                  long-float)) unit-vector))

This declaration, however, shot me back up to 22 seconds.

(declaim (ftype (function (long-float
                           long-float
                           long-float)
                          long-float)) minroot))

Of course, it really should have been returning (or long-float nil). But, that didn’t help either. From the compiler notes, it seems that (min …) in SBCL doesn’t deal well with unboxed floats. I will have to look harder at that section and ask on the SBCL lists. I believe that I tried decorating the expressions there, too.

(the long-float (min (the long-float
                       (/ (the long-float (+ (the long-float (- b))
                                             discrt)
                               (the long-float (* 2L0 a)))))
                     (the long-float
                       (/ (the long-float (- (the long-float (- b))
                                             discrt)
                               (the long-float (* 2L0 a)))))))

Lisp Patterns Question W.R.T. Clifford Algebras May 20th, 2009
Patrick Stein

Since I moved my website to WordPress, I have been watching what search-engine searches land people on my page.

Sadly, two of the things that get people to my page most often still have not been moved over to the new site from the old. One of those things is a C++ template library for Clifford algebras. I am going to move that stuff over this week, I promise. But, I thought I might also make a Lisp library for Clifford algebras, too.

An example Clifford algebra might be C_{3,0}. A generic element in this algebra is of the form:

a_0 + a_1 e_1 + a_2 e_2 + a_3 e_3 + a_{1,2} e_{1,2} + a_{1,3} e_{1,3} + a_{2,3} e_{2,3} + a_{1,2,3} e_{1,2,3}

where the a_* are coefficients. For ease in dealing with these items, I will probably store that in a vector that looks something like this:
#(a_0 #(a_1 a_2 a_3) #(a_{1,2} a_{1,3} a_{2,3}) a_{1,2,3})

If you want a simple element though (where most of the coefficients are zero), you shouldn’t have to stare down all of that stuff or remember that a_{1,3} comes before a_{2,3}. I want you to be able to make 3 + 4 e_1 + 5 e_{1,2,3} more simply. Something like one of the following:

(defvar *a* (ca-element '(3 (4 1) (5 1 2 3)) :p 3))
(defvar *a* (ca-element '(3 (4 . :e1) (5 . :e1-2-3)) :p 3))
(defvar *a* (ca-element :s 3 :e1 4 :e1-2-3 5 :p 3))

Similarly, I will define something akin to (aref …) so that one can check or change a_{1,2} like one of the following:

(caref *a* 1 2)
(caref *a* :e1-2)

By analogy with the complex numbers, I should instead have:

(e1-2 *a*)

But, that just doesn’t scale very well.

I am leaning toward using a list of numbers to tell which a_* is being referenced. This would allow greater flexibility in other functions. But, it’s also less mathy.

Does anyone have any suggestions? Should I really be supporting both? Through the same function names or through (caref …) and (caref* …) or something?

A Different Look at the Mandelbrot Set May 14th, 2009
Patrick Stein

When you see pictures of the Mandelbrot set you are seeing the results of iterating a function over and over.

For the Mandelbrot set, you take a complex number c. You square it and add the original number. You take that, square it, and add the original. You do this a number of times. If the value stays relatively close to zero, the number is in the Mandelbrot set. If the value takes off away from zero, the number is not in the Mandelbrot set. Typically, one colors in the parts of the picture that aren’t in the Mandelbrot set with some color that indicates just how fast it hightailed it out of there.

I wanted to try something different. I wanted to see what the iteration process looks like. So, I threw together some code using Lisp with cl-opengl.

fibersThe first visualization that I coded was to start with tiny patches of the complex plane. From each patch, I would extrude it up out of the plane and over to its next iteration. The picture at the right is (IIRC) a patch with side-length one half centered at i with either 25 or 36 patches tiled in that area. As you can see, this isn’t a wholly satisfying picture of what’s going on.

The other idea that I had was to show the progress through iterations as an animation. This is a bit more interesting to look at until some of the patches start overflowing my floating point numbers or get too big for my clipping region. This is an area of side-length one centered at the origin with four-hundred patches. Here is a movie of that flow.

Finding Better Polynomials May 12th, 2009
Patrick Stein

Some time ago, I wrote a small domain-specific language for finding polynomials given their value or the value of their derivatives at particular points.

It occurred to me shortly after writing that code that I could easily extend it to include the value of its integral over a certain range. I didn’t get to tackling that right away, and that was a Good Thing. In the intervening time, it occurred to me that I could extend it to moments as well.

So, are you looking for a polynomial that is zero at both zero and one, has a derivative of zero at one, has a second derivative of negative one at one, whose integral from zero to one is one, and whose mean (first moment centered at zero) on the interval zero to one is one fourth?

(polynomial-to-string
  (calculate-polynomial-subject-to
    (value :at 0 :equals 0)
    (value :at 1 :equals 0)
    (derivative :at 1 :equals 0)
    (nth-derivative 2 :at 1 :equals -1)
    (integral :from 0 :to 1 :equals 1)
    (mean :from 0 :to 1 :equals 1/4)))

Well, that would be f(x) = \frac{149}{4}x - 163x^2 + 265x^3 - 190x^4 + \frac{203}{4}x^5. (For some reason though, gnuplot thinks f(x) = -1, so no graph for you…)

Here is the source file.

graph
Edit: I realized that gnuplot was off by one because it was truncating the fractions. So, I just changed the 4’s in the denominators to 4.0’s and Bob’s your uncle.

 

Code Clarity Revisited May 11th, 2009
Patrick Stein

In an earlier post, I showed a simple loop written in several programming languages. The loop had to sum the weights of each items in a list. Dmitry pointed out a much clearer loop in Lisp using the (loop …) construct.

(loop for item in item-list sum (weight item))

I then twiddled for the better part of an hour trying to find the clearest way to do weighted random choice with Lisp (loop …). This is the best that I have come up with:

(loop
   with total = (loop for item in item-list sum (weight item))
   with thresh = (random total)
   for item in item-list
   if (minusp (decf thresh (weight item)))
     return item)

The biggest pedagogical obstacle in the above is the (decf …) which decrements the variable in place by the given amount and returns the new value of the variable. What I really wanted to do was this:

(loop
   with total = (loop for item in item-list sum (weight item))
   for item in item-list
   tracking item
   as thresh downfrom (random total) by (weight item))

That fails on multiple fronts, however.

  • There is no tracking keyword in (loop …). I can sum or maximize or collect items, but I cannot keep track of the last one that I saw. I had hoped to use the finally keyword, but its value isn’t returned from the loop.
  • Lisp requires that the decrement amount in the by of a downfrom be greater than zero. As such, I have to filter out any items that have zero weight. Feh. I can do that. I would rather not. But, I can do that.
  • Lisp only evaluates the by expression once. It does not evaluate it each time through the loop.

I am still learning all of the ins and outs of (loop …). Today, I learned as many outs as ins. Feh.

RSS Feeds

l