:: cortesi

linklog

30 January 2010

Pants-a-Pundit

Two pundit pantsings for you today.

  • Ray Kurzweil Response to "Ray Kurzweil's Failed 2009 Predictions"

    First, an amusing stoush between Ray Kurzweil and one Michael Anissimov. Quibbling with Kurzweil might be dangerous - after all, one wouldn't want to be left behind when the nerd rapture arrives - but by my reading he had the easy predictions right, and the difficult predictions wrong enough to have to rationalise and re-interpret his way around things. My advice to tech pundits is to avoid prose at all costs - stick to heavily allegorical verse, preferably in 16th century French. It makes these things so much easier.

  • Participatory media and why I love it (and must defend it)

    Caterina Fake's response to the ridiculous piece Jaron Lanier somehow managed to get into the Wall Street Journal recently. I guess it's not terribly surprising that the mainstream media finds it difficult to figure out who's worth listening to in the technical community, but I'm still occasionally surprised just how far chutzpah and self-promotion can get you.

Tech talks

Visualisation

Security

Comments

Timsort - a study in grayscale

28 January 2010

Timsort
Click to embiggen.

A couple of days ago I published a set of explosion-in-a-crayola-factory colourful sorting algorithm visualisations, using a colour sequence generated with the Hilbert curve. The idea was that using a space-filling curve to traverse the RGB colour cube we could get a large number of distinct but visually ordered colours. I contrasted this with a more common method, which is to vary the intensity of a monotone to generate a gradient of colours. A couple of people suggested that I provide a set of grayscale images for comparison. I was curious about this too, so I hacked a grayscale generator into sortvis. The results were striking, but not interesting enough to reproduce here in full. Subjectively, I think the coloured images do allow you to follow more of the detail in these dense visualisations, but I'm not wedded to the idea. Being able to visually judge the order of elements in a sorting algorithm visualisation is important, and that is something we sacrifice in the Hilbert RGB traversal. I still like my earlier sparse grayscale visualisations best.

If you're curious, you can check out sortvis and generate the full set of grayscale graphs with the following command:

./dense -g -n 512

I did think the grayscale version of Python's Timsort was worth sharing. It's pretty spectacular due to a purely coincidental 3d effect - not much good for explaining Timsort, but I'd hang it on my wall, for sure.

Comments

Hilbert Curve + Sorting Algorithms + Procrastination = ?

26 January 2010

I like the Hilbert curve. I like sorting algorithm visualisations. I occasionally procrastinate when I should be doing more important things. When all these factors converge, the result is a post like this.

In a previous post, I drew a picture of a Hilbert curve by projecting a Hilbert curve traversal of the RGB colour cube onto a Hilbert curve traversal of the plane (yes, it's a mouthful, but it's a mouthful of awesome). Since then, I've been pondering the general utility of Hilbert curve traversals of the colour cube. In large-scale visualisation, we often want to choose an ordered sequence of colours that have the property that colours close to each other on the sequence are also close to each other visually. The easy way to do this is to restrict yourself to a specific hue, and to vary the intensity. I used this idea in grayscale to generate some previous sorting algorithm visualisations:

Insertion sort

The problem with this approach is that it hugely restricts the number of distinct colours we can use. There are only so many distinct shades of gray the human eye can perceive - I'm already pushing it with 20 distinct colours in the image above. We can do much, much better using the Hilbert curve. Lets assume that human perception of RGB colours is uniform and consistent - that is, that any change along the RGB axes will result in uniformly proportional difference in perceived colour. This assumption is incorrect, but it's good enough as a first approximation. By traversing the RGB colour cube in Hilbert order, we can get a set of colours that are maximally distinct from each other, with near-optimal colour locality preservation (keeping in mind that perfect locality preservation is impossible). In other words, an equidistant sequence of colours that are simultaneously as different from each other as possible, and where colours 'close' to each other on the sequence are as similar as possible. The result is a colour sequence that looks like this:

Colour swatch
512-colour Hilbert-order swatch

We do, of course, pay a price for this mathematical marvel: we can't visually compare colours and see their order in the spectrum. When we really want a large ordered sequence of colours, this can be an acceptable tradeoff.

