Feynman Lectures on Computation을 읽는 중. 가역계산(Reversible computation)에 대한 내용이 나오길레 연습문제 삼아 조금 풀어보았다. N(Not), CN(Control-Not), CCN(Control-Control-Not) 게이트에 대한 내용.
편의상 진리표의 숫자를 이진수로 읽으면 가역계산의 경우 permutation이 된다는 것을 알 수 있다.
CN gate
CN
0->0 (00->00)
1->1 (01->01)
2->3 (10->11)
3->2 (11->10)
NC
0->0
1->3
2->2
3->1
이렇게 쓸 경우의 장점(?)은 행렬(matrix)로 쓸 수 있다는 것. 따라서 교환회로(exchange circuit)의 경우
exchange = CNxNCxCN
0->0
1->2
2->1
3->3
로 읽을 수 있다. 다음은 CCN 게이트의 permutation에 해당하는 값.
CCN gate
CCN
0->0
1->1
2->2
3->3
4->4
5->5
6->7
7->6
CNC
0->0
1->1
2->2
3->3
4->4
5->7
6->6
7->5
NCC
0->0
1->1
2->2
3->7
4->4
5->5
6->6
7->3
전부 계산하느라 헤맸는데 생각해보니 행렬로 쓸 거면 좌표변환에 해당하는 orthogonal matrix를 양쪽에 곱하면 되는거였다... OTL 다음 문제는 1-bit full adder를 reversible하게 구성하라는 문제. 진리표는 계속 permutation으로 쓰도록 하자.
1-bit full adder (A+B=S, C carry)
Z redundant(0,4)
CAB->ZCS
0->Z0
1->Z1
2->Z1
3->Z2
4->Z1
5->Z2
6->Z2
7->Z3
THIS CANNOT WORK!
보면 Z가 취할 수 있는 값이 두 가지밖에 없는데 Z1과 Z2가 각각 세 번 나오므로 3in-3out 게이트로는 가역연산을 구할 수 없다는 것을 알 수 있다. 그러므로 4in-4out 게이트를 구성해야 한다. 이건 Feynman Lectures on Computation에 언급된 내용. 다양하게 구성할 수 있겠지만 한가지 예시는 다음과 같다.
1-bit full adder (A+B=S, C carry) - hex
X redundant(0,8)
Y, Z redundant(0,4,8,C)
XCAB->YZCS
0->YZ0=0
1->YZ1=1
2->YZ1=4+1=5
3->YZ2=2
4->YZ1=8+1=9
5->YZ2=4+2=6
6->YZ2=8+2=A
7->YZ3=3
8->8
9->4
A->7
B->B
C->C
D->D
E->E
F->F
16진법을 이용해서 permutation을 구성해봤다. 보면 알겠지만 중복될 경우 0, 4, 8 순서대로 더해줘 다른 값이 나오도록 조정해주었다. 같은 색은 순환하는 성분들을 표시해준 것.
permutation이기 때문에 얻는 특이한(?) 성질은 이 연산을 반복하면 언젠가는 원래 값으로 돌아온다는 사실이다. 어쨌든 permutation group은 부분군으로 cyclic group을 형성하기 때문.
XCAB=F(YZCS) -> F^6=I , i.e. x=F(F(F(F(F(F(x))))))
아직까지는 초반부라 재미있는데, 뒤쪽에 가서도 흥미를 잃지 않았으면 한다.
rev. 01 Nov 2013
바로 다음에 나오는 Fredkin 게이트를 이용해 모든 논리연산 구현하기.
Fredkin Gate(Controlled exchange gate)
CAB
0->0
1->1
2->2
3->3
4->4
5->6
6->5
7->7
As AND gate: input X0Y->X(X∧Y)(¬X∧Y)
As NOT/Fanout gate: input X10->X(¬X)X
=>Construct NAND => Everything can be built out of NAND gates
Conway's Game of Life라는 글에 올린 코드를 실행시켜보면 파일 경로를 입력하라는 창이 뜬다. 물론 파일 경로에 빈칸(space)이 들어가도 되도록 만들었다.[각주:1] scanf로는(%s를 이용한 경우) 빈칸이 포함된 string을 읽지 못하기 때문에 다른 함수를 이용해야 한다. 링크된 글의 코드에서 빈칸이 포함된 string을 읽는 함수만 가져왔다.
int locate(char loc[])
{
int i;
printf("File location(length at most %d):\n", maxpath);
while(1)//loop until input is proper
{
for(i=0;i<=maxpath;i++) loc[i]=0;//initialize string
gets(loc);
if(loc[0]) break;
}
if(loc[maxpath]!=0) {printf("Path is too long.\n"); return 0;}
return 1;
}
main함수에서 이 함수에 집어넣을 array의 크기를 char location[maxpath+1]으로 선언했기 때문에 에러가 나지는 않는다. 다음은 main함수의 첫 부분.
int main()//main function
{
int i,time;
char a[scale*scale]={},loc[maxpath+1]={}, cell[2];
...
조금 생소한(?) gets라는 함수가 하나 보이는데 이 녀석은 return(new line)이 나타날 때까지 글자를 전부 읽고 string에 저장하는 역할을 한다. 문제는 gets가 쓰이기 전에 scanf가 쓰였을 경우이다. scanf는 new line이 있으면 그 전까지만 읽기 때문이다. 아직 new line이 메모리에 남아있기 때문에 gets 함수는 newline을 읽는다. 의도치 않게 자동으로(?) 입력되어 버리는 것이다. 그걸 막기 위해서 loop를 이용했다.
이렇게 input이 꼬인다는 것도 문제이기는 하지만, 사실 가장 큰 문제는 구해 놓은 메모리보다 더 큰 정보를 저장할 때 생긴다. gets 함수를 쓰면 프로그램이 지정해놓은 공간 '밖에도' 저장이 되기 때문에 엉뚱한 정보가 날아갈 위험이 있는 것이다. 때문에 보통은 fgets 함수를 쓰는 것이 더 안전하다고 한다. 알아서 응용해 보시길 ㅇ-ㅇ
"C:\my documents and settings\my documents\abc.txt" 와 같은 string을 사용자가 입력하도록 만들었다. [본문으로]
c언어로 세포가 점차 퍼저나가는 것을 시뮬레이션하는 프로그램 짜는게 과제이다. 전체 공간의 크기는 50x50개.
세포 주변의 4칸 이상이 다른 세포로 차 있으면 그 세포는 과잉밀집으로 사망.
세포 주변의 1칸 이하만 세포가 있으면 그 세포는 고립으로 사망.
세포 주변의 2~3칸에 이웃하는 세포가 있으면 그 세포는 그대로 살아간다.
세포 주변의 3칸에 이웃하는 세포가 있으면 그 지점에 세포가 자라난다.
ex>
▒▒▒▒▒
▒▦▦▦▒
▒▦▦▦▒
▒▒▒▒▒
상태에서
▒▒▦▒▒
▒▦▒▦▒
▒▦▒▦▒
▒▒▦▒▒
빨간 애들은 인구밀도가 높아서 사망. 아래 녀석은 주변에 무언가 닿지 않는 한 그대로 무한정 살아간다.[각주:1]
뭐 이런 프로그램을 짜란다. 인터넷 뒤져보니 Conway's Game of Life라는 시뮬레이션인듯. 이런 종류를 가리켜 Cellular Automaton이라고 부르는 듯 하다. 흥미가 생겨서 이것 저것 찾아보았는데, 70년대부터 여러가지 이유로 유명했던 시뮬레이션인 모양이다.
단, 이렇게 세포가 배치된 모양은 세개의 외부파일로부터 불러들여오거나 무작위로 생성하도록 하는 것이 조건.
외부파일 세개를 지정하는게 귀찮아서 어떤 파일이든 주소를 입력만 하면 불러올 수 있도록 만들었다. <space>가 포함된 string을 받아오게 하는게 좀 힘들긴 했지만 어쨌든 성공... 무작위생성은 인터넷에서 난수생성 알고리즘을 참고해가며 만들었다.
마지막 상태를 파일로 출력하는 기능도 추가했는데, 돌리면서 장난치다 보니까 자기가 출력한 파일을 제대로 못 읽는 상황이 발생해서 부랴부랴 디버깅을 했다. 문제는 그랬더니 입력을 조금 이상하게 받더라는 것(...) 이번에는 문제없을거다. 한줄이 50글자가 넘어가지 않는 한...
다 제작한 뒤에 한 나흘정도 잡고 장난치고 놀면서 최대한 메모리를 적게 잡아먹고 계산이 빠르도록개선한 결과물이다. 그리고 잘못 알고 있었던 진화조건(?)때문에 부랴부랴 알고리즘을 바꾼 것도 있고.(그래도 비슷한 알고리즘들 중에서는 계산이 빠른 편일듯)
unsigned long random(unsigned long i)//pseudorandom number generator
{
if(i && time(0)%2) return (unsigned long)(i>>1)|(((i^(i>>10)^(i>>30)^(i>>31))&1)<<31);
else return (unsigned long)(i*1103515245+12345)%0x100000000;
}
void grow(char a[])//determines the growth of whole grid
{
int i;
char b[scale*scale]={}, j;//j will be used as a number
for(i=0;i<scale*scale;i++) if(a[i]) for(j=0;j<9;j++)
if(j!=4 && i/scale+j/3!=0 && i%scale+j%3!=0 && i/scale+j/3<=scale && i%scale+j%3<=scale)
b[(i/scale-1+j/3)*scale+i%scale-1+j%3]++;//if the cell is alive, neighboring grid's count goes up
for(i=0;i<scale*scale;i++)
{
if(b[i]==3 || a[i] && b[i]==2) a[i]=1;//lives&generated when 3 cells are neighboring, lives when 2 cells are neighboring
else a[i]=0;
}
}
void printarr(char a[],char live,char dead)//prints grid status
{
int i;
for(i=0;i<scale*scale;i++)
{
if(i%scale==0&&i!=0) printf("\n");//new line is entered when nonzero i is a multiple of scale
if(a[i]) printf("%c", live);
else printf("%c", dead);
}
}
int locate(char loc[])
{
int i;
printf("File location(length at most %d):\n", maxpath);
while(1)//loop until input is proper
{
for(i=0;i<=maxpath;i++) loc[i]=0;//initialize string
gets(loc);
if(loc[0]) break;
}
if(loc[maxpath]!=0) {printf("Path is too long.\n"); return 0;}
return 1;
}
int fileread(char a[], char loc[])//opens a file, then returns alive cells to the grid
{
FILE *fp;
char alive[2];
int i,c;
printf("Input from a text file.\n");
if(!locate(loc)) {system("pause"); return 0;}
if((fp=fopen(loc,"r"))==0) {printf("File not found.\n"); system("pause"); return 0;}
while(1)
{
printf("Reading grid from <%s>\nWhich character represents alive cells?\n",loc);
scanf("%s",alive);//calling by %c somehow causes an error, so I used %s
if(alive[1]!=0) continue;
else break;
}
loc[0]=0;
for(i=0;i<scale*scale;i++)
{
if((c=fgetc(fp))==alive[0]) {a[i]=1; loc[0]=1;}
else if(c=='\n') if(loc[0]&&!(i%scale))i--;//fixes the problem of reading its output file differently
else i=scale*((i/scale)+1)-1;//when line is changed, grid line is changed
else if(c==EOF) break;//when file has ended, escape the loop
else loc[0]=1;//fixes the problem of reading its output file differently
}
printf("Grid is loaded.\n");
fclose(fp);
return 1;
}
int filewrite(char a[],char loc[],char live, char dead, int time)//saves the grid onto the output file
{
FILE *fp;
int i;
printf("Export grid to an output file.\n");
if(!locate(loc)) return 0;
printf("Saving the last grid in <%s>...\n",loc);
if((fp=fopen(loc,"w"))==0){printf("Save error: cannot open file.\n"); return 0;}
for(i=0;i<scale*scale;i++)
{
if(i%scale==0&&i)if(fputc('\n',fp)==EOF)goto writeerror;
if(a[i]) {if(fputc(live,fp)==EOF)goto writeerror;}
else if(fputc(dead,fp)==EOF)goto writeerror;
}
if(fprintf(fp,"\n\n Time:%d",time)<0) goto writeerror;
fclose(fp); printf("Saved.\n"); return 1;
writeerror:
printf("Save error: cannot write.\n"); fclose(fp); return 0;
}
void generate(char a[],int n)//generates random grid based on approximate cell number
{
int i;
unsigned long j=7;
if(n<=0) n=random(time(0))%(scale*scale);
else n=n%(scale*scale);
printf("Approximate cell number is %d.\n",n);
for(i=0;i<n;i++) {j=random(j); a[j%(scale*scale)]=1;}
}
int main()//main function
{
int i,time;
char a[scale*scale]={},loc[maxpath+1]={}, cell[2];
printf("John Conway's Game of Life - on a grid of %d x %d\nFor how long would you like to run the game?\n", scale, scale);
scanf("%d", &time);
gets(loc);//absorbs input error(such as writing a string)
while(1)//determining representation of cells
{
printf("An alive cell would look like: \n");
scanf("%s", cell);//calling by %c somehow causes an error, so I used %s
if(cell[1]!=0) continue;
printf("Alive cell is shown as %c. Enter 1 to confirm.\n",cell[0]);
scanf("%d", &i);
if(i) break;
}
while(1)//input determination
{
printf("Do you wish to start from any input file?(1 to read from an input file)\n");
scanf("%d", &i);
if(i!=1) break;
else if(fileread(a,loc)) break;
}
if(i!=1)//random input
{
printf("Choose approximate cell number(1~%d, 0 for random selection).\n", scale*scale-1);
scanf("%d",&i);
generate(a,i);
}
system("pause");
i=0; while(1)
{
system("cls");
printarr(a,cell[0],' ');
printf("\n\n Time:%d\n",i);
system("pause");
if(i>=time) break;
grow(a);
i++;
}
printf("\n\nEnd of simulation.\n");
while(1)
{
printf("Do you wish to save the last grid?(1 to save)\n");
scanf("%d",&i);
if(i!=1) break;
else if(filewrite(a,loc,cell[0],' ',time)) break;
}
printf("Programmed by Dexter.\n http://dexterstory.tistory.com\n");
system("pause");
return 0;
}
#define에서 scale은 전체 grid의 크기와 관련된 숫자고, maxpath는 저장시 입력할 수 있는 경로의 길이와 관련된 숫자다. 전체 code 길이는 162줄, main 함수를 포함해서 선언한 함수의 수는 8개.
gets()함수와 goto문, system call은 되도록이면 쓰지 말라는데 난 그런거 따위...
(그런데 system call 없이 화면을 지우는 방법은 도저히 못 찾겠다... 잠깐 멈추는 것도 경우에 따라서는 제대로 작동 안 하는 것 같고...)
전 적절한 카피레프트를 지지합니다.
완벽하게 최적화되었다고는 못 하니까 알아서 고쳐 쓰세요 -.-;;
전에 썼던 글에서 조건을 잘못 달았다 OTL. 어쩐지 예시와는 전혀 다른 방향으로 진화하더라... [본문으로]