Wednesday, September 30, 2009

Fast average calculation for website

In this article, I will explain how to efficiently calculate the average user rating of a zillion post or more generally how to calculate an average value when data comes at interval and the average need to be recalculated every time.

The arithmetic mean is calculated using the following formula :
A=\frac{x_1+...+x_n}n

If we add another value the formula becomes :
B=\frac{x_1+...+x_n+x_{n+1}}{n+1}

The interesting part is how we can calculate the new value B from the last average value A :
B=\frac{\frac{x_1+...+x_n}n*n+x_{n+1}}{n+1}=\frac{A*n+x_{n+1}}{n+1}

We need 3 values to calculate the new average : the last average, the last count of values contained in the last average and a new value to be considered. Put simply, we need to multiply the last average by the number of value in it and add the new value to be counted in the average. Then we divide the result by the new number of value in the average.

This is good enough method to calculate an average. It's a bit less precise than the usual method because of rounding error, but it's still much more precise than needed for any website use. Off course, you would need to store the average and the value count in a DB.

Monday, September 07, 2009

Pyrit - WPA PSK security and FPGA

Pyrit is an open-source tool allows to dictionary attack a WPA PSK handshake. I'm fairly impressed. It is written in Python and uses C bindings to do the crunching work. It's also able to use OpenCL, NVIDIA CUDA and ATI Stream to speed up 10x the calculation.

I believe a FPGA could be used to speed up even more the calculations. In any case, that is left to see. I'll be working on a VHDL prototype during the next few weeks.

Monday, June 15, 2009

Evolving Building

I saw a documentary about the conception of the Burj Dubai Tower. It was pretty impressive. They showed how they tested the structure using test model and computer simulation. They iterated through many variations of the structure during many years.

I recognize a pattern in this. This methodology is similar to Genetic Algorithm. A genetic algorithm uses a simple natural process.

  1. Generate new solutions to the problem

  2. Test the solutions

  3. Eliminate unworthy one

  4. Repeat until the best individual is good enough



Like in any other industry, I believe it would be beneficial for architect to use tools that would accelerate their works. This is not a totally new idea as it have already been applied to city planning. The architect would input in the software the constraint imposed by the location of the building. Then the software would generate new solutions from the nearly infinite pool of possibility. The tough part is to design a fitness function (a mathematical function that define how good a building design is) that would contain the intricate knowledge from the master architect. I strongly believe that computer simulation would accelerate tall building design. I'm adding this to the list of my research interest!

Tuesday, June 02, 2009

Windows 7 first impression

For now, I had no major problem. The install went smoothly. It took 2 reboots and about 20 minutes for Windows 7 RC1 to install. The first thing I have noticed is that the driver for my video card is integrated (NVIDIA) so I don't have to suffer from a low resolution during the install of the various device drivers.

Here a list of new functionalities or changes I've noticed:

  • Better organized control panel

  • The ability to burn .iso CD image directly from Windows

  • New task bar. The windows group by task (application) and are merged with the quick launch bar

  • Microsoft Paint have been updated (Nice!) ☺

  • I find the overall GUI to be smoother

  • I can't find how to deactivate windows 3D effects which I find annoying



more later

Wednesday, May 20, 2009

A web site launch




Today, I'm launching a new web site : www.votator.com. It's not quite like other poll web site you can find on the Internet. Most of them use simple majority to find the winner to a poll or rank the poll's choice according to the % of vote they get. Instead, www.votator.com uses a new method (1997, relatively new for the voting theory community), the Schulze method. It allows the poller to gather and consider the whole range of voters preference.

Let me explain a bit. Usually when you take a poll, you only give your favorite choices out of a list of a few choices, but Votator asks the user to rank the choices from first to the last using an intuitive GUI. Then, Votator uses this information to rank the choices from first to last. It ranks the candidates by comparing every candidates with every other candidates, so it counts how often a candidate is ranked better than another candidate in every ballot. When a candidate wins in this fashion against every other candidate he is considered the winner.

I hope you enjoy using this tool.

Friday, February 27, 2009