Computer-Science

So prime numbers are useful. I found that I needed to generate a prime number for a hash table (details of which should be posted soon. If all goes well that is…). And I decided to come up with an algorithm to generate that prime number. Clearly stating the problem: “Find the smallest prime greater than n” The simplest way of generating primes is of course using Eurothenes' sieve1. However, this naive method runs in order of $\frac{n}{2} + \frac{n}{3} + \frac{n}{5} \ldots + \frac{n}{p}$ time, which MathWorld tells me is about $T(n) = \omega(n \ln(\ln(n)))$, and uses $\Theta(n)$ memory. This sucks for big numbers (or atleast I think I can do better). Further more, this step has to be repeated (or intelligently modified) till a prime number has been found. (I will show later that the best this can go would be $T(\lceil(\sqrt{n})+1^2\rceil)$), which is of the same order, $\omega(n \ln(\ln(n+1)))$ (mind you this is a lower bound). The algorithm I came up with, which I thought might be better is: generate all primes till $\sqrt{n}$, and check if any of them divide the number in question. If they don’t well, we have a prime, ladies and gentlemen. If they do, then we’ll just have to move along won’t we… ...

QuickSort. It’s widely accepted as the fastest generic sorting algorithm around. It’s also very simple. A comment in the last article showed me this Haskell beauty: 1 2 qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) While my C implementations aren’t any where as beautiful, I’m quite satisfied with their efficiencies. I’ll keep the code to a minimum, and the let the graphs do the talking. Quicksort is kinda like the heapsort, only not as strong (thus not as reliable). It is generally always recursive, and basically consists of 2 steps (Divide and Conquer): ...

Note: All code in this under the WTFPL1. Except possibly for Stepane Delcroix’s adapted code, which is under the MIT/X11 license Very recently, I decided to spend some time coding those standard algorithms that every programmer should know, but I am woefully ignorant of. The plan was to do an algorithm a day. Unfortunately, yesterday night, I started on the Merge sort algorithm, and I found some ancient bash script I wrote to profile and graph the running time of some other sorts (i.e. the bubble sort). Which led to me spending precious time playing around with gnuplot and various program parameters. Expect graphs. Lots of them. ...