Monday, October 08, 2012

Drawing Factorization Diagrams Programmatically

I recently saw a post on a blog called The Math Less Traveled about creating neat-looking factorization diagrams using Haskell and the Diagram library. In that light, I'd like to set the record straight right away: the entire idea of my blog post is lifted. The basic idea is that you can represent a number's factorization by creating diagrams like the following that make it easy to see what a number's prime factors are.
The author makes this comment at the end of the post:
I wish I knew how to make a website where you could enter a number and have it show you the factorization diagram… maybe eventually.
After I read that, I felt like I had to do it myself. I decided to ignore the Haskell code and just take a stab at implementing something using JavaScript and the <canvas> element.

I knew that I whatever I came up with would be unlikely to match the elegance of the Haskell version, but after whipping up a very primitive Diagram interface, I had some code that made it pretty simple to implement the kind of factor diagrams I wanted.

Instead of starting with the greatest factor and moving down, my version starts by filling the entire canvas space with a circle, which can be thought of as 1. It then loops through each factor, F, and each time it scales the current diagram down proportionately to F, and places copies of the scaled version at each vertex of an F-sided polygon filling the entire canvas space. If you're a programmer, it's probably easier to just read the code than to try and follow that explanation.

All in all, it actually works pretty well, although I would definitely need to expand my Diagram interface before it could be considered useful for doing much more than render these diagrams. For fun, here is an example of how to render the factor diagrams for the numbers 1-25 on a canvas element:

This is the output:


And since I claimed the whole point of this project was to create the interactive Web version, here it is:

Tuesday, October 02, 2012

Solving Einstein's Puzzle with Haskell

I recently read Martin Erwig's interesting paper "Escape from Zurg: An Exercise in Logic Programming" [PDF]. It's a few years old, but still relevant, I think. The paper examines a homework assignment in a computer science course where the students were asked to solve a simple logic puzzle in the programming language of their choice. The paper goes on to compare a solution in Prolog with a solution in Haskell.

The solution in Haskell is actually fairly simple, as it just stores the solution space in a list and filters the list with a user-defined function which imposes the problem's invariants. Because Haskell is evaluated lazily, filtering the list ends up being equivalent to running a depth-first search with backtracking. It's pretty cool that the language gives this to the programmer for free.

I know "enough to be dangerous" with Haskell, and this paper got me thinking about solving other kinds of logic problems with Haskell. It seemed to me that the list monad (in conjunction with the MonadPlus instance for lists) could be used to model a simple constraint solver. I decided to see if I could model and solve Einstein's Puzzle.

Modeling the problem was not bad at all. I defined algebraic data types for each of the five main variables, and then defined a house as a 5-tuple containing each variable. I defined the street as a list of five houses. I then wrote functions for each of the problem's fifteen constraints. Each constraint function was of type [(Color, Nationality, Pet, Beverage, Cigarette)] -> Bool so that I could enforce the constraints with guard. Writing each constraint function was really easy due to Haskell's pattern-matching syntax. Here's one particularly nice example:

norwegianFirstHouse ((_, Norwegian, _, _, _):_) = True
norwegianFirstHouse _ = False

While writing the program, I noticed that the running time started to increase exponentially by the time I got to about the tenth constraint. I was more interested in solving the puzzle than optimizing my program (for the moment), so I decided to just plug in the rest of the constraints, compile with optimizations, and run the program and see what it would come up with.

Embarrassingly, the program took about two hours to complete. Although, considering the solution space includes close to 300 quadrillion possibilities, perhaps that's not too unreasonable for such a naïve solution (a well-written Prolog program could solve this problem orders of magnitude faster). I won't reveal the answer to the puzzle here, but my program did find the correct solution.

So my experiment was a partial success, I'd say. On the one hand, I solved Einstein's puzzle, and writing tho code was a breeze. On the other hand, my solution is hopelessly inefficient. I do believe that Haskell's list monad could be used as the foundation for a more efficient constraint solver, though. At this point, my only truly unresolved question is whether I qualify for Einstein's "2% of the population who can solve the puzzle." Unfortunately, Einstein seems to have been silent on the matter of those of us who can solve his puzzle by cheating.

