Posts tagged cool

Prime Numbers Generator

Jan 23rd

Posted by Detro in Curiosity

3 comments

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
Optimus Prime :-P – 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:

  1. 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
  2. No need to check any even number: they are divisible by 2, so no primes by definition
  3. No need to allocate more space then an array of the size of the requested prime ordinality: everything can be done in place

More >

, , , , , , , , ,

Money change problem: Greedy vs. Dyn.Pro.

Jan 17th

Posted by Detro in IT / Comp-Sci / Code

7 comments

This is a classical problem of Computer Science: it’s used to study both Greedy and Dynamic Programming algorithmic techniques.

Coins
I hate having my pocket full of copper!!! -_-

Definition

Given:

  • A set of n Denominations D[0...n-1] in ascending order, representing a Monetary Coin System
  • An money amount A, as input

calculate a solution:

  • S[0...n-1], with 0 <= S[i] <= (A/S[i]) and 0 < i < n-1

where:

  • A = Sum[i=0 -> n-1] { D[i] * S[i] }
  • Min{ Sum[i=0 -> n-1] { S[i] } }

In other words

Find the smallest amount of coins to make the given amount. More >

, , , , , , , , , ,

Calculate abs(int) without branching

Jan 13th

Posted by Detro in IT / Comp-Sci / Code

4 comments

For this you need someone to teach it to you: if you made it yourself, then you are a very good Comp-Sci, and you should send your CV to Google ASAP. ;)

Without branching O_o?

Yes, without using any “if ( a < 0 )...". To do that, you need to refresh how Two's Complement works, then come back.

What we really need to focus on is that, given a signed int A, the negative of that number is: B = ~A + 1. BUT, we are trying to calculate the Absolute Value, not the negative. So, something like:

RESULT =
    (INPUT, if positive, or NEGATE_INPUT, if negative)
    +
    (0, if positive, or 1, if negative)

Does it makes sense to you? To me it didn’t for the first 10 minutes. More >

, , , , , , , , , , ,

Pascal’s Triangle generator

Jan 11th

Posted by Detro in IT / Comp-Sci / Code

No comments

What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need).

Pascal's Triangle first 6 rows
Pascal’s Triangle first 6 rows

The thing I wrote here is a generator of the n-th row of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a Triangular Matrix, and building every row based on the one above, solution is built in place.

More >

, , , , , , ,

String search in O(n + m)

Jan 8th

Posted by Detro in IT / Comp-Sci / Code

2 comments

Searching a string inside another string is a very easy task. Given a string A and a string B, start a loop over A from left to right and, for every letter, start an internal loop to see if there is a match with the letters of B.

String
A ball of string

Pseudo code would look something like this:

function NaiveSearch(string s[1..n], string sub[1..m])
   for i from 1 to n-m+1
      for j from 1 to m
         if s[i+j-1] ≠ sub[j]
            jump to next iteration of outer loop
      return i
   return not found

Time Complexity? O(n * m), where n is the size of A and m is the size of B.

Wonna do better? Follow me. More >

, , , , , , , , ,

Count bits set in parallel

Jan 7th

Posted by Detro in IT / Comp-Sci / Code

2 comments

This time it’s not something I make myself. Indeed, I still can’t “see” it 100%: I got it, but it’s a bit complex.

Counting kid
A cute little lady counting (bits? ;-) )

It’s a method to count the number of bits in a number in O(1), in just 5 lines of code. INHUMAN.

The “human” solutions

Of course, there are methods that look way more easy and, given that the size of a number in memory is “fixed”, the O(1) still stands. For example:
0. Based on the “evenness/oddness” of the number

unsigned int bits_counter_v0(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If odd, add 1
        count += (x % 2 == 0) ? 0 : 1;
        x >>= 1;
    }

    return count;
}

1. Counting one bit at a time (always the least significant one)

unsigned int bits_counter_v1(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If least-significant bit is 1, add 1
        count += (x & 1) ? 1 : 0;
        x >>= 1;
    }

    return count;
}

2. Counting 4 bit at a time with max 8 shifts, using an “hashmap” with precalculated results
The fact that it can count the bits in “max 8 shifts” has the trade off of the memory used by the hashmap.

unsigned int bits_counter_v2(unsigned int x) {
    unsigned int count = 0;
    // "Hashmap" of the values for the least significant 4 bits
    unsigned int int_to_bits_count[16] = {
        0, // 0  00
        1, // 1  01
        1, // 2  10
        2, // 3  11
        1, // 4  100
        2, // 5  101
        2, // 6  110
        3, // 7  111
        1, // 8  1000
        2, // 9  1001
        2, // 10 1010
        3, // 11 1011
        2, // 12 1100
        3, // 13 1101
        3, // 14 1110
        4  // 15 1111
    };

    while ( x != 0 ) {
        // Add the bits count of the least significant 4 bits
        count += int_to_bits_count[ x & 15 ];
        x >>= 4;
    }

    return count;
}

Let’s see what some insane people made. More >

, , , , , , ,
« Older Entries