I was able to get the Arduino Mega 2560 to calculate and draw a next nearest neighbor fractal using uLisp-TFT. However, I had to use some rather aggressive GC to keep from running out of memory, which slowed the calculation down very much (about 8 or 9 hours for this image). I only need to store two lines of pixels at a time, but I think data extraction and rule-related calculation creates a lot of intermediate lisp objects. To make this practical I think I need to re-implement the core NNN functions in C, leaving the Lisp rule selection and drawing interface on top.
uLisp code is available here: http://download.savannah.nongnu.org/releases/ulisp-tft/nnn-slow.tar.gz
This call should get you a similar image:
(lcdinit) (drawnnn (buildf32 187 71 254 245) (randomline 30))
30 is for 30 blocks of 16 pixels, i.e., start with 480 pixel line.