Computer Algorithms: Karatsuba Fast Multiplication

Posted on May 15, 2012 by Stoimen

Introduction

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.

Typical Multiplication

We see that even for two-digit numbers this is quite difficult – we have 4 multiplications and some additions. Continue reading →

Posted in algorithms | Tagged , , , , , , , , , | Leave a comment

You think you know algorithms. Quiz results!

Posted on May 9, 2012 by Stoimen

Finally the results from “You think you know algorithms” are out. This time only 3 of you have answered correctly to all the questions.

1. Which string searching algorithm is faster?

  • Morris-Pratt correct answer (ref)
  • Brute force
  • Rabin-Karp

Quiz results for "Which string searching algorithm is faster?"


Continue reading →

Posted in quiz | Tagged , , , , , , , | Leave a comment

Computer Algorithms: Determine if a Number is Prime

Posted on May 8, 2012 by Stoimen

Introduction

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.

Overview

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.
Continue reading →

Posted in algorithms | Tagged , , , , , , , , , , , | 2 Comments

Computer Algorithms: Lossy Image Compression with Run-Length Encoding

Posted on May 3, 2012 by Stoimen

Introduction

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.

Lossless RLE for Images

Although lossless RLE can be quite effective for image compression, it is still not the best approach!

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.

Row by row or column by column compression

Row by row or column by column compression.

Continue reading →

Posted in algorithms | Tagged , , , , , , , , , , , , , , , , | 2 Comments

PHP Strings Don’t Need Quotes

Posted on April 26, 2012 by Stoimen

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.

PHP by Book

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";

PHP Tricks

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;

Variations

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!;

Final Words

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.

Posted in PHP | Tagged , , , , , , , , , , , , , | 11 Comments