Mathematics and computer science

In this post we're going to implement a simple algorithm which finds images that look similar to each other. # Overview In order to find images that look similar, we first need to normalize them to a simpler form and compute a fingerprint for each image. The fingerprint is a binary sequence of ones and zeros and it's created from the average color of the image and the average color of each pixel. In order to make the process faster and more flexible (and also to have fingerprints of the same length) the image is first resized to a fixed resolution, which defaults to 64x64. # Algorithm This is the algorithm which creates the fingerprint of an image: averages = [ ] for y in range ( height ) { for x in range ( width ) { rgb = img . get_pixel ( x , y ) averages . append ( sum ( rgb ) / len ( rgb ) ) } } avg = sum ( averages ) / len ( averages ) fingerprint = averages . map { | v | v < avg ? 1 : 0 } It ...

In this post we're going to look over the main things required in designing and implementing a programming language. # Overview Before writing any code and before designing any language construct, we need to think about the core of the language that we want to create. The core of the language is the most important part which defines the language itself. We also have to choose a  programming paradigm  for our language from the following list: imperative declarative functional object-oriented procedural logic symbolic A language can have more than one paradigm. For example, it can be imperative and object-oriented at the same time. These are called multi-paradigm languages. After these two criteria are met, we can start thinking about a syntax for our language and begin carefully to design language constructs and implement them. In order to implement our programming language, we need to write a parser which creates an abstract syntax tree (AST) from ...

Prime numbers play an important role in cryptography due to the fact that it's hard to factorize a semiprime into its original two factors. A while ago, RSA put prizes on large semiprimes and challenged the public to crack them. Not surprisingly, most of the numbers remained unfactored until this day. The entire security system is based on the fact that we don't have a truly efficient factorization algorithm. To give you an example, using the most efficient known algorithm ( GNFS ), it took 5 months to factorize the RSA-640 number using 80 AMD Opteron CPUs, clocked at 2.2 GHz. But there is something special about the RSA semiprimes; all of them are the product of two prime numbers which have about the same length, with a deviation of ± 1 in some cases. This is a very valuable piece of information, because we can test only a restricted amount of prime numbers that are in the range we are interested in. For example, RSA-100  is a 100-digit number and is the product ...

This time we're going to look at the elegant algorithm behind the classic Snake game. # Definition First, we need a 2D grid and some constants to label the blocks, which are described bellow: HEAD follows input or block directions creates BODY blocks BODY represents the body of the snake TAIL follows block directions changes  TAIL  to  VOID changes BODY to TAIL FOOD suspends  TAIL  actions VOID represents an empty block Initially, the grid is created with all the blocks labeled as   VOID . # Illustration After we have the 2D grid, we need to create the snake itself and the food source. Currently, the snake has no BODY , only the HEAD and the TAIL , both with a left (⬅) direction specified: FOOD HEAD ⬅ TAIL ⬅ ...

Back to image territory, to prove again that the 2D land is awesome. :-) In this post we're going to talk about image cropping and how to do this generically for any background color, even for backgrounds that have variations of the same color. # Finding the background color First, we need an algorithm to detect the background color, then we need to find where the background ends in all four parts of the image. The background color detection is the simplest part. We can take a pixel from one corner of the image and assume that this is the background color. To validate or invalidate this assumption, we have to test each edge of the image, pixel by pixel, to see if all pixels are about the same color. A clever way is by sampling pixels in larger steps and spiraling-in slowly until we checked all the pixels from a given row or column. For example, if we have a row of 100 pixels wide, the steps that we'll take in order to check all the edge pixels, are ...