I love a good subterfuge. It can be in the form of a hoax, fake argument, prank, magic trick or even an incendiary blog post aimed at hyping the public. Something surprising and unexpected is always a nice diversion from the daily grind. The latest ploy is a computer-generated image of a mysterious craft knocking about over Santa Cruz. The hoax started out as a winner by first being reported on AM radio. It then reached critical mass after arriving on the BoingBoing front page.

Details surrounding these pictures were convincing. The creators added plausible EXIF tags and PICT#### file names to give the illusion that they were taken with a Minolta Dimage camera. Next, plenty of people on the Net were backing-up the story with pseudo-scientific explanations that sounded believable. And, reports of other sightings exist at multiple conspiracy-nut websites.

Nevertheless, a few glaring mistakes were evident to keen-eyed netizens. The accounts of the would-be roustabout and all of his supporters on Flickr were discovered to be newly registered. Next, a CG-expert produced a clone of the alleged craft using 3D software in under 2-hours. Other detractors noted that the picture size was too small, the f-stop setting was implausible, and the weather was cloudy at the alleged location.

Sigh… This was so close to being a perfect ruse too. It had believable images, supporters on Flickr, and even a BoingBoing mention. Nevertheless, the whole story jumped the shark in less than two hours thanks to the wisdom of nerds. Hooray for the tubes.

UPDATE: Flickr user o_ashford speculates as to one possible use of the craft.

In England, muffins are referred to as “American muffins” and English muffins are just called “muffins”. It makes perfect sense, but it’s one of those facts that you just don’t ever consider.

I love Little Feat. They are my all time favorite band. It’s not surprising for me to learn that Lowell George has admirers in Japan. He was a truly unique composer, vocalist, and slide guitarist. Thankfully, you can still enjoy Lowell’s music in the current incarnation of Little Feat. I will be heading to Aptos on May 26th to see them perform.

OK, I’m all for working smarter not harder, but I don’t see how the Lambda Calculus can help solve fib(n). I mean, one could use the closed-form solution, recursion, or iteration in pretty much any language. Nevertheless, over at Martini Design, he seems to think that Scheme can somehow more succinctly describe Leo’s incredible series. Problem is, fib(n) in closed-form i.e. (Φn+(1-Φ)n)/√5 where the Golden Ratio, Φ=(√5+1)/2 is more computationally efficient for small values of n, and the iterative-form is more efficient when calculating large values of n using only integer maths. I ran some tests on the following implementations to get a handle on the matter. I started out with an iterative, recursive, and libgmp C-implementation versus the demonstrated Scheme design.

#include <stdio.h>
#include <math.h>
#include <gmp.h>

#define PHI 1.61803398874989484

// C recursive solution
unsigned long long fib_r(unsigned long long n) {
  return (n<3) ? 1 : fib_r(n-1) + fib_r(n-2);
}

// C closed-form solution
unsigned long long fib_c(unsigned long long n) {
  return((pow(PHI,n)-pow(1.00-PHI,n))/sqrt(5)+0.5);
}

// C iterative solution
unsigned long long fib_i(unsigned long long n) {
  if (n<=2) return(1);
  unsigned long long i, sum=0, a=1, b=1;
  for(i=3; i&lt=n; i++) {
    sum=a+b;
    a=b;
    b=sum;
  }
  return sum;
}

// C libgmp solution
char* fib_g(unsigned long long n) {
  mpz_t fn;
  mpz_init(fn);
  mpz_fib_ui(fn, n);
  return mpz_get_str(NULL, 10, fn);
}

Here is the original solution in Scheme.

(define (fib x)
  (define (fib2 x1 x2 cnt maxcnt)
    (cond
      ((= cnt 0)
       (fib2 0 0 (+ cnt 1) maxcnt))
      ((= cnt 1)
       (fib2 1 0 (+ cnt 1) maxcnt))
      ((> cnt maxcnt)
       x1)
      (else
       (fib2 (+ x1 x2) x1 (+ cnt 1) maxcnt))))
    (fib2 0 0 0 x))