Here is the complete code:

Thursday, September 06, 2012

The Tuner's Dilemma

Here's a musical tidbit that tends to take people off guard: It is impossible to play in tune on a piano. Or a guitar. Or an organ. Fretted bass... The list goes on, and includes essentially all tuned instruments that don't provide the player with a reasonable way to manipulate the exact pitch of the notes that are produced.

This is because of what I've decided to call The Tuner's Dilemma, and it's best understood by placing oneself in the mindset of a tuner. As a practical example, let's think about tuning a guitar. Our task is to tune a six-string guitar in standard tuning: E2-A2-D3-G3-B3-E4.

This means that the musical interval between each of the strings is a perfect fourth, with the exception of the G- and B-string, which form a major third. Thinking about this, let's see what happens if we tune these intervals perfectly.

We won't worry about our starting point. In this example, we'll assume our bottom E-string is perfectly in tune (perhaps when played open, it plays at 82 Hz, but that doesn't really matter).

A true perfect fourth is typically defined as two pitches whose frequencies form a ratio of 4:3. The ratio for a major third is 5:4. There are alternative definitions of these intervals, as we'll see later, but these simple, rational ratios are very commonly accepted. An octave is almost universally understood to form a 2:1 ratio.

Ready, Set, Tune

Let's start. Our low E2 is in tune, so now we tune our A2 so that its pitch is exactly 4/3 higher. If you have a guitar, you can do this yourself -- if your guitar is reasonably in tune, adjust your A-string so that you hear zero beats in the sound wave when E2 and A2 are played simultaneously. Whether you're using math or your ear to come up with the new pitch, this process is known as forming a just interval.

Say we now do the same between A2 and D3 and between D3 and G3. Then we tune a just major third from G3 to B3 and a final perfect fourth from B3 to E4. Each interval we've tuned has been completely in tune.

So what's the problem? The problem presents itself when you try playing your two E-strings simultaneously. These notes are two octaves apart and should thus form a 2:1 ×  2:1 = 4:1 ratio. Yet your ears will tell you right away that something is amiss.

Let's get a better idea of what happened by examining the numbers. You'll notice from the previous paragraph that I used simple multiplication to come up with a compound interval (i.e. the double octave, 4:1). We can use this technique to find out what the actual interval between our two E-strings actually is:

4:3 × 4:3 × 4:3 × 5:4 × 4:3= 1280:324 = 320:81

320:81 is approximately, but not exactly, equal to 4:1. This is the mathematical view of the dilemma, and the technical term for the 81:80 (4 ÷ 320:81) discrepancy is a comma. There are all kinds of commas, because there are all kinds of tuning systems. Let's stay focused on this "guitar comma" and investigate what we can do about it.

Solving the Tuner's Dilemma

Put succinctly, there is no way to solve The Tuner's Dilemma. However, the problem can be at least somewhat mitigated. For the sake of example, let's implement a naïve solution that fixes our octaves at the cost of making our perfect fourths, well, not so perfect. We'll keep our major third intact.

Since our E4 fell flat of where it should have been, common sense tells us that our perfect fourths will all have to become a little sharp. How sharp? We need to distribute the comma evenly between our four perfect fourths. This means that each fourth is widened (multiplied by, mathematically speaking) by a factor of the fourth root of the comma, or  3 / (2 × 45). Our resulting definition of a "perfect" fourth is a ratio of 2:45. This is getting pretty gnarly. Let's persevere and try it, though. Here's the new tuning math:

2:45  ×  2:45  ×  2:45  ×  5:4  ×  2:45  =  80:20  =  4:1

That outcome looks better. This isn't a very satisfying solution, though. We've essentially distributed 100% of the comma across our perfect fourths and nowhere else, rendering them noticeably out of tune while other intervals, like the major third between the G- and B-string, remain in tune. In practice, a more balanced approach is used.

Equal Temperament

Equal temperament is the system used to tune the majority of instruments in the Western musical world. It allows instruments to be tuned so that they sound the same in all 12 keys, and that all intervals are acceptably close to their just counterparts, although in equal temperament, only octaves remain justly tuned.

This is done by means of a simple function, f, which takes as its input the number of semitones, i, above a given starting pitch and produces the tuning ratio for the interval corresponding to that number of semitones.

f (i) = 2i/12

A fourth can also be defined as being equal to 5 semitones, so let's try using the equal temperament function and seeing how its result compares.

f (5) = 25/12 = 1.334839854


Tuning systemValueIntonation
Just intonation4/3 (1.3)In tune
Equal temperament1.3348398542 cents sharp
Solution above1.337480615 cents sharp

So you can see that equal temperament produces a fairly acceptable "perfect" fourth. Note that this interval is much closer to being in tune than what we came up with in our naïve solution above (5 cents is often thought to be the minimum distinguishable difference in pitch for most humans). The noticeable improvement in the equal tempered perfect fourth is due to the fact that equal temperament distributes the comma evenly throughout all twelve notes in the scale.

Conclusion

Does equal temperament solve The Tuner's Dilemma? No. However, it does a reasonable job of allowing us to tune our instruments once and be able to play in any key without retuning.

Over the centuries, countless tuning systems have been devised to work around The Tuner's Dilemma. Many of them have interesting characteristics that make them worth studying and hearing. Here are some links to more information:

Friday, August 24, 2012

Every Little Thing

I'd like this blog to contain a healthy number of posts about music. My friend Todd recently asked me if I could send him the chords for a song, "Every Little Thing" by Olentangy John.

A quick Google search didn't seem to turn up any results. I actually couldn't even find the lyrics. So the following is my rough cut at a lead sheet for this song. If I were a better guitar player, I'd provide some tabs for the guitar part. I still may do that, but it'll have to wait for now.

Every Little Thing
By Olentangy John

INTRO (4 bars)
G     /     /     /

VERSE 1
G
I built a house up on the hill where I                           
C             G
Always said I would. Watch you
C                      G
Pass on the interstate below but
D                C
I don't remember you or what it is you
G
Drove. But

CHORUS
Em    D      C
Every little thing. Yes
Em    D      C
Every little thing I done is
G
Yours. And

Em    D      C
Every little word. Yes
Em    D      C
Every little word I sung was
G
Mine.

VERSE 2
I seen a girl in church sittin' three rows back in a
Dress that you would wear. She's
Doin' that thing you used to do with your hair, but her
Mama don't look like yours and your mama wouldn't be sittin'
There. But

CHORUS
Every little move. Yes
Every little move she makes is
Square. And

Every little thing. Yes
Every little thing she says is
Fair.

INSTRUMENTAL BREAK
G     /     /     /
C     /     G     /
C     /     G     /
D     /     C     /
G     /     /     /
Em D  C     /
Em D  C     /
G     /     /     /

VERSE 3
I built a house up on the hill, but
I can't call it home.
Too many eyes in the pine walls and the
Interstate headlight faces burn too bright in the
Dawn. But

CHORUS
But every little thing. Yes
Every little thing
I done is yours. And

Every little word. Yes
Every little word I sung was
Mine. And

Every little thing. Yes
Every little thing I own is
There.

Wednesday, July 18, 2012

Hello world.

In the immortal words of George Costanza: I'm back, baby!

For a long time now, I've contemplated reviving my Internet presence, and for better or for worse, I'm officially doing so. I am beginning the whole endeavor with this blog. I hope that I can eventually conjure up some other stuff as well.

It has been my intention for a long time to launch my blog on a blogging platform of my own design and implementation. That is all in the works, albeit moving at a snail's pace, and the fact is that I've lately found myself wanting to blog more or less right now, yet having no means of doing so readily available. So I'm beginning by using Blogger to produce a blog that might very well document my ongoing efforts at producing a Blogger alternative.

Other possible topics for blogging that spring immediately to mind include: cooking and food experiments, all manner of technology commentary, various Tacoma happenings, analyses and/or transcriptions of music that I like, the occasional political rant, and possibly much, much more.

If any of the above seems of interest, I hope you will check back in from time to time. My theory is that regular writing will be good for me personally, but it would also be nice to have a small audience.