Tuesday, December 25, 2012

Pufftygraph, an HTML5 Spirograph with touch-driven gears

First, thank you, now defunct Kenner, for the most excellent Spirograph toy. I had a Kenner 401 Spirograph set as a boy, and I fondly remember the joy of trying to drive the gears with a pen, and watching as the hidden shapes were revealed.

About a year back, I did some searches for online spirograph apps, thinking little Scout, then 6 years old, would enjoy it. I found some nice sites talking about how hypotrochoid math works, a complete listing of the gear ratios of one of the Kenner 401 set with close-up images of each gear, and several Flash, java, and HTML5 apps to draw hypotrochoids with given gear ratio inputs. However, nowhere did I find an app that showed the gears move as you drew, which as far as I was concerned was the main draw.

I decided that was a perfect excuse to brush up on my HTML5 animation skills, and within a few days I had code that would draw actual gears that followed mouse movements or touch gestures, drawing a hypotrochoid in its wake. I added the necessary elements to let it function as a smartphone web app, posted it here, and showed it to my daughter Scout, who thought it was a fun enough idle amusement for a minute or two, but since it could only make the one shape, didn't have much replay value.

I shelved the code and moved onto other things, but late this year I returned to the app and spruced it up some, and presented it to Scout under the title Pufftygraph ("Puff" is one of her nicknames) as one of her official Christmas presents. She and her mom enjoyed playing with it while Christmas cookies were in the oven, and it seemed to be a big hit with both of them. Here's an example of a drawing it can produce now:

Tuesday, November 27, 2012

iPhone multi-touch events and braille-like input

Below is a quick demo of me "typing" a short phrase and some numbers using a modified version of my Blind Input iPhone web app. This is a proof of concept app that doesn't integrate into the phone's other text entry forms, and is arguably more difficult to learn than braille. In case it appears I've solved some great accessibility problem, Siri and the iPhone's native accessibility features has me beat in spades, and my app is only an interesting idea I wanted to experiment with.

Monday, November 12, 2012

The math behind HTML5 context transforms

If you've drawn widgets with HTML5 canvases, you've no doubt come across such methods as ctx.translate(x, y), ctx.scale(x, y), and ctx.rotate(radians). These are all convenience methods for ctx.transform(a, b, c, d, e, f), which applies a generic affine transform to the canvas. Consulting the specs will show that the a-f variables refer to this transformation matrix:

If this looks incomprehensible, it might help to express the matrix in basic Algebraic terms:

 x' = ax + cy + e, and
 y' = bx + dy + f

Sunday, November 04, 2012

Simple Javascript RGB/HSV converter

This is a simple and straightforward converter between RGB and HSV values, with RGBs from 0 - 255 and HSV values with hue from 0 - 359 and S/V from 0 - 1. I wrote it for an as yet unfinished HTML5 red-eye correction tool, but I'll be unable to devote much time to side-projects until after the holidays, so I thought I'd put this up now in case someone found it useful.


