We know that finding the minimum in a list of integers is a fairly simple task, but what about finding the i-th smallest element? Then the task isn’t that trivial and we have to think for a different approach.
First of all there are some very basic and intuitive approaches. Since finding the minimum is so easy, can we just find the minimum, than exclude it from the list and then search the minimum again until we find the i-th smallest element.
Typically multiplying two n-digit numbers require n2 multiplications. That is actually how we, humans, multiply numbers. Let’s take a look of an example in case we’ve to multiply two 2-digit numbers.
12 x 15 = ? |
OK, we know that the answer is 180 and there are lots of intuitive methods that help us get the right answer. Indeed 12 x 15 it’s just a bit more difficult to calculate than 10 x 15, because multiplying by 10 it really easy – we just add one 0 at the end of the number. Thus 15 x 10 equals 150. But now again on 12 x 15 – we know that this equals 10 x 15 (which is 150) and 2 x 15, which is also very easy to calculate and it is 30. The result of 12×15 will be 150 + 30, which fortunately isn’t difficult to get and equals to 180.
That was easy but in some cases the calculations are a bit more difficult and we need a structured algorithm to get the right answer. What about 65 x 97? That is not so easy as 12 x 15, right?
The algorithm we know from the primary school, described on the diagram below, is well structured and help us multiply two numbers.
We see that even for two-digit numbers this is quite difficult – we have 4 multiplications and some additions. Continue reading Computer Algorithms: Karatsuba Fast Multiplication
Each natural number that is divisible only by 1 and itself is prime. Prime numbers appear to be more interesting to humans than other numbers. Why is that and why prime numbers are more important than the numbers that are divisible by 2, for instance? Perhaps the answer is that prime numbers are largely used in cryptography, although they were interesting for the ancient Egyptians and Greeks (Euclid has proved that the prime numbers are infinite circa 300 BC). The problem is that there is not a formula that can tell us which is the next prime number, although there are algorithms that check whether a given natural number is prime. It’s very important these algorithms to be very effective, especially for big numbers.
As I said each natural number that is divisible only by 1 and itself is prime. That means that 2 is the first prime number and 1 is not considered prime. It’s easy to say that 2, 3, 5 and 7 are prime numbers, but what about 983? Well, yes 983 is prime, but how do we check that? If we want to know whether n is prime the very basic approach is to check every single number between 2 and n. It’s kind of a brute force.
The basic implementation in PHP for the very basic (brute force) approach is as follows.
Unfortunately this is one very ineffective algorithm. We don’t have to check every single number between 1 and n, it’s enough to check only the numbers between 1 and n/2-1. If we find such a divisor that will be enough to say that n isn’t prime.
Although that code above optimizes a lot our first prime checker, it’s clear that for large numbers it won’t be very effective. Indeed checking against the interval [2, n/2 -1] isn’t the optimal solution. A better approach is to check against [2, sqrt(n)]. This is correct, because if n isn’t prime it can be represented as p*q = n. Of course if p > sqrt(n), which we assume can’t be true, that will mean that q < sqrt(n).
Beside that these implementations shows how we can find prime number, they are a very good example of how an algorithm can be optimized a lot with some small changes.
Although the sieve of Eratosthenes isn’t the exact same approach (to check whether a number is prime) it can give us a list of prime numbers quite easily. To remove numbers that aren’t prime, we start with 2 and we remove every single item from the list that is divisible by two. Then we check for the rest items of the list, as shown on the picture below.
The PHP implementation of the Eratosthenes sieve isn’t difficult.
As I said prime numbers are widely used in cryptography, so they are always of a greater interest in computer science. In fact every number can be represented by the product of two prime numbers and that fact is used in cryptography as well. That’s because if we know that number, which is usually very very big, it is still very difficult to find out what are its prime multipliers. Unfortunately the algorithms in this article are very basic and can be handy only if we work with small numbers or if our machines are tremendously powerful. Fortunately in practice there are more complex algorithms for finding prime numbers. Such are the sieves of Euler, Atkin and Sundaram.
Run-length encoding is a data compression algorithm that helps us encode large runs of repeating items by only sending one item from the run and a counter showing how many times this item is repeated. Unfortunately this technique is useless when trying to compress natural language texts, because they don’t have long runs of repeating elements. In the other hand RLE is useful when it comes to image compression, because images happen to have long runs pixels with identical color.
As you can see on the following picture we can compress consecutive pixels by only replacing each run with one pixel from it and a counter showing how many items it contains.
In this case we can save only counters for pixels that are repeated more than once. Such the input stream “aaaabbaba” will be compressed as “[4]a[2]baba”.
Actually there are several ways run-length encoding can be used for image compression. A possible way of compressing a picture can be either row by row or column by column, as it is shown on the picture below.
I bet you didn’t know that PHP strings don’t need quotes! Indeed PHP developers work with strings with either single or double quotes, but actually in some cases you don’t need them.
Here’s how PHP developer declare a string, which is something very common in any programming language.
$my_var = 'hello world'; // or $my_var = "hello world"; |
What if you do the following:
echo hello; |
That appears to be correct … Well, it’s not absolutely correct. You’ll be “noticed”.
// Notice: Use of undefined constant hello echo hello; |
However if you disable error reporting, the code will be completely fine.
error_reporting(0); // no problem now echo hello; |
What follows from the thing above is that you can use strings without quotes:
// hello echo hello; // hello world (concatenated) echo hello . ' world'; // helloworld echo hello . world; |
However you can’t have spaces and most of the “special” symbols.
// syntax error echo hello world; // syntax error echo hello!; |
Although you can do this in PHP, that is completely wrong. The code becomes more difficult to read and understand. In the second place you can miss a $ sign in front of a variable declaration and thus the PHP interpreter will assume this is a string. So disable error reporting isn’t so great sometimes.
