Steganography
Today, reading all kind off things after hours, I've found an interesting subject : Steganography. What this term really means : well, it represents a technique of hiding something by changing it's form or by encapsulated it in something else. This way of covering something is used since long ago, from the times of ancient Greeks ( where they used head tattooed slaves to send messages ).But ,steganography have become more known with the introduction of digital photos. Why, because photos permit hiding information very well without any suspicion. So called Digital steganography can be used where cryptography isn't possible or legal. We can easily send coded messages into photos to our Chinese fellows, without any problem. Sadly , digital steganography has a bad part. I can be ( and it was ) used by terrorist to send key instructions. Anyway, here is a site where you can play with this thing : http://mozaiq.org/
First post
Welcome to my blog. In my first post I will talk have a programing topic, more exactly a Divide and conquer problem : Matrix multiplication using this programming technique. We will show the simplest way, using a particular case of matrices, square matrices with dimension being an even number (in order to keep the thing clear and concise ).
The idea is the follow : split each matrix in 4 square matrices till the dimension of this matrices is 2 . In this case, we will apply the known matrix multiplication. Our function will have as arguments the input matrices, their dimension , the left upper corner coordinates ( line and column ) and the current dimension.
When the algorithm reaches matrices with dimension equal to 2 , proper elements in the matrix result are computed.
Here is the algorithm, written in C :
#include <stdio.h> #include <stdlib.h> int **d = NULL ; // global result matrix /* * reading function * file_name file input name * n dimension of the matrix * a, b operand matrices */ void read(char* file_name, int *n, int ***a, int ***b) { int i, j; FILE *fd = fopen(file_name, "r"); // dimension of the matrix fscanf(fd, "%i", n); // elements of A *a = (int**)malloc((*n) * sizeof(int*)); for (i = 0; i < *n; i++) { (*a)[i] = (int*)malloc((*n) * sizeof(int)); for (j = 0; j < *n; j++) { fscanf(fd, "%i", &((*a)[i][j])); } } // elements of B *b = (int**)malloc((*n) * sizeof(int*)); for (i = 0; i < *n; i++) { (*b)[i] = (int*)malloc((*n) * sizeof(int)); for (j = 0; j < *n; j++) { fscanf(fd, "%i", &((*b)[i][j])); } } fclose(fd); } /* * iterative algorithm for multiplication * n dimension * a, b operands * c result */ void matrix_multiply(int n, int **a, int **b, int ***c) { int i, j, k; *c = (int**)malloc((n) * sizeof(int*)); // inmultire matrice for (i = 0; i < n; i++) { (*c)[i] = (int*)malloc((n) * sizeof(int)); for (j = 0; j < n; j++) { (*c)[i][j] = 0; for (k = 0; k < n; k++) { (*c)[i][j] += a[i][k] * b[k][j]; } } } } /* * compare matrices * n dimension * a,b matrices * return 1/0 different/equal */ int matrix_cmp(int n, int **a, int **b) { int i, j; if ( (a == NULL) || (b == NULL) ) { return 1; } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (a[i][j] != b[i][j]) { return 1; } } } return 0; } /* * free memory * n dimension * a matrix */ void free_matrix(int n, int **a) { int i; for (i = 0; i < n; i++) { free(a[i]); } free(a); } void print_matrix(int n, int **a) { for(int i=0; i<n; i++) { for (int j=0; j<n; j++) { printf("%i ",a[i][j]); } printf("\n"); } } void DI_mm(int n, int **a, int **b, int lia, int cia, int lib, int cib, int dim) { int i; if ( dim == 2 ) { d[lia][cib] += a[lia][cia] * b[lib][cib] + a[lia][cia + 1] * b[lib + 1][cib] ; d[lia][cib + 1] += a[lia][cia] * b[lib][cib + 1] + a[lia][cia + 1] * b[lib + 1][cib + 1] ; d[lia + 1][cib] += a[lia + 1][cia] * b[lib][cib] + a[lia + 1][cia + 1] * b[lib + 1][cib] ; d[lia + 1][cib + 1] += a[lia + 1][cia] * b[lib][cib + 1] + a[lia + 1][cia + 1] * b[lib + 1][cib + 1] ; } else { dim = dim / 2 ; DI_mm(n,a,b,lia,cia,lib,cib,dim); // 1 DI_mm(n,a,b,lia,cia + dim,lib + dim,cib,dim); // 2 DI_mm(n,a,b,lia,cia,lib,cib + dim,dim); // 3 DI_mm(n,a,b,lia,cia + dim,lib + dim,cib + dim,dim); // 4 DI_mm(n,a,b,lia + dim,cia,lib,cib,dim); // 5 DI_mm(n,a,b,lia + dim,cia + dim,lib + dim,cib,dim); // 6 DI_mm(n,a,b,lia + dim,cia,lib,cib + dim,dim); // 7 DI_mm(n,a,b,lia + dim,cia + dim,lib + dim,cib + dim,dim); // 8 } } int main(int argc, char** argv) { int n; // dimensiune matrice int **a, **b, **c; // matrices char *in_file; // in file if (argc < 2) { fprintf(stderr,"Usage %s in_file\n", argv[0]); exit(1); } in_file = argv[1]; // read matrices and their dimension read(in_file, &n, &a, &b); // iterative matrix multiply (c = a * b) matrix_multiply(n, a, b, &c); // matrix multiplication using DivideAndConquer (d = a * b) d = (int**)malloc((n) * sizeof(int*)); for (int i = 0; i < n; i++) { d[i] = (int*)malloc((n) * sizeof(int)); } for (int i = 0; i < n ;i++) for(int j = 0; j < n ;j++) d[i][j] = 0; printf("a = \n"); print_matrix(n,a); printf("\nb = \n"); print_matrix(n,b); printf("\nc = \n"); print_matrix(n,c); DI_mm(n,a,b,0,0,0,0,n); printf("\nd = \n"); print_matrix(n,d); // verificare rezultat if (matrix_cmp(n, c, d)) { printf("Wrong answer\n"); } else { printf("Corect\n"); } // free memory free_matrix(n, a); free_matrix(n, b); free_matrix(n, c); // TODO free_matrix(n, d); return 0; }