Sunday, December 19, 2010

XOR using string rewriting

Can XOR to be constructed using string rewriting and iterating such rules like the following:

0 -> 0 0
0 2

1 -> 2 2
2 4 ?

Friday, July 17, 2009

XOR - Sierpinski gasket

# include ;
# include ;
# include ;

int x,y;int gd,gm;

void main(void)
{
clrscr();

initgraph(&gd,&gm,"c:\\bc\\bgi");

for(x=0;x < getmaxx();x++)
for(y=0;y < getmaxy();y++)
{
putpixel(x,y,((x+y)-(x^y))%15+4);
}

getche();
closegraph();
}

Farey - XOR - Fractals: Sierpinski gasket, Peano

For the relation between the Farey numbers and the XOR table, please visit the page:
http://www.cut-the-knot.org/blue/Fusc.shtml

I found the problem from: http://www.cut-the-knot.org/arithmetic/NimSum.shtml
also in an old book from authors: A. M. Iaglom, I. M. Iaglom: "Nonelementary problems treated elementary" - problem 127.

Related to this problem I found some fractals: the Sierpinski gasket fractal and Peano.
For the Sierpinski fractal the procedure is the following:
- every number stored in the position (i,j) will be expressed like i+j + d where d has a meaning of difference.
For the first rows if we memo in an array just the differences we obtain:

0 0 0 0
0 2 0 2

0 0 4 4
0 2 4 6
The matrix begin with the position (0,0).

This matrix can be represented with colors and we obtain the Sierpinski gasket; it is the same like representing on the coordinates (i,j) the a pixel with the color i xor j.

If we follow the odd and even numbers of the XOR table we obtain the Peano curve
---*---
---*--- ---*--- where * means again some recursive drawing of rectangles.
---*---

XOR - Peano filigree



# include ;
# include ;
# include ;

int x,y;
int gd,gm;

void main(void)
{
clrscr();

initgraph(&gd,&gm,"c:\\bc\\bgi");

for(x=0;x < getmaxx();x++)
for(y=0;y < getmaxy();y++)
{
putpixel(x,y,(x^y)%2);
}

getche();
closegraph();
}