Matrix Multiplication: 3x3 and 3x1

Formula:

| a11 a12 a13 |    | b1 |    | a11*b1 + a12*b2 + a13*b3 |
| a21 a22 a23 | x | b2 | = | a21*b1 + a22*b2 + a23*b3 |
| a31 a32 a33 |    | b3 |    | a31*b1 + a32*b2 + a33*b3 |

For arrays:

| a11 a12 a13 |      | a[0][0] a[0][1] a[0][2] |
| a21 a22 a23 |  =  | a[1][0] a[1][1] a[1][2] |
| a31 a32 a33 |      | a[2][0] a[2][1] a[2][2] |

| b1 |    | b[0] |
| b2 | = | b[1] |
| b3 |    | b[2] |

| c1 |    | a11 a12 a13 |    | b1 |    | a[0][0]*b[0] + a[0][1]*b[1] + a[0][2]*b[2] |
| c2 | = | a21 a22 a23 | x | b2 | = | a[1][0]*b[0] + a[1][1]*b[1] + a[1][2]*b[2] |
| c3 |    | a31 a32 a33 |    | b3 |    | a[2][0]*b[0] + a[2][1]*b[1] + a[2][2]*b[2] |

Code:   

c[0] = a[0][0]*b[0] + a[0][1]*b[1] + a[0][2]*b[2]
c[1] = a[1][0]*b[0] + a[1][1]*b[1] + a[1][2]*b[2]
c[2] = a[2][0]*b[0] + a[2][1]*b[1] + a[2][2]*b[2]

Matrix Inverse - 3x3

Operations of matrices of 3x3 are very common in day to day applications. Because the dimensions are already known, its better to avoid using a for-loop because of the extra computation involved in finding the subscript values.

Following is a quick formula for the inverse of a 3x3 matrix (implemented as a 2D array).

Formula

The inverse of a 3x3 matrix:
| a11 a12 a13 |-1                   |   a33a22-a32a23  -(a33a12-a32a13)   a23a12-a22a13   | 
| a21 a22 a23 |    =  1/DET *  | -(a33a21-a31a23)   a33a11-a31a13  -(a23a11-a21a13) |
| a31 a32 a33 |                      |   a32a21-a31a22  -(a32a11-a31a12)   a22a11-a21a12   |

where DET is the determinant of the matrix, i.e.

DET  =  a11(a33a22 - a32a23) - a21(a33a12 - a32a13) + a31(a23a12 - a22a13)

For 2D array

Moving on from matrices to 2D arrays

| a11 a12 a13 |        | mat[0][0] mat[0][1] mat[0][2] |

| a21 a22 a23 |   =   | mat[1][0] mat[1][1] mat[1][2] |

| a31 a32 a33 |        | mat[2][0] mat[2][1] mat[2][2] |

and,

| a11 a12 a13 |-1     | inv[0][0] inv[0][1] inv[0][2] |

| a21 a22 a23 |   =   | inv[1][0] inv[1][1] inv[1][2] |

| a31 a32 a33 |        | inv[2][0] inv[2][1] inv[2][2] |

Hence for code, the assignments are:

inv[0][0] = mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]

inv[0][1] = mat[2][1] * mat[0][2] - mat[2][2] * mat[0][1]

inv[0][2] = mat[1][2] * mat[0][1] - mat[1][1] * mat[0][2]

inv[1][0] = mat[2][0] * mat[1][2] - mat[2][2] * mat[1][0]

inv[1][1] = mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]

inv[1][2] = mat[1][0] * mat[0][2] - mat[1][2] * mat[0][0]

inv[2][0] = mat[2][1] * mat[1][0] - mat[2][0] * mat[1][1]

inv[2][1] = mat[2][0] * mat[0][1] - mat[2][1] * mat[0][0]

inv[2][2] = mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1] 

DET =   mat[0][0]*inv[0][0] + mat[1][0]*inv[1][0] + mat[2][0]*inv[0][2]

Forgotten rules of C/C++: Part 1

Following is a list of important points people find very convenient to forget. This is the first article of a series

·   For bitwise operations, operand is promoted to "int" before evaluation.

