cool

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 >

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.

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

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 >