◎ 2개의 n * n 행렬(n = )을 곱하는 표준 알고리즘과 쉬트라센 알고리즘을 구현하는 프로그램을 각각 작성하라. 작성한 프로그램을 각각 돌려서 수행시간을 비교하라.
○ 쉬트라센 알고리즘
를 이용하여
void strassen (int n
n * n_matrix A,
n * n_matrix B,
n * n_matrix C)
{
if ( n <= threshold)
표준 알고리즘 C = A * B 계산
else {
A를 4개의 부분행렬로 분할
B를 4개의 부분행렬로 분할
쉬트라센 알고르즘으로 C = A * B 계산
}
}
○ 표준 알고리즘
가로 세로를 행렬로 만든 뒤 각각을 곱
○ 프로그램
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
#define MAX_SIZE 10
//행렬의 최대 크기는 10으로 한다
class matrix
{
private:
int a[MAX_SIZE][MAX_SIZE], b[MAX_SIZE][MAX_SIZE], result[MAX_SIZE][MAX_SIZE];
int n;
long int start_time, end_time;
void strassen(int n, int a1[][MAX_SIZE], int b1[][MAX_SIZE], int c1[][MAX_SIZE]);
public:
void init();
const void print(char *msg);
const void print();
void multiplication();
void strassen_start();
};
//쉬트라센 알고리즘 시작
void matrix::strassen_start()
{
double start, stop, timer;
start = clock();
//수행 시간을 구하기 위해 start에 시작 시간을 넣는다
int i, j;
//계산된 결과가 저장될 배열을 만든다
for( i=0; i<n; i++)
for( j=0; j<n; j++)
result[i][j]=0;
strassen( n, a, b, result);
//쉬트라센 함수를 호출한다
stop = clock();
timer = ((double)(stop-start)) / CLK_TCK ;
cout << timer << endl;
//쉬트라센 함수를 호출후 계산을 마치고 돌아온 시간을 기록하여 수행시간을 계산한다
}
//쉬트라센 함수
void matrix::strassen( int n, int a1[][MAX_SIZE], int b1[][MAX_SIZE], int c1[][MAX_SIZE])
{
int i,j;
int m1[MAX_SIZE][MAX_SIZE], m2[MAX_SIZE][MAX_SIZE],
m3[MAX_SIZE][MAX_SIZE], m4[MAX_SIZE][MAX_SIZE],
m5[MAX_SIZE][MAX_SIZE], m6[MAX_SIZE][MAX_SIZE],
m7[MAX_SIZE][MAX_SIZE];
int temp1[MAX_SIZE][MAX_SIZE], temp2[MAX_SIZE][MAX_SIZE];
int sm1, sm2, sm3, sm4, sm5, sm6, sm7;
if( n<=2){
//만약 행렬의 크기가 2라면 바로 곱셈을 한다
//그 이유는 손익분기점이 2이기 때문이다
sm1=(a1[0][0] + a1[1][1]) * (b1[0][0] + b1[1][1]);
sm2=(a1[1][0] + a1[1][1]) * b1[0][0];
sm3=a1[0][0]*(b1[0][1] - b1[1][1]);
sm4=a1[1][1]*(b1[1][0] - b1[0][0]);
sm5=(a1[0][0] + a1[0][1]) * b1[1][1];
sm6=(a1[1][0] - a1[0][0]) * (b1[0][0] + b1[0][1]);
sm7=(a1[0][1] - a1[1][1]) * (b1[1][0] + b1[1][1]);
c1[0][0] = sm1 + sm4 - sm5 + sm7;
c1[0][1] = sm3 + sm5;
c1[1][0] = sm2 + sm4;
c1[1][1] = sm1 + sm3 - sm2 + sm6;
}
else{
//손익 분기점을 넘는다면
for(i = 0; i < n/2 ; i++)
for (j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i][j] + a1[i + n/2][j + n/2];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i][j] + b1[i + n/2][j + n/2];
strassen(n/2,temp1,temp2,m1);
//을 계산하여 쉬트라센 호출
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i + n/2][j] + a1[i + n/2][j + n/2];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i][j];
strassen(n/2,temp1,temp2,m2);
//계산하여 쉬트라센호출
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i][j];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i][j + n/2] - b1[i + n/2][j + n/2];
strassen(n/2,temp1,temp2,m3);
for(i = 0; i < n/2 ; i++)
for(j = 0; j <n/2 ; j++ )
temp1[i][j] = a1[i + n/2][j + n/2];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i+n/2][j] - b1[i][j];
strassen(n/2,temp1,temp2,m4);
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i][j] + a1[i][j + n/2];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i + n/2][j + n/2];
strassen(n/2,temp1,temp2,m5);
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i+n/2][j] - a1[i][j];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i][j] + b1[i][j + n/2];
strassen(n/2,temp1,temp2,m6);
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp1[i][j] = a1[i][j+n/2] - a1[i + n/2][j + n/2];
for(i = 0; i < n/2 ; i++)
for(j = 0; j < n/2 ; j++ )
temp2[i][j] = b1[i+n/2][j] + b1[i + n/2][j + n/2];
strassen(n/2,temp1,temp2,m7);
for(i = 0 ; i < n/2 ; i++ )
for(j = 0 ; j < n/2 ; j++ )
c1[i][j] = m1[i][j] + m4[i][j] - m5[i][j] + m7[i][j];
for(i = 0 ; i < n/2 ; i++ )
for(j = 0 ; j < n/2 ; j++ )
c1[i][j+n/2] = m3[i][j] + m5[i][j];
for(i = 0 ; i < n/2 ; i++ )
for(j = 0 ; j < n/2 ; j++ )
c1[i+n/2][j] = m2[i][j] + m4[i][j];
for(i = 0 ; i < n/2 ; i++ )
for(j = 0 ; j < n/2 ; j++ )
c1[i+n/2][j+n/2] = m1[i][j] + m3[i][j] - m2[i][j] + m6[i][j];
//이런 식으로 계산하여 각각 쉬트라센을 호출한다
}
}
void matrix::init()
//행렬의 크기를 결정
{
int i, j;
do{
cout << endl << endl;
cout << "행렬의 크기를 결정 (2의 제곱수)" << endl;
cout << ">> ";
cin >> n;
//행렬의 크기를 결정하기 위해 사용자로부터 행열의 크기를 부여받는다
if( n > MAX_SIZE) continue;
i= n;
j=0;
do{
i=i/2;
}while( i != 1);
if( j == 0) break;
}while(1);
srand( ( unsigned)time( NULL));
//시간함수를 호출하여 랜덤함수를 호출한다
for( i=0; i<n; i++)
for( j=0; j<n; j++){
a[i][j] = rand()%10;
b[i][j] = rand()%10;
//각각의 랜덤함수는 10보다 작은수로 결정한다.
}
}
void matrix::multiplication()
//표준 알고리즘을 이용하여 행렬을 계산한다
{
double start, stop, timer;
start = clock();
//역시 시간을 계산하기위해 start에 현재 시간을 넣고
int i, j, k;
for( i=0; i<n; i++)
for( j=0; j<n; j++)
result[i][j]=0;
for( i=0; i<n; i++)
for( j=0; j<n; j++){
result[i][j] = 0;
for( k=0; k <n; k++)
result[i][j]=result[i][j]+a[i][k]*b[k][j];
}
//각각 행렬을 가로세로로 각각 곱해서 표준 알고리즘으로 계산
stop = clock();
timer = ((double)(stop-start)) / CLK_TCK ;
cout << timer << endl;
//걸린 시간을 출력한다
}
const void matrix::print()
//처음 수를 입력받아 만들어진 두 개의 행렬을 출력하는 함수
{
int i, j;
cout << "----------" << endl << " 2개의 n * n 행렬 " << endl << "---------" << endl;
for( i=0; i<n; i++){
for( j=0; j<n; j++){
cout.width(3);
cout << a[i][j];
}
cout << " ";
for( j=0; j<n; j++){
cout.width(3);
cout << b[i][j];
}
cout << endl;
}
}
const void matrix::print( char *msg)
{
int i, j;
cout << "============" << endl << msg << endl << "============" << endl;
for( i=0; i<n; i++){
for( j=0; j<n; j++){
cout.width(7);
cout << result[i][j];
}
cout << endl;
}
}
main()
//main 이지만 하는일은 모든 함수들의 계산한 결과값을 출력하는 것만 수행
{
matrix m;
m.init();
m.print();
m.multiplication();
m.print("표준 알고리즘");
m.strassen_start();
m.print("쉬트라센 알고리즘");
}
○ 두 개의 알고리즘을 사용하여 돌렸으나 시간은 미세하여 0으로밖에 출력 되지 않았음
○ 출력 결과
두 개의 행렬을 만들고 쉬트라센 알고리즘을 사용하여 계산한 결과값과
표준 알고리즘을 이용하여 계산한 결과 값은 같았으나 시간의 미세한 차이로 두 알고리즘의 시간 차이는 알아내지 못하였음
참고로 이 자료는 인터넷에 공개된 자료를 정리하여 올렸습니다.