unsigned char I = 0x80;
printf("%d", i<<1 nbsp="nbsp">  256

·   printf(5 + "intelligent");  => “ligent”

      Number specifies displacement to string pointer. This is the same as doing…

char *s = "intelligent";
s += 5;
printf("%s",s);

·    In a switch statement, initializations are allowed in the beginning, but they are NOT EXECUTED. The control is passed directly to an executable statement, i.e. matching case statement.

switch(1)
{
     printf("hello");                         => NOT PRINTED
     case 1:printf("case 1");break;
     case 2:printf("case 2");break;
}

·   The ++ operator means ``add one to a variable'' and DOES NOT work with constants.

int i = ++ 3 ;
printf("%d", i);                              =>  GARBAGE VALUE

·   Static arrays are constant! The base address cannot be modified. Any pointer arithmetic that attempts to do so causes a compilation error.

int arr[ 10 ] ;                     => “arr” is a constant. It is defined to be the address, &arr[ 0 ].

·   Array pointer logic for an array, “int a[10][10];”

      a+1
=> a[1]
=> &a[1][0]

·    In pointer arithmetic, addition and subtraction are valid operations, (as long as they don’t try to change the base address of the pointer) but pointer division and pointer multiplication are INVALID.

Code Snippet - Summed Area Table

SUMMED AREA TABLE
Using the method described here, I have written the following code to calculate a summed area table. A sample image table of 5x5 dimensions has been assumed for simplicity. The code snippet and its results are given below.

CODE
// assumed height and width of the input table
#define height 6
#define width 6

// input matrix - 5x5
long matrix[ height - 1][width -1] = {{5,2,3,4,1},{1,5,4,2,3},{2,2,1,3,4},{3,5,6,4,5},{4,1,3,2,6}};
// output matrix - 6x6
long sat[height][width];

void sat_matrix(){
 // formula variables
      int a=0, b=0, c=0, m=0;
      // matrix traversal loop for calculating the SAT
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
                     // following code picks up array elements within bounds and picks "zero"
                     // for values outside bounds.
a = (i-1>=0)?sat[i-1][j]:0;
b = (j-1>=0)?sat[i][j-1]:0;
c = ((i-1>=0)&&(j-1>=0))?sat[i-1][j-1]:0;
m = ((i-1>=0)&&(j-1>=0))?matrix[i-1][j-1]:0;
                      // ACTUAL FORMULA FOR SUMMED AREA TABLE
sat[i][j] = m + a + b - c;
}
}
}

PROCEDURE:
Use the function as it is and write supporting code. The code written was compiled using g++ compiler in cygwin environment

OUTPUT:

CUDA Emulator

The CUDA emulator is a software that duplicates (or emulates) the functions of a computer system with a CUDA-enabled card in a computer system with no such hardware, so that the emulated behavior closely resembles the behavior of the real system. This software package is mainly aimed to empower developers and students who do not have access to Nvidia GPU's.


Initially, the CUDA Toolkit came with an emulator "built into" the CUDA compilor; "nvcc". Later, from versions after 3.0, the emulator was dropped. The last version that supports the emulator is v2.3, and can be downloaded from the CUDA Toolkit archives here.


But thankfully, several third parties have contributed to produce several emulation options that will be listed in this space shortly.

What your C\C++ teachers didnt teach you...or forgot!!!

Well their is no end to C\C++ and their never will be, simply because C++ can evolve to suit whats being demanded... Even this infinite syllabus has certain features that all of you should know. You might know most of this stuff but mind you many do not have that privilege.

Level - C++ is NOT a "High Level Language", or atleast not a conventional HLL because of its heavy use of low level features...

Header Files - YES!! you can make your own, it should only have class and function declarations and definitions in a related "library" file...but you can avoid that if you want and have entire classes as headers. They can be included just as normal header files are included in programs.

Graphics - C++ has a very primitive DOS based working environment but does support very simple graphics. More advanced graphics can also be supported by designing the right API for your own graphics driver. You can use graphics to make anything from games to animations...although that might get really frustrating and tiring!!!

Friend Class - A class can declare other classes/functions as friends to allow access to non-public class members unaccessible to outside code. Of course this was taught, but what was not told is that 'friend' is a USELESS concept. It can be used to split data between multiple classes, something that can be avoided.