Below is a re-imagining of my previous sorting algorithm visualisations, at a much larger scale than I could achieve using shades of gray. Each image shows a random list of 512 elements being sorted. The images are at a 1-pixel per element resolution, and each element has a distinct colour along the Hilbert RGB cube traversal. The aspect ratios differ, because the width of the images are equal to the number of element swaps that occur during the sorting process. I've left out a number of algorithms that end up being too "wide" to be enjoyable - shellsort and bubblesort, I'm looking at you. Oh, and I make absolutely no claims that these particular visualisations are useful or informative. I made them for the same reason Mallory climbed Everest and the chicken crossed the road: because it's there, and to see what's on the other side. Come to think of it, the Mallory-Chicken Impetus explains rather a lot of what I do.

Selection sort

Selection sort

Insertion sort

Insertion sort

Python's Timsort

I explained the pattern you see below in a previous post visualising Timsort.

Timsort
Click to embiggen.

Quicksort

Quicksort
Click to embiggen.

The code

As usual, I've published the code used to draw the images in this post. I extended scurve, where I'm collecting algorithms and visualisation techniques related to space-filling curves, to draw colour swatches. Then I added added a "fruitsalad" visualisation technique to sortvis, which houses my sorting algorithm visualisation code.

Comments

linklog

20 January 2010

Intertubes

Code

Toys

UX

Two long UX reads in this edition of the linklog - make a cup of coffee, sit somewhere comfortable, and enjoy:

Visualisation

Comments

An email to the authors of JSCrypto

14 January 2010

[Update: A fix for these problems and one noted by Peter Burns in the comments to this post has been posted. Get it while it's hot, folks.]

Hi folks,

Thanks for a blazingly fast little crypto library. Please find below a few comments on the code.

There's an error in the is_ready function of the random number generator. On line 1386 of the jscrypto.js file, you have:

    return (this._pool_entropy[0] > this._BITS_PER_RESEED &&
    new Date.valueOf() > this._next_reseed) ?

This should be:

    return (this._pool_entropy[0] > this._BITS_PER_RESEED &&
    new Date().valueOf() > this._next_reseed) ?

In Safari, this will cause an error and script termination. In Firefox, the effect is much worse - new Date.valueOf() returns an object, which never compares as greater than any integer. As an unfortunate consequence, that clause can never evaluate to true, and your Fortuna implementation's periodic reseeding never triggers...

All is not lost, though, because luckily the random_words function in which the return value from is_ready is used makes no sense. ;-) To start with, on line 1289 you have:

    if (readiness == this.NOT_READY)

But readiness here is a bit field, and this clause will evaluate to false in half the situations that is_ready actually does return NOT_READY. You surely want 

    if (readiness & this.NOT_READY)

Three lines further down, you have:

    else if (readiness && this.REQUIRES_RESEED)

This, again, doesn't do what it seems - && is the boolean and, not the bitwise and. Since this.REQUIRES_RESEED is simply a positive constant, that really becomes:

    else if (readiness)

So despite the bug in is_ready, your reseeding function actually runs every time random data is requested. Phew - who says two wrongs don't make a right, ey? ;-) Reseeding every time data is requested might open the generator to some interesting entropy exhaustion attacks, but is much better than not reseeding at all.

A corollary to all this is that you also need to address the fact that the the return value from is_ready is used incorrectly in the rest of your code and your examples. As it stands, testing for readiness with 

    if (Random.is_ready())

is wrong, because your readiness function can return REQUIRES_RESEED | NOT_READY, which is a positive integer. I'd recommend changing the interface of is_ready to have an obvious boolean return value instead, though - typing 

    if (Random.is_ready() & Random.IS_READY)

is a bit of a mouthful.

Thanks again for jscrypto.



Regards,


Aldo

[No animals were harmed producing this post. Content lightly edited for markup and formatting from the original email. Yes, I really do like JSCrypto - this error-hiding-an-error was amusing, but the AES implementation seems good (although the jury's still out on the SHA256 portion).]

Comments

linklog

07 January 2010

I'm starting an approximately weekly linklog of interesting reading I come across. The content will be mostly technical, with a liberal dollop of eclectic bric-a-brac. Enjoy!

Algorithms

Software

Visualisation

UX

Security

Comments

More posts:

recent tweets:

    follow me on Twitter

    Copyright 2008 Aldo Cortesi