led page 10 - Dave's Blog

Deriving a Non-Recursive Fibonacci Function Using Linear Algebra

In my Intro to Algorithms course in college the Fibonacci sequence was used as the example algorithm to which various types of algorithm creation methods were applied. As the course went on we made better and better performing algorithms to find the nth Fibonacci number. In another course we were told about a matrix that when multiplied successively produced Fibonacci numbers. In my linear algebra courses I realized I could diagonalize the matrix to find a non-recursive Fibonacci function. To my surprise this worked and I found a function.

Looking online I found that of course this same function was already well known. Mostly I was irritated that after all the algorithms we created for faster and faster Fibonacci functions we were never told about a constant time function like this.

I recently found my paper depicting this and thought it would be a good thing to use to try out MathML, a markup language for displaying math. I went to the MathML implementations page and installed a plugin for IE to display MathML and then began writing up my paper in MathML. I wrote the MathML by hand and must say that's not how its intended to be created. The language is very verbose and it took me a long time to get the page of equations transcribed.

MathML has presentation elements and content elements that can be used separately or together. I stuck to content elements and while it looked great in IE with my extension when I tried it in FireFox which has builtin MathML support it didn't render. As it turns out FireFox doesn't support MathML content elements. I had already finished creating this page by hand and wasn't about to switch to content elements. Also, in order to get IE to render a MathML document, the document needs directives at the top for specific IE extensions which is a pain. Thankfully, the W3C has a MathML cross platform stylesheet. You just include this XSL at the top of your XHTML page and it turns content elements into appropriate presentation elements, and inserts all the known IE extension goo required for you. So now my page can look lovely and all the ickiness to get it to render is contained in the W3C's XSL.

NetFlix Media Center and Ong-Bak

I just installed vmcNetFlix which lets you watch your on demand NetFlix movies via your Vista Media Center or any Media Center Extenders like the Xbox 360. It works well but fails poorly with some cryptic error messages and long timeouts. Be sure to get NetFlix on demand movies working in your browser before installing this plugin. Once I did that everything worked very well.

To test it out I watched Ong-Bak: The Thai Warrior in which Ting must travel from his country village to Bangkok where he works with his cousin in the city to recover his village's stolen religious artifact. Its a mix of Perfect Strangers, Street Fighter and Pad-See Ew. Martial arts movies, like porn and video games, aren't required to have a strong plot but Ong-Bak has a fine plot line and enjoyable Thai martial arts. I saw the Tiger Knee in there several times. An enjoyable movie that reminded me of watching martial arts movies with my friends in high school.

GPS Stolen

My GPS was stolen last night or this morning and I'm missing it already. For instance when I drove to Novus glass repair to get my front passenger window replaced I drove down the wrong road for a while.

When I got out of my apartment this morning there was a police car sitting in my parking lot and the officer asked me: "David? ... What'd you leave in your car?". My face must have changed a lot when I had the following sequence of realizations: (a) a police officer is asking for me by name, (b) I'm not in trouble, (c) my car must have been burgled, and (d) my GPS must be stolen.

The officer was waiting outside my complex because someone had reported my car's broken window to the police in the morning. The officer was very courteous and upon taking my date of birth noted that we were born on exactly the same day. The window's safety glass was shattered and lying in tons of tiny pieces all over the passenger seat, my glove box was open and the middle armrest where I keep my CDs was open. Nothing appears to be missing other than the GPS, the GPS power cable, and the GPS dash mount. Adding insult to theft, the their scattered my CDs throughout my car and didn't take any of them, insulting my taste in music.

My car's window should be repaired now and hopefully the rain that came in through the broken window until I covered it with plastic bags (classy!) didn't do any permanent damage.

Kids in the Hall Live in Seattle

Sarah and I saw the Kids in the Hall "Live As We'll Ever Be" Tour in the WaMu theater in Seattle this past Thursday. I'd only ever seen their television show so it was cool to see them live. I thought that them being in a live format on stage would make the show significantly different, but other than having a bad seat and not being able to see very well, and the Kids sometimes ad-libbing or breaking character, it was like watching their show. It consisted of mostly new material with some returning characters like the Chicken Lady, Buddy Cole, the head crusher, etc. Their Facebook page has two videos that they played during the show.

I've been using the best Kids in the Hall fansite with an archive of searchable transcripts since high school. But now days what with all the new fangled video websites I can link right to some of my favorite sketches from the show. Like the Inexperienced Cannibal.

And the meta-sketch The Raise.

Finished Paper Mario Games

Sarah and I have finished playing through the games "Paper Mario", "Paper Mario: The Thousand-Year Door", and "Super Paper Mario" last week (including the various Pits of 100 Trials). We played them all on the Wii, because even though Super Paper Mario was the only one released explicitly for that platform, Wii maintains compatibility with Game Cube games such as Thousand-Year Door and Paper Mario although originally released for the Nintendo 64 is now available as a pay for download game on the Wii's Virtual Console. So, yay for Nintendo!

