Posts tagged fast

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 >

, , , , , , , , ,

Swap the value of two integers without temporary storage

Jan 13th

Posted by Detro in Personal

2 comments

Someone says this is an old lame trick. I think it’s simple and clever use of XOR.

How/Why does it work?

It’s built around the properties of the XOR ^ operator, who has the following properties:

  • A ^ B = B ^ A (commutative)
  • A ^ 0 = A
  • A ^ 1 = ~A
  • A ^ A = 0

So, you can see how it get’s applied here:

#include <stdio .h>
int main(void)
{
   unsigned int a, b;
   // ... populate somehow "a" and "b"...

   printf("a = %d - b = %d\n", a, b);

   a ^= b; // store in "a" the value of "a XOR b"
   b ^= a; // store in "b" the value of "a XOR b XOR b" = "a XOR 0" = "a"
   a ^= b; // store in "a" the velue of "a XOR b XOR a" = "b XOR 0" = "b"

   printf("a = %d - b = %d\n", a, b);
}

Neat.

, , , , , , , ,

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 >

, , , , , , , , ,