Skip to main content

Posts

Showing posts from June, 2012

Waiting around for something to happen in Go

I was faced with what turned out to be a synchronization problem with a simple solution using Go.  How do you get multiple goroutines to wait for a single event to occur?  The answer is... close a channel.
package main import ( "fmt" ) func main() { count := make(chan int) hold := make(chan int) num := 16 for i := 0; i < num; i++ { go func(i int) { fmt.Printf("%d ", i) count <- 1 <-hold fmt.Printf("%d ", i) count <- 1 }(i) } for reported := 0; reported != num; reported += <-count { } fmt.Printf("\n") close(hold) for reported := 0; reported != num; reported += <-count { } fmt.Printf("\n") } This program outputs something like:
0 2 1 4 5 3 8 9 7 6 12 13 14 11 10 15 1 5 4 3 2 0 8 6 13 14 12 7 9 11 10 15 The exact order will depend on the order in which the goroutines are executed…

What the final Turing Machine Google Doodle does

If you solved the puzzles in the Google Doodle commemorating Alan Turing's 100th birthday and clicked on the rabbit you'd get to see the machine performing this program starting with a blank tape.


Translating that into pseudo-code you obtain the following:
one do if one blank do right while not blank one right zero while not blank left end one right else blank do right while not blank one while not blank left end zero right end end There one, zero and blank each write those symbols to the same; when used in an if or while they test for the presence of a symbol.  Right and left move the tape one square left or right.

The two branches of the main if there are doing very similar things.  They both blank out the current square, then move right until they find blank space and write 1 0 or 1 depending on whether the original square examined in the if was 1 or 0.  Then the…

Is there a 'Moore's Law' for web pages?

I came across an article I wrote in 1999 for The Guardian entitled Cut you modem's flying time which mentions that at the time the HTML of The Guardian's home page was 18kB.  Today the home page is more like 250kB.

I was curious about the growth pattern so using the Internet Archive I downloaded the home page of The Guardian for every year available from 1996 to 2011 (plus the current page) and compared the sizes of the HTML of the front page.  Here's the raw data:

Year Bytes ---- ----- 1996 5381 1997 11140 1998 10435 1999 39013 2000 97746 2001 70933 2002 92995 2003 81833 2004 92637 2005 92078 2006 108445 2007 118300 2008 186670 2009 184271 2010 181221 2011 192592 2012 253748
This excludes anything other than the raw HTML of / on The Guardian.  Clearly, it's grown a lot, but curious about the pattern I decided to see what curve would fit by using Wolfram Alpha.  Linear, quadratic and cubic fits were all about an R^2 …

New Scientist's Instant Expert on Alan Turing now free to non-subscribers

Tomorrow is the 100th anniversary of the birth of Alan Turing and earlier this year I was asked to write a special supplement for New Scientist covering his life and work.  The supplement was in the June 1 edition of the physical magazine and available on line to subscribers only.

This morning a gentle nudge of New Scientist persuaded them to make the entire thing open to anyone who registers on their site.  You don't have to pay, just register.  The complete thing is here.

The individual articles in the special are:
Code breaking and code-makingComputationIntelligence and LifeLife, Interrupted A big thank you to New Scientist for making this available to all.

Autograms

The following is a list of words that can be anagrammed into other words.  It is ordered by the number of possible words that can be made from a single word (e.g. dog and god have the same letters, trap, part and prat have the same letters).  It shows all the words that have 6 or more possible anagrams.

I particularly like that canter can turn into trance, recant, nectar, cretan, tanrec, and creant.

10 angor argon goran grano groan nagor orang organ rogan ronga
10 elaps lapse lepas pales salep saple sepal slape spale speal
9 ester estre reest reset steer stere stree terse tsere
9 caret carte cater crate creat creta react recta trace
8 asteer easter eastre reseat saeter seater staree teaser
8 laster lastre rastle relast resalt salter slater stelar
8 armet mater metra ramet tamer terma trame trema
8 leapt palet patel pelta petal plate pleat tepal
8 arist astir sitar stair stria tarsi tisar trias
7 canter creant cretan nectar recant tanrec trance
7 alem alme lame leam male meal mela
7 acinar arnica…

One way to fix your rubbish password database

Suppose for a moment that you are running a web site that has a poorly implemented password database that stores password hashes using something like SHA1(password) or MD5(password) or versions of that with some salt.  (This is what LinkedIn, last.fm and eHarmony were all doing and undoubtedly many, many other companies are in the same position).

And suppose you realize that if your password database gets disclosed your users are in danger and you'd really like to change the system used to something much more secure like bcrypt or scrypt.

Here's how you can do that in one go and secure your password database.

1. Suppose you have a database that contains password hashes for the n users of your site, and for each user you have salt si and hash hi (where hi was computed with some algorithm such as SHA1 or MD5).  (Note that the rest of these instructions work if there's no salt, just ignore it).

2. Suppose that you've chosen to use scrypt.  For each user you first create…

Animated solution to the "Never gonna give you up" program problem

I mentioned the fun "smallest program to output the lyrics of 'Never gonna give you up'" the other day.  It being a bank holiday weekend I've come up with my own solution which has 589 bytes in Perl.

It works by building a dictionary from which to compress the lyrics and then there's a simple decompressor.  Like many of the solutions this works by having the dictionary be indexed by single bytes and be built into a single string that expands to the result.

Here's the compressor.
use strict; use warnings; my $n =<<EOF; We're no strangers to love You know the rules and so do I A full commitment's what I'm thinking of You wouldn't get this from any other guy I just wanna tell you how I'm feeling Gotta make you understand Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you We've known each other for so long Y…

Compression of the lyrics of "Never gonna give you up" using the Bentley/McIlroy algorithm

There's a fun StackExchange post about the smallest program to output the lyrics to Never gonna give you up making the rounds today.  I'm not entering the competition, but I thought it would be interesting to look at from a compression perspective.  I've been working a lot with the Bentley/McIlroy algorithm for long string compression and this is a good example to illustrate its output.

Here are the original lyrics (1871 bytes):
We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand
Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you
We've known each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the…