IDEs - NO, the world doesnt end after Turbo C, in fact TC is very much dead nowadays. GUI based Integrated Development Environments are openly available for download that do not need (crappy) DOS to run and are much useful when it comes to more modern Operating Systems like Windows 7. But yes there is a catch, you need to download and install compilers all by yourself.

Templates - An advanced concept, templates are used on both  functions and classes. All they do is to extend the functionality of a class that has not been defined yet. Now this template function/class can use the undefined class as a regular datatype!! Templates look somewhat like this...
template ...other datatype> 
function/class declaration;
There can be multiple templates for the same class.

Keyword "volatile" - A type qualifier that indicates that the value of the variable will change value depending on external conditions, like hardware, operating system, network, etc. Then the compiler will always work on the current value every time a volatile variable is used.

Keyword "mutable" - A 'mutable' data member can be assigned values by a 'const' method.

New style casts - Forget c-style casts that you were taught and move on to the following for lesser bugs...

• static_cast, 
• dynamic_cast, 
• reinterpret_cast and 
• const_cast)

Threading - Several libraries that allow threading are now open source....


Exception Handling - Same as Java....

Garbage Collection - As I mentioned in my previous post, Garbage collection is simply automatic memory management incorporated into runtime. C++ was much criticized for its lack of a Garbage Collector. But automatic memory management is possible through external libraries and Smart Pointers. Also, a Garbage colletor by Boehm-Demers-Weiser can be used. It replaces malloc in C and new in C++

Interrupts - Interrupts, like the name suggests, disrupt the linear flow of control to execute certain subroutines. After that the program execution resumes from where it was suspended. Interrupts are messages to the CPU to suspend the program, execute a small executable and resume its activity. These executables are sets of instructions that are already stored in the CPU. Interrupts can be used to anything a library function can do and much beyond. Consult your IVT(Interrupt Vector Table) for details.

Register Variables - Variables can be stored directly onto CPU's registers, (which is storage available on the CPU). This feature reduced cost of accessing RAM. In embedded systems, storage is done directly onto the processor's registers as primary storage.

Hardware Application - Embedded C and C++ are dialects for embedded systems. They work directly on a processor's registers and interrupts using the familiar syntax. The focus here is on using low-level features to work closely with memory. A common example is the language used with Keil.

Updates - C++ has constantly evolved over the years thanks to a C++ Standard that is maintained as well as updated. The first was ANSI-C++ and the current is C90, also the next modern dialect of C++ will be called C++0x

Flood-fill Algorithm - Working Demo

This is a working code to demonstrate the Flood-fill or Brushfire or Wavefront Algorithm in C++. The main crux of this code however, is the Flood method.

Flood-Fill algorithm calculates relative cost of moving to a Block of an array and fills all consecutive blocks with numbers corresponding to cost. The Source is tagged as 0 as there is no additional cost to move there.
Here is the code:


#include <iostream.h>
#include <conio.h>


#define GridMaxX 5
#define GridMaxY 5


int Grid[GridMaxX][GridMaxY],r,c;
// r and c are coordinates of filling source.


void DisplayGrid()//Display the grid
{
for(int i=0;i<=GridMaxX-1;i++)
{
for(int j=0;j<=GridMaxY-1;j++)
cout<<"\t";
cout<<"\n\n";
}
}


void Flood()//Flood the grid
{
for(int i=0;i<=GridMaxX-1;i++)
for(int j=0;j<=GridMaxY-1;j++)
Grid[i][j] = (((i-r)>=0)?(i-r):(r-i))+(((j-c)>=0)?(j-c):(c-j));

//x-distance(positive) added to y-distance(positive)
DisplayGrid();
}


void main()
{
clrscr();

//Initialize Grid with junk values of 99.
for(int i=0;i<=GridMaxX-1;i++)
for(int j=0;j<=GridMaxY-1;j++)
Grid[i][j]=99;
DisplayGrid();

//Input the source of Flooding
cout<<"ENTER SOURCE COORDINATES:\nx = ";
cin>>r;
cout<<"\ny = ";
cin>>c;
Flood();
getch();
}