Posts tagged generator
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 valueVby everyP[i]we find thatP[i] > sqrt(V), stop dividing and classifyVas 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
Use Backtracking to print all Subsets
Jan 22nd
I’m “studying” this algorithmic technique: Backtracking. This is an algorithmic approach to problem solution that I trust every good Computer Scientist already uses; but taking a good theo-practical look at it is something better.
A Backtracking Tree
I believe you can find enough informations about it online (the 2 links I provided are more than enough), so I’ll go straight to the problem.
Problem definition
Given an integer n, and the set S = { 1 ... n }, calculate (print) all the possible subsets of S. For example, for n = 1, all the possible subsets are { 1 } and { } (empty set). For n = 2, all the possible subsets are: { 1 2 } { 1 } { 2 } { }. In general, for the set made of the first n Integers, the number of possible subsets is 2n.
Approaching the problem
A way to describe a possible subset is an array of n elements, one for every integers; every element in the array will have value TRUE if the correspondent integers is part of the subset, FALSE otherwise.
Why the Backtracking then? Because the backtracking technique is designed to generate every possible “candidate solution” once. If we design the algorithm smartly, we can get the backtracking logic to work for us and generate all the possible subsets.
Are you are asking yourself: “isn’t this a bit of a stretching of the backtracking approach?”. I believe it is: the code could be made way smaller, even though it would have the same complexity. We are going to execute the backtracking, designing the algorithm so it will never stop until it tried every possible solution. No “intermediate stopping condition” then.
Pascal’s Triangle generator
Jan 11th
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.
Twitter
Facebook
Google
Anobii
GitHub
LinkedIn