function getHSV(r, g, b) {
  var h, s, v, max, delta;

  // v (value) is the highest of the RGB values scaled to [0-1]
  max = Math.max(r, Math.max(g, b));
  if (max == 0) return [0, 0, 0];
  v = max / 255;

  // delta is the difference between the largest and smallest of RGB
  delta = max - Math.min(r, Math.min(g, b));
  if (delta == 0) return [0, 0, v]; // No delta = grey, only v is significant

  // s (saturation) is delta divided by max
  s = delta / max;

  // h (hue) is a number in degrees describing the color's angle on the hsv color wheel
  if      (r == max) h =     (g - b) / delta;
  else if (g == max) h = 2 + (b - r) / delta;
  else if (b == max) h = 4 + (r - g) / delta;

  // convert hue to degrees
  if (h < 0) h += 6;
  h *= 60;

  return [h, s, v];

function getRGB(h, s, v) {
  var quadrant, max, mid, min, fraction;
  max = Math.round(v * 255);
  if( s == 0 ) return ([max, max, max]); // Greys

  // Quadrant is between 0 and 5, where 0, 2, and 4 are red, green, and blue
  h /= 60;
  quadrant = Math.floor(h);

  // fraction is distance away from quadrant representing hue's primary color
  fraction = (quadrant % 2 == 0) ? (1 - h % 1) : h % 1;

  // min and mid are the smaller two RGB colors in the final return array
  // We don't know what primary colors they represent...
  min = Math.round(max * ( 1 - s ));
  mid = Math.round(max * ( 1 - s * fraction ));

  // ...until we check what quadrant we're in
  switch (quadrant) {
    // reds
    case 5: return [max, min, mid];
    case 0: return [max, mid, min];
    // greens
    case 1: return [mid, max, min];
    case 2: return [min, max, mid];
    // blues
    case 3: return [min, mid, max];
    case 4: return [mid, min, max];

Thursday, October 11, 2012

Internet Explorer rendering issue fixed

I noticed today that viewing this site in IE blew things up. This was due mainly to putting javascript source for HTML5 canvas operations above the fold in a couple of blog entries.

I fixed that, so the page should look normal to IE users... however, you're missing out. Use an HTML5-capable browser instead to get the full gist of what I've been working on lately. And also the cool pacman banner.

In other news, Adelaide turns one year old on Sunday! Here she is with her sister Scout, the person who has given Liberty and I the most help with the baby, and who is possibly the most loving and patient sister a baby could have. I love them both more than I can say... but I'll keep trying anyway.

Sunday, July 29, 2012

Counting Squares

NPR's "Science Friday" posted a square-counting puzzle on their Facebook page yesterday, and a friend of mine challenged me to write a program to count them, hopefully coming up with the same answer (40) that we did with a manual count.

My first pass is a generalized (more or less) solution where different sized boards can be created with arbitrary horizontal or vertical lines. It's not the most solid thing I've ever written, doesn't take user inputs or validate the hardcoded input, but it illustrates a simple, brute-force attack of the problem.

This requires an HTML5-capable browser (Chrome, Firefox, Safari), and should start counting 5 seconds after loading.

Tuesday, July 10, 2012

Dear Scout

So Scout's father moved to California, and this weekend I flew her out to see him, where she'll stay until just before school starts. Combine missing a girl I love with my recent dive into cryptography, and the natural outcome is, of course, to write her a letter - in secret code!

When I was in high school, I had the idea to write a substitution cipher using symbols for letters. My code consisted of squares, circles, triangles, stars, horizontal, vertical, and diagonal lines, plus and equals signs, and some other unique but easy to draw symbols that the intervening 25 years has wiped from my memory. I used it to write a letter of no particular consequence to my friend Rachel (actually she was my friend Bill's friend, who I poached for purposes of odd geeky stuff like inventing strategy games to play and reviewing her early short stories), and she decoded it with little effort, predictable given her intelligence. What made it pretty straightforward to decode was context. I had formatted the letter like a letter, complete with spaces between words, and the encoded greeting "Dear Rachel" which let her immediately translate the 7 letters a, c, d, e, h, l, and r. Since "a" was included, a lone "I" was easy to translate, and then the rest could be filled in with a style akin to Sudoku, filling in words that were mostly complete already, and adding the newly translated letters to other words.

I wanted to do something like that for Scout, but I thought of a symbol set that would be both easy to write a program for, and comprise 26 letters and 10 digits: pairs of dice. Each die face could have a value of 1 through 6, giving 36 possibilities for a pair. I didn't want the code to be as easy as iterating through the alphabet and replacing 1.1 with a, 1.2 with b, etc., but at the same time I didn't want it to be so complex as to be off-putting for a 7 year old. It eventually ocurred to me that "Dear Scout" was an even better greeting than Rachel's, as it had no overlapping letters. If I kept the cipher alphabetized, but pulled "Dear Scout" to the beginning of the cipher, then the greeting would look like this:

Saturday, July 07, 2012

Encryption, part 2: Elgamal and the Discrete Logarithm

In my quest to better understand the mechanics of encryption, I've found the Elgamal method the hardest to get my head around. The problem was not that the underlying math is difficult, it was that I didn't know some of the background terminology (cyclic group, congruence class, group isomorphism), the various explanations online all used different variables, and made references to "mathy" things it was supposed the reader was already familiar with. Lastly, the articles on discrete logs and Elgamal encryption on my go-to site for techie info, Wikipedia, were a hot mess, mistaking modular multiplicative inverse for division, and leaving out crucial middle steps (how to get from "collect underpants" to "profit", as it were). The whole affair really shook my faith in using Wikipedia as a trusted source for tech info.

A relatively simple explanation is this: You and your buddy both have a secret that combines to form an encryption key. To encrypt a message, multiply the key by the message value, divide by a modulus, and the remainder is your ciphertext. To decrypt, multiply the ciphertext by the key's inverse, and, again, divide by the modulus, and the remainder is the original message. Fin.

There is, naturally, some math involved, most of it geared around how to build the secret key so only you and your buddy know it, without either of you revealing your part of the secret. Let's start with some of the basic terminology, then get into the mechanics of building the encryption key.

Thursday, June 28, 2012

RSA encryption and the other Sun Tzu


Before we get started on how exactly RSA works and how it's related to Chinese mathematicians, it's important to have a basic comprehension of modular arithmetic, totients, and the "modular multiplicative inverse". None of these are very difficult, but they aren't commonly talked about, so here's a quick refresher:


In simplest terms, what you're looking for in a modular problem is the remainder of a division. Dividing 7 by 3 gives 2 with a remainder of 1. Expressed as a modular equation, 3 is the modulus, and 7 and 1 are congruent. The equation can be expressed like this:

7 ≡ 1 (mod 3)

Wednesday, June 13, 2012

Four ways to construct a pentagon

There are animations of the 4 compass and straightedge construction techniques at the bottom of this entry, but they require an HTML5 capable browser. (I suggest Chrome, but the animations should work with a modern Firefox, Safari, or Chromium... but let me know if they don't.)

Also included are animations of the first 6 "problems" in book 1 of Euclid's Elements, as a preview of a larger project I'm working on, and two variations on creating a heptadecagon (a seventeen-sided polygon).

Over the last few weeks I've been spending what free time I have obsessing over the odd mathematics of Argand diagrams, complex roots, and how they relate to constructing regular polygons with a compass and straightedge. I found, among other things, that I had forgotten quite a bit from my trig and geometry classes from 25 years ago.

Friday, May 18, 2012

Compass and Straightedge geometry meets HTML5

This is a proof of concept build of an HTML5 engine to perform classical Greek compass and straightedge calculations, as described in this Wikipedia article. In brief, an initial set of points can be created, and then points can be connected by lines, circles can be drawn with one point as center and another as one point in the circumference, and finally the points where circles and/or lines intersect can be added as new points. With those simple rules, angles and line segments can be bisected, and certain regular (equilateral) shapes can be created.

I have created a rudimentary language to describe the adding of points, lines, and circles, and finding their intersections, which I discuss briefly after the demo below. Without further ado, choose a sample "program" to run to bisect an angle or create a regular shape. If you're a fan of Gauss, be sure to check out the heptadecagon.

Thursday, May 10, 2012

Animated prime number machine

This uses the HTML5 canvas architecture, so no IE8 or less; sorry. I have only tested it with Google Chrome, so it may not work in other HTML5-capable browsers. If you find this to be the case, please leave feedback with any errors you see, and what browser version you're using, and I'll see what I can do to get it working for you.

The principle of the prime number machine is of rolling coins and elevators. I created this because I thought it would be neat to have a way for prime numbers to be produced by a set of mechanical rules rather than with pure mathematical methods. Here is a basic description of the rules:

  • If a coin rolls into an empty box, it creates an elevator with the height shown on the coin, and a new empty box appears.
  • If a coin hits the top or bottom of an existing elevator, it bounces off with no effect.
  • The coin's number increments after each cycle
  • The elevators go down a floor during each cycle until the top car is flush with the ground line, then they begin going back up to where they started.

This results in two basic phenomena: All new elevators correspond to prime numbers. When a coin does not have a prime number on it, all of the elevators corresponding to the coin's prime factors have a car flush with the ground.