mathr / blog / #

Resurrecting Spiders

Spider 3/7

The Spider Algorithm finds a parameter \(c\) for the iterated quadratic polynomial \(P(z)=z^2+c\) that has the same dynamics as a rational external angle \(\theta\). There are few implementations: Yuval Fisher implemented a program in 1992, but it wouldn't compile and run on my 64bit GNU/Linux/Debian desktop. So I set about fixing it, so I could try it out and eventually learn how the spider algorithm works to re-implement it myself.

The first problems I had were quite simple, missing or conflicting declarations. It wasn't hard to get it to compile, but it would crash horribly on startup. Some digging led me to realize that it was an incompatibility between 64bit OS and the XView toolkit used by the code. Debian supports multi-arch (for example running 32bit binaries on a 64bit OS) so the next step was to get a 32bit version compiled.

I installed qemu, and inside a virtual machine I installed a 32bit Debian. An alternative would have been to set up a cross-compiler, but it would probably have taken even longer, though I would have learnt more in the process. Inside the VM I could compile the 32bit binary I needed, and outside the VM in my 64bit OS I could install xviewg:i386 using Debian multi-arch.

The binary still crashed on startup, sometimes entering an infinite recursion first (interrupting the execution in the gdb debugger gave a stack trace with over 15000 items). The copy_va_to_av() function in XView was going crazy, presumably because it missed a sentinel. On a hunch I added some extra 0 padding to a few variadic function calls, and luckily that seemed to fix it. I probably missed some cases because the binary still crashes occasionally, but it works well enough to have a play around.

The image above is a snippet of a screenshot, after entering angle \(3/7\), clicking the lift button a few times, and finally activating the Julia set button. The spider legs seem to converge to special points in the Julia set, which is presumably related to how the algorithm works.

I uploaded a repository with my code changes: maximus/spider on gitorious spider on, and a compiled binary for i386 which might be useful if you don't fancy setting up a 32bit VM to compile it yourself.