## Little endian vs. big endian

This is about how the bytes of a data type are arranged in memory. An int variable for example occupies 4 bytes in memory. In case of little endian, the least significant byte of the integer value will be first in memory (at a smaller address). In case of big endian, the most significant byte if the integer value will be the first byte in memory.

Consider the following code that prints the digits of a number by remembering the last digit and by shifting to the left. ‘size’ is the number of bits to print, ‘val’ is the number to print:

void PrintBinary(int val, int size)
{
unsigned char* b  = new unsigned char[size];
memset(b, 0, size);
int pos = size – 1;
while ( val != 0 )
{
b[pos] = val % 2;
val = val >> 1;
pos–;
if (pos < 0) break;
}
for (pos = 0; pos< size; ++pos)
{
printf(“%d”, b[pos]);
if (pos%8 == 7) printf(” “);
}
delete[] b;
}

int x = 8;
PrintBinary(x, 32);

Then the above code will print:  00000000 00000000 00000000 00001000

The code below will print ‘00001000 00000000 00000000 00000000’ which  shows that it was run on a little endian machine because the least significant byte is first.

unsigned char* b = (unsigned char*) &x;
for (int i = 0; i
{
PrintBinary(b[i], 8);
}

Here is a method to determine the endianess of a machine:

bool IsLittleEndian()
{
int b = 1;
return ((unsigned char*)(&b))[0];
}

A more interesting approach is to use a union (a C++ facility to agregate mode data types over the same memory space):

bool IsLittleEndian()
{
union local_t
{
int i;
unsigned char b;
};
local_t u;
u.i = 1;
return u.b;
}

That was the C++ approach. Java offers an API for it:

import java.nio.ByteOrder;

if (ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)) {
System.out.println(“Big-endian”);
} else {
System.out.println(“Little-endian”);
}

In C# the BitConverter class has the IsLittleEndian static method.

## Just another counting problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

There are $n_3 = 1000/3 = 333$ multiples of $3$ and $n_5 = 1000/5 - 1 = 199$ multiples of $5$. Some of those numbers are multiple of both $3$ and $5$ (i.e. they are multiples of $15$). When summing, we need to avoid summing twice we need to subtract those numbers.

There are $n_{15} = 1000/15 = 66$ multiples of $5$. The result is:

$3 \cdot \frac{n_3(n_3+1)}{2}+5 \cdot \frac{n_5(n_5+1)}{2}-15 \cdot \frac{n_{15}(n_{15}+1)}{2}=233168$

This is a simple C++ program that verifies the math:

int main()
{
int n = 1000;
int sum = 0;
for ( int i = 1; i < n; i++ )
{
if ( ( i % 3 == 0 ) || (i % 5 == 0 ) )
{
sum += i;
}
}
int div3 = ( n – 1 ) / 3;
int div5  = ( n – 1 ) / 5;
int div15 =  ( n – 1 ) / 15;
int sumDirect =  3 * div3 * ( div3 + 1 ) / 2 +
5 * div5 * ( div5 + 1 ) / 2  – 15 * div15 * ( div15 + 1 ) / 2;
if ( sum != sumDirect )
{
}
else
{
cout<<“Excellent!”;
}
}

## SVD – a simple proof

Every $m \times n$ real matrix $A$ can be decomposed as: $A=U \Sigma V^T$ where $U$ is a $m \times m$ orthogonal matrix, $\Sigma$ is a $m \times n$ matrix, having non-zero elements only on the diagonal, and  $V$ is a $n \times n$ orthogonal matrix.

We know from the previous post that a symmetric matrix is digonalisable, and can be diagonalised by a orthogonal matrix. In our case $A^{T}A$ happens to be a $n \times n$ symmetric matrix.

Therefore, $\exists v_i, \lambda _i, i=1..n$, and $A^TAv_i=\lambda _iv_i$. Real symmetric matrices have real eigenvalues and additionally $\lambda _i \geq 0$ because:

$== \lambda _i$

Because $$ is grater or equal to $0$ for some vector $x$, it follows that $\lambda _i=0$ when $Av_i=0$ (i.e. $v_i$ is in the null space of $A$) and $\lambda _i>0$ otherwise.

For $\lambda _i > 0$, multiplying $A^TAv_i=\lambda _iv_i$ by ${v_j}^T$ and considering that $v_i$ and $v_j$ are orthogonal unit vectors, we get:

${v_j}^TA^TAv_i=\lambda _i \delta _{i,j}$  =>

${(Av_j)}^TAv_i=\lambda _i \delta _{i,j}$ =>

${(\frac {Av_j} {\sqrt {\lambda _j}})}^T{(\frac {Av_i} {\sqrt {\lambda _i}})}=\delta _{i,j}$