So, for fun, I benchmarked the Scheme implementation against libgmp on my Macbook Pro (2.33GHz Core 2/2GB) for n=1000000. Here are the timed results.

$ time ./fib_scheme
real    6m0.414s
user    5m54.327s
sys     0m1.889s

$ time ./fib_gmp
real    0m0.167s
user    0m0.152s
sys     0m0.010s

The Scheme solution takes over 6 minutes to complete while the libgmp one finishes in 0.167 seconds. Therefore, the Scheme implementation requires more lines for trivial cases and is computationally slower for non-trivial cases.

Next, I decided to test an iterative ruby implementation for fib(1000000) to compare.

# Ruby - iterative algorithm
  def fib(n)
    return 1 if n<=2
    i=0; a=1; b=1; sum=0
    return 1 if n<=2
    3.upto(n) {
      sum=a+b
      a=b
      b=sum
    }
    return sum;
  end

Here are the results from CRuby.

$ time ruby fib.rb
real    3m18.343s
user    2m6.019s
sys     1m7.913s

Hmmm, what about JRuby, Rubinius and yarv?

$ time jruby-1.0.0RC1/bin/jruby fib.rb
real    5m19.290s
user    5m3.198s
sys     0m6.543s

$ time yarv/ruby ~/fib.rb
real    3m15.521s
user    2m7.299s
sys     1m7.079s

$ time shotgun/rubinius ~/fib.rb
[Using local compiler]
real    4m31.221s
user    0m9.542s
sys     0m53.533s

I ran another functional implementation through Erlang.

%% Erlang - recursive
fibonacci(N) when N < 2 -> 1;
fibonacci(N) -> fibonacci(N-1) + fibonacci(N-2).

This unfortunately did not complete after 27 minutes.

Next up is an iterative Python implementation.

# Python - iterative
def fib(n):
  sum=0
  a=1
  b=1
  if n<=2: return 1
  for i in range(3,n+1):
    sum=a+b
    a=b
    b=sum
  return sum

$ time python fib.py
real    3m16.089s
user    2m28.190s
sys     0m46.314s

Dons and Quhaha from reddit encouraged me to try Haskell. So, I ran the following fast recursion implementation as well.

module Main where
-- Haskell Fast Recursion
f n = fst (l n) where
  l n | n<2 = (1,1)
    | n==2 = (2,1)
    | n>2 = if (rem n 2)==1 then ( k1*(k1+k2)+k1*k2,k1*k1+k2*k2)
                  else ((l1+l2)*(l1+l2)+l1*l1, (l1+l2)*l1+l1*l2)
      where (k1,k2) = l (div (n-1) 2)
         (l1,l2) = l ((div n 2)-1)
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f n))

Surprisingly, the Haskell routine was very fast as a recursive algorithm.

$ time ./fibh
real    0m2.205s
user    0m2.188s
sys     0m0.012s

It appears that the libgmp Fibonacci implementation is orders of magnitude faster than any normal iterative or recursive solution using FP or iterative solutions. Since libgmp is the defacto choice for number theorists, the speed of its custom fibonacci function is to be expected. The most surprising fact is that CRuby is nearly as fast as compiled Python for this calculation, and the Haskell fast recursion algorithm’s excellent speed.

Note: My graph legend specifies “/i” for iterative and “/r” for recursive.

I finally got bit hard by the slowness of REXML at work, so I compiled my own Ruby XML library parser as a gem for Mac OS X and Linux. You can download these gems from my repository until I figure out how to setup a multiplatform gem server.

To install under Intel-based Macs:

wget http://involution.com/xaggly/xaggly-0.0.1-i686-darwin8.8.2.gem
sudo gem install xaggly-0.0.1-i686-darwin8.8.2.gem

So, old hudge was kicking up a helluva fuss about setxattr errors this morning.

I was getting the following errors, over and over and over again in my syslog file.

hudge kernel: post_create: setxattr failed, rc=28 (dev=sda1 ino=8339458)

In fact, I got so many of these errors that they filled up my root partition. The full disk caused mysql to stop working altogether and the corruption of a couple of tables in my wordpress database. Question is, with SELinux disabled on my box, why would I get 50GB worth of setxattr errors?