Sierpinski triangle

Sierpinski triangle
You are encouraged to solve this task according to the task description, using any language you may know.

Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this:

	               *
	              * *
	             *   *
	            * * * *
	           *       *
	          * *     * *
	         *   *   *   *
	        * * * * * * * *
	       *               *
	      * *             * *
	     *   *           *   *
	    * * * *         * * * *
	   *       *       *       *
	  * *     * *     * *     * *
	 *   *   *   *   *   *   *   *
	* * * * * * * * * * * * * * * *

Common Lisp

(defun print-sierpinski (order)
  (loop with size = (expt 2 order)
        repeat size
        for v = (expt 2 (1- size)) then (logxor (ash v -1) (ash v 1))
        do (fresh-line)
           (loop for i below (integer-length v)
                 do (princ (if (logbitp i v) "*" " ")))))

Printing each row could also be done by printing the integer in base 2 and replacing zeroes with spaces: (princ (substitute #\Space #\0 (format nil "~%~2,vR" (1- (* 2 size)) v)))

Replacing the iteration with for v = 1 then (logxor v (ash v 1)) produces a "right" triangle instead of an "equilateral" one.

D

Translated from Lisp examples. <d>module sierpinski ; import std.stdio ;

long ipow(int x, int n) { return n > 0 ? x*ipow(x, n-1) : 1 ; }

void sietri(uint n) {

 if(n > 5) return writefln("integer bit size limited : n should not be larger than 5") ;
 long size = ipow(2,n) ;
 long v = ipow(2, size) ;
 for(int i = 0 ; i < size ; i++) {
   for(int j = 0; j <v.sizeof*8 ; j++ ) 
     writef(ipow(2,j) & v ? "*" : " ") ;
   writefln() ;
   v = (v << 1) ^ (v >> 1) ;
 }

}

void main() {

 for(int n = 0; n < 5 ; n++)
   sietri(n) ;

}</d>

Forth

: .line ( n -- )
  begin
    dup 1 and if [char] * else bl then emit
    1 rshift  dup 0=
  until drop ;

: triangle ( order -- )
  1 swap lshift   ( 2^order )
  1 over lshift
  swap 0 do
    dup cr .line
    dup 2/ swap 2* xor
  loop drop ;

4 triangle

Haskell

sierpinski 0     = ["*"]
sierpinski (n+1) =    map ((space ++) . (++ space)) down 
                   ++ map (unwords . replicate 2)   down
  where down = sierpinski n
        space = replicate (2^n) ' '

printSierpinski = mapM_ putStrLn . sierpinski

J

There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity:

   |._31]\,(,.~,])^:4,:'* '

Here's one that leverages the relationship between Sierpinski's and Pascal's triangles:

   ' *'{~'1'=(-|."_1[:":2|!/~)i.-16