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.

Advertisements
Posted in c++ | Leave a comment

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.

Source: http://projecteuler.net/problem=1

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 )
   {
      cout<<“Bad idea!”;
   }
   else
   {
      cout<<“Excellent!”;
   }
}
Posted in Algorithms, Math | Leave a comment

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:

<A^TAv_i, v_i>=<Av_i, Av_i>= \lambda _i<v_i, v_i>

Because <x, x> 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} , <Av, w> = <v, Aw> because A is real and symmetric. But <Av, w>=0 because Av \in V. Thus <v, Aw>=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: <X_i, X_j>=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,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 <AX,Y>=<X,{A^t}Y>, for any matrix A

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

<AX,Y>=(AX)^t\overline{Y}=X^tA^t\overline{Y}=X^t\overline{A^tY}=<X,{A^t}Y>

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

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

From \lambda<X,X>=\overline{\lambda}<X,X> 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

Google interview question

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;    
   }
  }  
 }
 printf("Not found\n");
}

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);
  }
 }
 printf("Not found\n");
}

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;  
  }
 }
 printf("Not found\n");

}

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