Denoting $u_i=\frac {Av_i} {\sqrt {\lambda _i}}$ we get: $Av_i=\sqrt {\lambda _i}u_i$ =>

$A[v_1 ... v_r v'_{r+1} ... v'_{n}]=[u_1 ... u_r u'_{r+1} ... u'_{m}]\begin{bmatrix} {\sqrt \lambda_1} & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & {\sqrt \lambda_r} & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \\ 0 & \cdots & 0 & \cdots & 0 \end{bmatrix}$

$r$ is the rank of the matrix.

The set of vectors $v_i$ is extended by the set of orthogonal vectors $v'_j$ to form a basis in $R^n$.

The set of vectors $u_i$ is extended by the set of orthogonal vectors $u'_j$ to form a basis in $R^m$.

Posted in Math | 1 Comment

## Real symmetric matrices are diagonalizable

This article involves advanced linear algebra knowledge but it definitely worth understanding it. The previous post contains a proof that a real symmetric matrix has real eigenvalues. Additionally the real symmetric matrices are diagonalizable by an orthogonal matrix. This means: $\forall A$ symmetric,  $\exists P$ orthogonal ($P^tP=I$) and $D$ diagonal, such that $A=P^{t}DP$

To continue the proof I will use the following result:

Let let $A$ be a real symmetric matrix and let $V$ be a subspace of $R^n$ and $V^{\bot}$ its complement ($R^n=V \oplus V^{\bot}$). If $\forall v \in V$, $Av \in V$ then: for $w \in V^{\bot}$ $\Rightarrow$ $Aw \in V^{\bot}$.

Proof: I will use the dot product defined in the previous post. Given $v \in V$ and $w \in V^{\bot}$ , $ = $ because $A$ is real and symmetric. But $=0$ because $Av \in V$. Thus $=0$, $\forall v \in V$. This means that $Aw \in V^{\bot}$.

Getting back to the problem, $A$ has at least one eigenvalue. It results that exists $X_1$ and $\lambda _1$, such that $AX_1=\lambda _1X_1$.

If $V_1$ is the vector space generated by $X_1$, then the operator $A$ is also symmetric when applied to the subspace $V_1^{\bot}$ (this can be proven by changing the basis). This means that exists $X_2 \in V_1^{\bot}$ such that $AX_2 = \lambda_2X_2$. Considering the vector space generated by $X_1$ and $X_2$, and by applying the operator $A$ to its orthogonal we will get $AX_3 = \lambda_3X_3$. By induction we get: $AX_i = \lambda_iX_i, i=1..n$, where the vectors $X_i$ are pair wise perpendicular: $=0, \forall i,j \in {1..n}$.

Additionally the vectors can be divided by their norm to make them unit vectors. In a matrix form the relations above can be written as:

$A[X_1 X_2 ... X_n]=[X_1 X_2 ... X_n]diag(\lambda_1, \lambda_2, ... ,\lambda_n)$

Or $A=P diag(\lambda_1, \lambda_2, ... ,\lambda_n) P^{-1}$, where the columns of $P$ are the vectors $X_1, X_2, ...X_n$. P is orthogonal because vectors $X_i$ are pair wise perpendicular and unit vectors. This also means that $P^{-1}=P^t$.

Posted in Linear Algebra, Math | 3 Comments

## Real symmetric matrices have real eigenvalues

A real matrix is symmetric if $A^t=A$. I will show in this post that a real symmetric matrix have real eigenvalues.

I will need a dot product for the prof and I’ll use the basic dot product for two vectors $X$ and $Y$: $=X^t\overline{Y}$, where $\overline{Y}$ is the complex conjugate of the vector $Y$.

The useful property of this dot product is that $=$, for any matrix $A$

And considering that $A$ is real, a simple proof is:

$=(AX)^t\overline{Y}=X^tA^t\overline{Y}=X^t\overline{A^tY}=$

An eigenvalue have a correspondent eigenvector: $AX=\lambda X$.

We have $=<\lambda X, X>=\lambda $ and considering that A is symmetric $====\overline{\lambda}$.

From $\lambda=\overline{\lambda}$ and because $X$ is not a zero vector it results that the imaginary part of $\lambda$ is zero, so the eigenvalue is a real number.

Posted in Linear Algebra, Math | 3 Comments

Given an array of integers and an integer S, find if there are two numbers X and Y in the array such that X + Y = S. The problem was received by a friend during a phone interview with Google. A naive solution is:

void solutionNaive(vector& inVals, int sum) //O(n^2)
{
size_t size = inVals.size();
//naive
for (int i = 0; i < size-1; i++)
{
for (int j = i+1; j < size; j++ )
{
if (inVals[i] + inVals[j] == sum)
{
printf("Values: %d and %d\n", inVals[i], inVals[j]);
return;
}
}
}
}