I think my favorite of the three is Thousand-Year Door mostly because of the RPG attack system. In Thousand-Year Door and Paper Mario when you come into contact with an enemy you go into an RPG style attack system where you take turns selecting actions. In Super Paper Mario you still have hit points and such, but you don't go into a turn based RPG style attack system, rather you do the regular Mario jumping on bad guys thing (or hitting them with a mallet etc...). Thousand-Year Door and Paper Mario are very similar in terms of game play but Thousand-Year Door looks very pretty and has made improvements to how your party-mates are handled in battle (they have HP and can fall as you would expect) and there's an audience that cheers you on during your battles.

Even if the gameplay sucked the humor throughout the series might be tempting enough. Mario's clothing and mustache are mocked throughout and standard RPG expectations are subverted. I hate to describe any of these moments for fear of ruining anything but, for instance, an optional and very difficult enemy who may only be killed after hours of work only results in one experience point, or a very intimidating enemy who you imagine you'll have to fight actually challenges you to a quiz.

Despite how I personally rank them, all the games are great and I'd recommend any of them.

URI Fragment Info Roundup

Information about URI Fragments, the portion of URIs that follow the '#' at the end and that are used to navigate within a document, is scattered throughout various documents which I usually have to hunt down. Instead I'll link to them all here.

Definitions. Fragments are defined in the URI RFC which states that they're used to identify a secondary resource that is related to the primary resource identified by the URI as a subset of the primary, a view of the primary, or some other resource described by the primary. The interpretation of a fragment is based on the mime type of the primary resource. Tim Berners-Lee notes that determining fragment meaning from mime type is a problem because a single URI may contain a single fragment, however over HTTP a single URI can result in the same logical resource represented in different mime types. So there's one fragment but multiple mime types and so multiple interpretations of the one fragment. The URI RFC says that if an author has a single resource available in multiple mime types then the author must ensure that the various representations of a single resource must all resolve fragments to the same logical secondary resource. Depending on which mime types you're dealing with this is either not easy or not possible.

HTTP. In HTTP when URIs are used, the fragment is not included. The General Syntax section of the HTTP standard says it uses the definitions of 'URI-reference' (which includes the fragment), 'absoluteURI', and 'relativeURI' (which don't include the fragment) from the URI RFC. However, the 'URI-reference' term doesn't actually appear in the BNF for the protocol. Accordingly the headers like 'Request-URI', 'Content-Location', 'Location', and 'Referer' which include URIs are defined with 'absoluteURI' or 'relativeURI' and don't include the fragment. This is in keeping with the original fragment definition which says that the fragment is used as a view of the original resource and consequently only needed for resolution on the client. Additionally, the URI RFC explicitly notes that not including the fragment is a privacy feature such that page authors won't be able to stop clients from viewing whatever fragments the client chooses. This seems like an odd claim given that if the author wanted to selectively restrict access to portions of documents there are other options for them like breaking out the parts of a single resource to which the author wishes to restrict access into separate resources.

HTML. In HTML, the HTML mime type RFC defines HTML's fragment use which consists of fragments referring to elements with a corresponding 'id' attribute or one of a particular set of elements with a corresponding 'name' attribute. The HTML spec discusses fragment use additionally noting that the names and ids must be unique in the document and that they must consist of only US-ASCII characters. The ID and NAME attributes are further restricted in section 6 to only consist of alphanumerics, the hyphen, period, colon, and underscore. This is a subset of the characters allowed in the URI fragment so no encoding is discussed since technically its not needed. However, practically speaking, browsers like FireFox and Internet Explorer allow for names and ids containing characters outside of the defined set including characters that must be percent-encoded to appear in a URI fragment. The interpretation of percent-encoded characters in fragments for HTML documents is not consistent across browsers (or in some cases within the same browser) especially for the percent-encoded percent.

Text. Text/plain recently got a fragment definition that allows fragments to refer to particular lines or characters within a text document. The scheme no longer includes regular expressions, which disappointed me at first, but in retrospect is probably good idea for increasing the adoption of this fragment scheme and for avoiding the potential for ubiquitous DoS via regex. One of the authors also notes this on his blog. I look forward to the day when this scheme is widely implemented.

XML. XML has the XPointer framework to define its fragment structure as noted by the XML mime type definition. XPointer consists of a general scheme that contains subschemes that identify a subset of an XML document. Its too bad such a thing wasn't adopted for URI fragments in general to solve the problem of a single resource with multiple mime type representations. I wrote more about XPointer when I worked on hacking XPointer into IE.

SVG and MPEG. Through the Media Fragments Working Group I found a couple more fragment scheme definitions. SVG's fragment scheme is defined in the SVG documentation and looks similar to XML's. MPEG has one defined but I could only find it as an ISO document "Text of ISO/IEC FCD 21000-17 MPEG-12 FID" and not as an RFC which is a little disturbing.

AJAX. AJAX websites have used fragments as an escape hatch for two issues that I've seen. The first is getting a unique URL for versions of a page that are produced on the client by script. The fragment may be changed by script without forcing the page to reload. This goes outside the rules of the standards by using HTML fragments in a fashion not called out by the HTML spec. but it does seem to be inline with the spirit of the fragment in that it is a subview of the original resource and interpretted client side. The other hack-ier use of the fragment in AJAX is for cross domain communication. The basic idea is that different frames or windows may not communicate in normal fashions if they have different domains but they can view each other's URLs and accordingly can change their own fragments in order to send a message out to those who know where to look. IMO this is not inline with the spirit of the fragment but is rather a cool hack.