Curiosity

Prime Numbers Generator

Jan 23rd

I believe I don’t have to describe what primes are, what are their properties and what not. This post is more a tribute to geek-ness of 2 friends-and-colleagues (@lucabox) that have fun thinking of algorithms to solve stupid (or less stupid), and always useless problems .

Optimus Prime – yeah yeah, a stupid joke

Briefing

This code is based on the assumption that we want to generate very very large primes, so it uses unsigned long long to store the values, instead of classical unsigned int. Live with that.

Also, give that there is nothing much better then a “try-dividing-by-every-previous-prime” out there (there are alternatives, but I’m not aware of more complex ones), I took a look to some properties of Primes, and putted into the algorithm those properties as conditions for early stop:

Say P[i] are the previously calculated Primes; If trying dividing value V by every P[i] we find that P[i] > sqrt(V), stop dividing and classify V as a newly found prime
No need to check any even number: they are divisible by 2, so no primes by definition
No need to allocate more space then an array of the size of the requested prime ordinality: everything can be done in place

More >

code, cool, fast, generator, implementation, number, optimizations, Personal, primes, tricks

The “Polite” Merge Sort

Jan 6th

Posted by Detro in Curiosity

No comments

Another old-classic problem: the Merge Sort.

Merge Sort Algorithm

The problem of the classical implementation

The whole algorithm is explained in the wikipedia link above, so I’ll focus on the problem here.

The Merge Sort is an in-place-sorting-algorithm that requires some support memory to do it’s calculations. At the “merge step”, an amount of memory as large as the current portion of array being merged is allocated to be used as priority queue (again, the why is easy to find on the web).
After this memory is used, normally get’s released.

Theoretically speaking, the amount of memory that at every recursive call get’s created is always < = size-of-input-array. So, no big deal: we knew it.

Unfortunately in practice this is not always a good idea: malloc(...) and free(...) are System Calls, and those are expensive to do. They normally require Context Switches and other system operations that I can’t advice to do without properly thinking through your code.

More >

cool, english, merge, operating system, Personal, polite, sort, system call

Fibonacci’s numbers calculator

Jan 5th

Posted by Detro in Curiosity

No comments

Another simple-but-yet-interesting problem that I found challenging solving is the to Write a Fibonacci’s numbers calculator. It’s a REALLY SIMPLE problem, but still can demonstrate how superficial thinking in programming can lead to dramatically bad solutions.

What’s a Fibonacci’s number

A Fibonacci’s number is an integer number generated using the following function:

Assumed that:
f(0) = 0
f(1) = 1

for a generic “n” Integer:
f(n) = f(n-1) + f(n-2)

For example, the first 20 Fibonacci’s number are:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

The young-and-entusiast approach

Recursion! We all love the elegance of it. When we manage to write something that uses Recursions, everything seems easier and simpler to our eyes for a while. BUT, in this particular case, using recursion for implementing such simple task is really bad.

Why? Because at every call to this function, it will generate 2ⁿ recursive function calls. A bit of a nightmare for the process call stack if the whole purpose of this thing is calculating a “stupid” integer number.

Functions call tree using a recursive algorithm

Plus, given the nature of the function itself, it will recalculate the same f(x) over and over again, because f(x) is going to be a subproblem shared between a certain y and z, where both y > x and z > x.

Result? An awful implementation. With a quick Big-Oh analysis I would say that the Time Complexity of this “monster” will be O(2ⁿ).
Don’t believe it? Check out the implementation here:

#include <stdio .h>

unsigned long fibonacci_slow(unsigned short i)
{
    if ( i == 0 )
        return (0);

    if ( i == 1 )
        return (1);

    return ( fibonacci_slow(i-1) + fibonacci_slow(i-2) );
}

int main(int argc, char** argv)
{
    unsigned short i, input;
    unsigned long curr = 0, prevprev = 0, prev = 1;

    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (1);

	printf("RESULT: fibonacci(%d) = %lu\n\n", input, fibonacci_slow(input));
	return (0);
}

Running it on my Code 2 Duo laptop with n > 40 takes around 10 seconds. For n = 50 I got bored to wait after 1 minute passed by.

If you check out this book, it is going to tell you that such solution is going to take 13 days to come out with a solution, for an average machine (i.e. a machine where O(1) = 0.001 µs).

BUT, of course, I have an alternative solution. Actually, more then one. And the best runs in O(log(n))
More >