Archive for the ‘Mathematics’ Category

Solution to the Codility Common Prime divisors Set Problem

This article discusses (a problem that I recently solved on codility ).

The core of the problem is the following:
Given two non negative integers N and M, , the task is to check whether they have the same set of prime divisors.
A prime divisor of an integer P is a prime d s.t. for some positive . You are given up to of such queries, and should return the total number of them that evaluates to true.

For instance given if and then our function should return *true* because the set of prime divisor of is equal the
the set of primal divisor of i.e. while for and the function should return *false*.

Smart (not enough) Brute Force approach

An easy approach in solving this problem could be computing by bruteforce the set of prime divisors of both numbers and compare them, and return true if they contains the same elements.
In order to achieve that we should:

  1. compute the set of primes up to . There are approximately (Read here for a more info on this topic https://primes.utm.edu/howmany.html)
  2. Using the Sieve of Έρατοσθένης approach we are able to compute it in time and space (see the following code).
  3. 
    void getPrimesSieve(vector<long long>&primes, const ll n) {
    using ll = long;
        vector<bool> nums(n + 1, true);
        primes.push_back(2);
        for (ll i = 3; i * i < n + 1; i += 2) {
            if (nums[i]) {
              for (ll j = i * i; j < n + 1; j += 2 * i) {
                 nums[j] = false;
                }
            }
        }
    
        for (ll i = 3 ; i <= n ; i += 2)
            if (nums[i])
                primes.push_back(i);
    }
    
  4. With the set of prime numbers in place then we can start finding the primal divisors. The following function computes the set of unique prime divisors of and stores them in .
  5. bool primalDivisors( long p , vector<long>& F, vector<long>& primes) {
     int i = 0;
     int c = 0;
     if (i >= primes[primes.size()-1])
                return false;
        while (p > 1) {        
            if (p % primes[i] == 0)
            {
                c++;
                p /= primes[i];
            }
            else 
            {
                if (c > 0) {
                    F.push_back(primes[i]);
                    c = 0;
                }
                i++;
            }
        }
        if (c > 0) 
            F.push_back(primes[i]);
        
        return true;
    }
    
  6. Finally we can iterate among all the queries and count the number of pairs returning *true*.
  7. int solution(vector<int>& A,vector<int>& B){
    	int LIM = -1;
    	int ans = 0;
    	LIM = max( *max_element(A.begin(), A.end()) ,*max_element(B.begin(), B.end()) ) ;
    	vector<int> primes;
    	getPrimesSieve(primes, LIM);
    
    	for (unsigned i = 0; i < A.size(); ++i)
    	{
    		vector<int> divA; 
    		vector<int> divB;
    		primalDivisors(A[i] , divA, primes);
    		primalDivisors(B[i] , divB, primes);
    		
    //same set of divisors
    		if( divA == divB)
    			ans++;
    
    	}
    	return ans;
    }
    

Altough this approach is correct, it is too slow. There are primes up to . Since the primalDivisors function gets called up to times and it has linear complexity then the overall time complexity is: which translates to !

Fast Approach using GCD

For two number to share the same set of prime divisors it must be the case that and . Checking if a number has a set of prime divisors that is subset of another is easy. In order for two number to have the same set of prime divisors the following must hold:
and i.e. their factorization only differ in the exponents.
Since clearly the we can divide by it obtaining . cannot have a larget set of factors than and hence its set of prime divisor is still contained into 's one. We can keep repeating this process until becomes one.
Dividing by the eliminates the common part of among the two number. And if eventually the dividend becomes , that means that the common part was the only part present.

As an example consider and , and . Repeting the process leads to and and and .
This shows that the set of prime divisor of M is contained in the set of prime divisor of N.
If we can show that the set of N is included in M's one, than the two sets must be equal. It is sufficient to do the same process with roles of N and M swapped.
If apply the same process to swapping the values of M and N from the previous example we obtain that and , and .

If there is a divisor that is not common to both number then the process will eventually isolate it.
Imagine that and . All common divisors will be cancelled out by repeting the division by the GCD leaving and .

Finally, the following is a possible implementation of the overall previous idea, which is also much simpler and cleaner than the one presented in the previous section.

bool containedSet(int M, int N){
	int g = __gcd(min(N,M), max(N,M));
    while(g != 1){
    	M /= g;
    	g = __gcd(min(N,M), max(N,M));
    }
    return M==1;
}


int solution(vector<int>& A,vector<int>& B){
	int ans = 0;
	for (unsigned i = 0; i < A.size(); ++i)
	{
	    //divisor A contained in divisor of B
	    //divisor A contained in divisor of A
	    //implies divisor A =  divisor of B	
           if(containedSet(A[i],B[i]) && containedSet(B[i],A[i]))
		ans++;

	}
	return ans;
}

List Cycle Detection

List Cycle Detection

Linked list cycle detection problem is a very instructive and fun problem to reason about. This article will state the problem and explains how we can solve it efficiently while giving some insight on the underlying maths.

Well, list can gets corrupted and some node can be linked by one or more nodes (as in the following figure). This could lead to never ending traversal of the list. So it make sense to solve the following problem:

List Cycle Detection - Cicrular List

Cicular List

List Cycle Detection - Problem Statement

  1. Given  a linked list detect (if any) check if the list is circular i.e. contains a cycle
  2. Find the starting node of the cycle (the node with two inward arrows in the figure)

The problem is easily solvable in time and space considering that we can visit the list from the head and store in a separate list the visited nodes. As the visit continues we check if the node we are examining was previously visited (is that node contained in the support list?). If yes the list is circular and that node is the start point of the cycle. If we reach the tail of the list then the list is not circular. We can lower the complexity of this approach down to time using a more efficient support (set) data structure (like a tree set). But we can do much better, and the rest of the article will show how to obtain time and .

List Cycle Detection - Floyd’s algorithm

We use the fact that like clock's hands things iterating on a cicle will meet at some point in the future. Consider two runner with velocities starting running from the same point in a circular stadium. They will meet again when the slower runner reach the starting point for the second time (Why? By the time the slower one has completed half circle the faster has completed a complete cycle and by the time the slower finishes his run, arriving at the starting point again, the faster has completed a second entire cycle).

Things are a bit more complicated in the List Cycle Detection problems because the iterators do not necessarily start from the same point. Consider two iterators with velocities  respectively. Suppose the cycle has length and that it starts at node number When the slower iterator reaches the faster is at location . How many iteration it will take before they meet? And at which node?

The situation is described by the following congruence

which has solution . This means that they will meet after iteration of the slower iterator and since it starts from this means that they will meet at nodes before the beginning of the cycle. We can use that fact to count nodes from the beginning of the list. Once the iterators matche in the cycle, we can move the fast iterator back to the beginning of the list and iterate forward one node per stepo with both iterators until they match again (They are far away nodes from the beginning of the cycle, so they will meet exaclty in that point.

 

Let's consider now the case when . This means that by the time the slower iterator reaches the beginning of the cycle the faster one has completed more that a cycle. What will be the starting point for the faster one? We argue that once p reaches A q is at node 2A but since A > n this means that some it will be at position A + (A mod(n)). We can now use similar argument to the previous case and write:

  • since

which has solution . This means that the meetpoint is nodes before the beginning of the cycle. If we do the sape operation as the previous case we obtain the sme result. Itrators wil meet at the beginning of the cycle. Why? Well advancing makes cycles possibly several times ( remember that  ) and it will clearly stops at .

In other words the slower pointer is at first  at node number . We can write where . After advancing steps it will be at location   Since the result follows.

As an example consider in which we have a list with a cycle of length and starts at node number . The first part of the algorithm tells us that the nodes will meet at node . Moving the fast pointer back to te head of the list and iterating one node per time both iterators will lead the slower point to node:

  • 12 again after advancing of 4 nodes
  • 12 again after advancing of 4 nodes
  • 10 advancing of the remaining 2 nodes.

CUDA - Julia Set example code - Fractals

This article present a CUDA parallel code for the generation of the famous Julia Set. Informally a point of the complex plane belongs to the set if given a function f(z) the serie does not tend to infinity. Different function and different initial condition give raise eventually to fractals. One of the most famous serie is   (the one that generated the video below).
Some nice picture may be obtained with the following initial conditions:

  1. # dentrite fractal
  2. # douady's rabbit fractal
  3. # san marco fractal
  4. # siegel disk fractal
  5. # NEAT cauliflower thingy
  6. # galaxies
  7. # groovy
  8. # frost

Here a video, showing a sequence of picture generated using different initial conditions. A nice example of how math and computer science can produce art!

CUDA Julia set code

The code is such that it is very easy to change the function and the initial condition (just edit the device function functor).

#define TYPEFLOAT

#ifdef TYPEFLOAT
#define TYPE float
#define cTYPE cuFloatComplex
#define cMakecuComplex(re,i) make_cuFloatComplex(re,i)
#endif
#ifdef TYPEDOUBLE
#define TYPE double
#define cMakecuComplex(re,i) make_cuDoubleComplex(re,i)
#endif

__global__ void computeJulia(int* data,cTYPE c,float zoom){
	int i =  blockIdx.x * blockDim.x + threadIdx.x;
	int j =  blockIdx.y * blockDim.y + threadIdx.y;

	if(i<DIMX && j<DIMY){
		cTYPE p = convertToComplex(i,j,zoom);
		data[i*DIMY+j]=evolveComplexPoint(p,c);
	}
}


cTYPE c0;
__device__ cTYPE juliaFunctor(cTYPE p,cTYPE c){
	return cuCaddf(cuCmulf(p,p),c);
}

__device__ int evolveComplexPoint(cTYPE p,cTYPE c){
	int it =1;
	while(it <= MAXITERATIONS && cuCabsf(p) <=4){
		p=juliaFunctor(p,c);
		it++;
	}
	return it;
}


__device__ cTYPE convertToComplex(int x, int y,float zoom){

	TYPE jx = 1.5 * (x - DIMX / 2) / (0.5 * zoom * DIMX) + moveX;
	TYPE jy = (y - DIMY / 2) / (0.5 * zoom * DIMY) + moveY;
	return cMakecuComplex(jx,jy);

}


The code above are the GPU instructions that are devoted to the computation of a single set. The kernel computeJulia() is executed on DIMX*DIMY (the dimension of the image) threads that indipendently compute the evolveComplexPoint() function on the converted to complex corrensponding pixel indices, the viewport (each threads compute a single pixel that has integer coordinates). The evolveComplexPoint() take care of checking how fast che point diverges.

The code is available here on github. It generates a number of png tha can be then merged in a video (as the one I present here) using a command line tool as ffmpeg.

In order to compile and run it need the CUDA SDK,a CUDA capable device and libpng installed on your system.
To compile and/or generate the video simply hit:

#compilation
nvcc -I"/usr/local/cuda-6.5/samples/common/inc"  -O3 -gencode arch=compute_35,code=sm_35  -odir "src" -M -o "src/juliaSet.d" "../src/juliaSet.cu"

nvcc  -I"/usr/local/cuda-6.5/samples/common/inc" -O3 --compile --relocatable-device-code=false -gencode arch=compute_35,code=compute_35 -gencode arch=compute_35,code=sm_35  -x cu -o  "src/juliaSet.o" "../src/juliaSet.cu"

/usr/local/cuda-6.5/bin/nvcc --cudart static --relocatable-device-code=false -gencode arch=compute_35,code=compute_35 -gencode arch=compute_35,code=sm_35 -link -o  "JuliaSetDynParallelism"  ./src/juliaSet.o ./src/main.o   -lpng

#video generation
ffmpeg -f image2 -i "julia_%05d.png" -r 40 output.mov

Here another animation

 

Fold operator - a brief detour

This article aims to be a brief practical introduction to new haskell programmer about the fold high order function (which roughly speaking is a function that takes as input and/or produces as output a function) and its usage. It will also outline a bit of the theory that lies behind this operator (the term operator comes from the field of recursion theory (Kleene, 1952), even if, striclty speaking fold is a function in haskell).

Haskell Fold - Introduction and formal definition

Many problem in function programming are solved by means of tail recursive functions (one that do not perform any other operations that need some values from the recursive call). For instance let's say we want to get the product of integers stored in a list.
What we would do is to write down a tail recursive function (more or less) like this

tailmultiply :: [Int] -> Int -> Int
tailmultiply [] acc     = acc
tailmultiply (x:xs) acc = tailmultiply xs (acc * x)

Note, to stress the tail recursion, a definition like the one that follows would not be tail recursive.

Read On…

The Grossone Numeral System

A recently developed computational methodology for executing numerical calculations with infinities and infinitesimals. The approach developed has a pronounced applied character and is based on the principle “The part is less than the whole” introduced by the ancient Greeks. This principle is applied to all numbers (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite).(Ya. D. Sergeyev)

 A brief detour in infinity

The infinity is a concept that attracts and fascinate humans from its earlist time. The earliest mathematical account of infinity comes from Zeno of Elea (490-430 BCE) who was a pre-Socratic Greek philosopher of southern Italy (named by Aristotle the "invector of dialectic"). But in order to have a systematic and mathematically rigorouse use of the concept of infinity we have to wait the 17th century, when an English mathematician, Jonh Wallis for the first time used the symbol to denote an infinite quantity in its attempt to divide a region in infinitesimal parts . Than, thanks to his concepts of infinity and infinitesimal,  Leibniz was able to develop big part of his work on calculus, but they were still abstract objects,  different from appreciable quantities as finite numbers. But they shared some interesting properties with them (law of continuity,"whatever succeeds for the finite, also succeeds for the infinite").

Cantor set, we begin with a straight line, of length 1 and remove its the middle third and repest the process with the new two pieces over and over again.

 

Read On…