This is $O(n^2)$ and its performance definitely not acceptable for large arrays. A faster solution is to use a hash set for storing the elements tested so far, and to test if S minus the current element was already stored in the hash set. More memory is used in this approach, but the complexity in this case is $O(n)$ because searching in a hash set or hash map is $O(1)$:

void solutionOk(vector& inVals, int sum) //O(n)
{
hash_set checkedVals;
for (vector::iterator it = inVals.begin(); it!= inVals.end(); ++it)
{
if (checkedVals.find(sum - (*it)) != checkedVals.end())
{
printf("Values: %d and %d\n", sum - (*it), *it);
return;
}
else
{
checkedVals.insert(*it);
}
}
}

An other possible solution, not so efficient but interesting, is to sort te numbers and then for each X in the array to use binary search for searching if S-X is there. The complexity is $O(nlog(n))$, and no additional memory is used. An important aspect of this method is the way it handles the case when S-X = X:

void solutionNotSoBad(vector& inVals, int sum) ////O(n log(n))
{
size_t size = inVals.size();
//sorting is O(n log(n))
sort(inVals.begin(), inVals.end());
bool found = false;
for (vector::iterator it = inVals.begin(); it != inVals.end(); ++it)
{
vector::iterator current = it;
int toFind = sum - (*it);
if ((toFind <= *it) && (it!= inVals.begin()))
{
found = binary_search(inVals.begin(), --current, toFind);
current = it;
}
if ((toFind >= *it) && (it != inVals.end()))
{
found = binary_search(++current, inVals.end(), toFind);
current = it;
}
if (found)
{
printf("Values: %d and %d\n", (*it), toFind);
return;
}
}

}

As a conclusion, keep in mind that hash based data structures are generally the most appropriate to use when fast search operations are needed.

Posted in Algorithms | 1 Comment

## Celular automata – generating chaos with simple rules

Consider a matrix having $n$ lines and $2n+1$ columns. The contents of the matrix is filled with 0 or 1 based on the following rules:
1. First line is full of zeros except the central element (position $n$ for 0 based index as in C++, C#, Java etc, and position $n+1$ for Matlab, Pascal etc) wich is 1. For $n = 3$ the first line will be: 0 0 0 1 0 0 0
2. The line $k+1$ is computed based on line $k$. Each element is computed based on the three upper neighbours. Thus for each combination of the possible values for upper neighbours we need to specify a value: 0 or 1
000 -> $a_1$
001 -> $a_2$
010 -> $a_3$
011 -> $a_4$
100 -> $a_5$
101 -> $a_6$
110 -> $a_7$
111 -> $a_8$
where $a_1, a_2,...,a_8$ can be 0 or 1.The array $\overline{a_8...a_1}$ is the base 2 representation of a number between 0 and 255.
For simplicity the first elements of each row are always set to 0 because for those elements only two out of three upper neighbours are known.

Based on this rule different patterns can be generated. For example if $\overline{a_8...a_1}=90$ and $n = 261$ the following pattern is generated:

Here is the Matlab code for generating patterns:

function [] = automata()
n = 261;
m_in = zeros(n, 2*n+1);
rule = [0, 0, 0, 1, 1, 1, 1, 0]; %rule 30
%rule = [0, 1, 0, 1, 1, 0, 1, 0]; %rule 90
m_out = generate(m_in, rule);
imshow(1 - m_out);
%---------------------------------------------------------------------
function [o] = generate(m, rule)
problemSize = size(m, 1);
%starting alue
m(1, problemSize+1) = 1;
mid = problemSize+1;
%for each row
for row = 2:problemSize-1
%for each column
for col = mid -(row-1) : mid +(row-1)
i1 = m(row-1, col-1);
i2 = m(row-1, col);
i3 = m(row-1, col+1);
%based on te values from the previous row
%and based in the rule generate the values in
%current row
n = i1*4+i2*2+i3;
m(row, col) = rule(8-n);
end
end
o=m;

A particular interesting pattern is generated by rule 30. This is how it looks for $n = 261$:

Compared to other rules, a chaotic pattern is generated (see the right side of the result). Rule 30 shows that using simple evolution rules, and starting from something basic (a single value of 1 in this case) something complex can be generated.
This lead to the following idea: what if the universe was generated in a similar way; A simple initial state and a simple rule that evoluates  in time and lead to the complexity that we see around?

Source:  Stephen Wolfram, “A New Kind of Science”, http://www.youtube.com/watch?v=_eC14GonZnU

Posted in Math | 1 Comment