wellons

Wordpress Blog

2008-07-06T14:29:00.000-07:00

I'm experimenting with a Wordpress blog. So far the key advantage is that it does not impose the black boxes on my images.

Publishing Latex to the Web

2008-07-04T18:54:00.000-07:00

It's gross.

With that in mind, I'll say a few words about how I got somewhat nice-looking mathematical notation into blogspot a few days ago. I originally wrote that entry in TexShop and put in on my website as a PDF file. While this shares it with my fans, there are some disadvantages to PDfs as opposed to HTML in a blog entry:

* As a blog entry, it is intregrated into my blog and it benefits from the search engine crawling, incoming links, tags and appearing with the rest of my recent writings.

* PDFs are less accessible than HTML. It's often more work for the reader to download it if your browser doesn't display PDFs inline and it can be harder to search or cut and paste.

Let me mention two of my workflow principles:

* There must be one master version of a document. All edits should be made to this copy, and changes are propagated to all other formats and versions as automatically as possible.

* The master version should be the format where is the easiest and most natural to express oneself. For example, LaTeX makes it many times easier to create equations such as those appearing in my most recent posting mentioned above.

It was clear I had to do the editing in LaTeX, and develop a way to publish to Blogspot. Below is the Bash script I came up with. It has very rough edges. I believe in programming with a focus on a particular problem. As I use the programs in this entry in the future, they will doubtlessly improve greatly. In the meantime, any comments are welcome. Be warned that Blogspot's narrow text column may be wrapping some of the lines.

#!/bin/bash tex_file=$1 name=`cut -f1 -d'.' <<< $tex_file` echo Operating on $name... rm -f -- $name-trimmed.html.txt temp.html links.sh latex2html -no_navigation -auto_prefix -split 0 -info "" -noaddress $tex_file xmllint --format --html $name/index.html > index.html.new mv -f index.html.new $name/index.html arg="'s/src="'"'$name'-img/src="http:\/\/jonathanwellons.com\/'$name'\/'$name'-img/g'"'" echo $arg echo perl -pi -e $arg $name/index.html >> links.sh chmod 755 links.sh ./links.sh purge-html.pl $name/index.html >> $name-trimmed.html.txt rsync -vaz $name/ jonathan@my_servers_ip:/var/www/jonathan/$name

Let's step through the lines one by one.

#!/bin/bash
This tells the shell to use bash to run the script.
tex_file=$1 name=`cut -f1 -d'.' <<< $tex_file` echo Operating on $name...
This segment takes in a variable tex_file that holds the name of the Latex file to convert. It then trims off the extension and saves it as the name of the project.

rm -f -- $name-trimmed.html.txt temp.html links.sh
This clears out the temporary files we'll use later.

latex2html -no_navigation -auto_prefix -split 0 -info "" -noaddress $tex_file
This is the most important part. There is actually a pre-existing program called latex2html that does just what it suggests. It doesn't do a perfect job, and blogspot has a number of idiosyncrasies, most of the rest of the script is accommodating the personality of this wonderful (seriously) program.

xmllint --format --html $name/index.html > index.html.new mv -f index.html.new $name/index.html
xmllint is an excellent program that cleans up XML and HTML. I use it here to make the HTML much nicer to look at and process later.

arg="'s/src="'"'$name'-img/src="http:\/\/jonathanwellons.com\/'$name'\/'$name'-img/g'"'" echo $arg echo perl -pi -e $arg $name/index.html >> links.sh chmod 755 links.sh ./links.sh
One of Blogspot's weaknesses (to me) is image uploading. It seems that you can only upload five at a time, and even without that restriction, I wouldn't put up with the hassle of uplaoding the dozens of images needed for a blog entry generated from Latex. This is especially true because many of them could change as the source document is corrected or refined. Instead, I host the images on my personal site and change the links produced by latex2html to use these new URLs.

purge-html.pl $name/index.html >> $name-trimmed.html.txt
Much of the HTML tags produced by Latex2html are redundant or interact poorly with Blogspot. This is a program I wrote to strip most HTML tags, which can be found at the end of the file. I originally set out to use Perl's HTML::Parser module, but this turned out to be easier to do myself. This leaves a file that can be opened in any text editor and copied into the Blogspot editing interface. For my last entry, it was barrels-of-gold-trimmed.html.txt.

rsync -vaz $name/ jonathan@my_servers_ip:/var/www/jonathan/$name
Finally, push all the images produced by latex2html up to my server.

Any comments or ways to improve are welcome (I am sure there are many). In particular, if someone knows a way to better clean up the spacing and get rid of the borders on the images that Blogspot's CSS adds, that would be helpful.

Appendix: purge-html.pl

#!/usr/bin/perl -w use strict; use HTML::Parser; use Data::Dumper; my $file = shift; my $okay_tags = { 'img' => 1, 'table' => 1, 'td' => 1, 'i' => 1, 'tr' => 1, 'div' => 1, 'a' => 1, 'h2' => 1, }; my $no_content_tags = { 'title' => 1, 'h1' => 1, }; open(IN, "<$file") or die "Couldn't open $file: $!"; undef $/; my $data = <IN>; $data =~ s/<!--[^>]*>//gs; my $lines = [ split('<', $data) ]; my $result = ''; foreach my $line (@$lines) { $line = '<' . $line; if ($line =~ /^<$/) {next;} if ($line =~ /^<!/) {next;} $line =~ /<(\/?)([^ >]*)([^>]*)>(.*)/s; my $end = $1; my $tag = $2; my $rest = $3; my $content = $4; my $temp_result = ''; if ($tag =~ /^a$/) { if ($rest =~ /(.*")(.*)(#.*)/) { $rest = "$1$3"; } $result =~ s/\n$/ /; } if ($okay_tags->{$tag}) { $temp_result = '<' . $end . $tag . $rest .'>'; } unless($no_content_tags->{$tag}) { $temp_result .= $content; } if ($tag =~ /^a$/ || $content =~ /^$/) { $temp_result =~ s/\n//g; } $result .= $temp_result; } $result =~ s/\n\n*/\n/sg; $result =~ s/^\n//g; print $result;

Barrels of Gold

2008-07-01T19:49:00.000-07:00

Problem

My friend Brian Marion posed a variant of the following problem:
Suppose I just robbed Fort Knox. I was in a rush and I put the gold in what I had available: 3 large barrels. I didn't keep track of how much I put in each one, I just threw bars into whichever was closest until the klaxons drove my nerves over the edge. Then I hammered down their lids and bailed - I can't even be sure that a particular barrel has anything in it.
Since you helped plan the heist, I'll let you have any one of these three sealed barrels that you want. Of course, even an empty barrel is too heavy to lift by hand, so it's hard to tell which has the most gold. The only way you can measure their contents is to see if the forklift can lift them. As a safety feature, our forklift can be calibrated to a certain weight, which it will lift no more than. However we can only set this once because changing it a second time requires retooling and a visit from the manufacturer, which would blow our cover.
We know this: these barrels are holding between 0 and 1000 pounds of gold, with a uniform, random distribution. You get to pick a weight, any weight you'd like and test which barrels are heavier than that, and which are lighter. If just one is heavier and two are lighter - great! You found the one with the most gold. If there's a tie for heaviest, you'll just have to pick one. But hey, you might eliminate the lightest one and that's better than no information, right?
Suppose the forklift's zero calibration is the weight of an empty barrel, so we can ignore that number. Therefore, if you set it to 500 pounds, you have exactly a 1/2 chance of getting a particular barrel too heavy to lift, but a 3/8 chance of getting one too heavy and two too light. On the other hand, you might get two too heavy, and you'll wish you had set it higher. Obviously, there's a tradeoff: higher weights are less likely to have a tie among several barrels being the heaviest, but on the other hand they risk overshooting all the barrels and you'll be stuck just picking one of the three.
What is the weight capacity you should set on the forklift to maximize your average expected gain?

Solution

First we'll solve a more general problem, then plug in the numbers to solve this one. Without loss of generality, say the amount of gold in a barrel ranges from 0 to 1. Suppose there are barrels and (for guesses) calibrations available to us. Suppose the set is the set of calibrations, which we'll write as
. will be the biggest one and they descend from there, so this equation is true:

(1)

Finally, add the two constants and to make our formulas cleaner. Each barrel can fall into any of the ranges: less than the smallest calibration, bigger than the largest, or between any pair of consecutive calibrations.
To find the expected value of a set of calibrations, we can find the expected values of each of these gaps and multiply those values by their probabilities, then sum up the products. The average value of a barrel between and is
and the only way you'll end up with that as the amount of gold you get is if the largest barrel is in that range. Fortunately, that probability is easy to calculate: the chance of all the barrels being less than is and the chance of them all being smaller than is , so we can simply subtract these two powers to get the probability that all the barrels are less than , but not all are less than .
Then the expected value is

			(2)

The maximum value of can be found by taking partial derivatives with respect to each , setting these expressions to zero, and solving them simultaneously. The constant 1 will not survive differentiation and the is superfluous. A variable appears in 4 terms, namely

with derivative,

Thus the solution can be found by solving the equations:

(3)

Finally, If g = 1 and b = 3

Returning to our original problem, if there are 3 barrels and 1 calibration , the Equations (3) require that we solve

Therefore, the solution is
, meaning the best calibration is 577 lbs. This has a nice 42% chance of isolating the heaviest barrel and a mere 27% chance of not separating the barrels at all. You must be wondering what your payout is. By Equation 2 it is 748 pounds of Gold.

Another Example, g = 3 and b = 4

As another example, for 3 calibrations
and 4 barrels, Equations (3) are

This might be pretty tricky to solve by hand, but the mathematical software Sage gives the numerical solution:

In fact, Sage finds 57 solutions but only 5 are real. Of these 5, only 1 satisfies the ordering in Inequalities (1).

The Factorial Base II

2008-06-13T15:28:00.000-07:00

After my factorial base post, a commenter asked about multiplication and it turns out multiplication is hard in factoradix, as far as I know. A natural question is, what does factoradix make easy? Here's an example: testing for divisibility.

In fact, this can be downright awesome by comparison. In decimal, testing if a number n divides into m takes time about equal to the length of m. Checking if 3 divides into a billion digit decimal number will take your computer about one billion cycles, within some constant factor of time spent.

Checking if m divides n in factoradix takes time proportional only to m. Checking if 3 divides a billion digit number in factoradix (which would be about a 9 billion digit number in decimal because of decimal's less efficient use of digits), only requires looking at the last 2 places!

Let me give an example. Does 3 divide into 9a0a4023220011?

Recall that each of the places corresponds to a certain number of factorials. Well, every factorial greater than 2! contains 3 as a factor, by definition. Therefore, the values of any digit other that the two rightmost, is irrelevant, because it could only change the value of the number by a multiple of three. This is sort of like how you can tell if a decimal number is divisible by ten only by looking at the last digit (all the other digits cannot affect the divisibility by ten).

Getting back to 9a0a4023220011, we need only check 11. Sure enough 11(factoradix) = 1 * 2! + 1 * 1! = 3. So yes, 3 does divide 9a0a4023220011.

Is No One Rational?

2008-06-12T21:23:00.001-07:00

I ran into a math subproblem in the course of a bigger problem. I thought I'd give the Internet a shot before posting the answer. Here it is:

Show that for any finite set of positive real numbers, there must exist some number x such that x times each of the numbers in the set produces an irrational number.

Or rephrased:

If n runners start out together on an infinite race, each at a constant speed, which is different from the others' speeds, show that at some time each one will be an irrational distance from the start line.

Just a reminder: irrational numbers are those that cannot be written as a fraction a/b with a and b both whole numbers.

The Factorial Base

2008-06-08T13:56:00.000-07:00

We've all heard of binary and decimal as systems to represent integers. The idea is simple: In the decimal number 328, 3 reflects three hundreds, 2 reflects two tens and the 8 adds in eight ones.

The same number is 101001000 in binary. Specifically, one 256, one 64 and one 8. 256, 64 and 8 are the eighth, sixth and third powers of two, and those occur as ones that many spaces over from the right side of the number.

Clearly, numbers are longer in binary than they are in decimal, but the digits are much simpler in binary. If all we cared about was reducing the number of digits, we could use base 20, or 2008 or the largest number we could think of.

Of course the tradeoff that comes is that it can be hard to make up and keep straight all the extra digits we would need. For example, the decimal number 1330 only needs three digits in base 11, but each of those digits is the digit "10", because 1330 = 10 * 11² + 10 * 11 + 10. How would we write this? One option is the hexadecimal system where 10 is a, 11 is b and so on. Then 1330 (base 10) = aaa (base 11). We can take this all the way up to base 36 using all 26 letters, in which case a long decimal number like 2621102907451 (base 10) compacts down to xg48zv3v (base 36).

But for a small number like 10, it seems unreasonable to write it as "a" just to save one digit. What if there was some way to have small digits for small numbers and compact representations for large numbers? It turns out there is a way to do this using the "factorial base" or "factoradix".

In factoradix, the rightmost digit is base 2, the next one is base 3, and so on. As an example, here's how you would calculate the factoradix notation for 99:

First we notice that 99 gives a remainder of 1 when divided by 2. The quotient is 49. We keep both of these numbers: 1 because it is the rightmost digit of the factoradix representation of 99 and 49 because we need it for the next steps. Next, 49 divided by 3 is 16 with remainder 1. So 1 is the next digit and so far we have _11 as our representation with the _ part still to be filled in (we can't know how many digits it will be, yet). Divide 16 by 4, quotient: 4, remainder: 0. Last, divide 4 by 5 to get a remainder of 4 and quotient of 0 (0 means the algorithm is finished). Combining all the remainders, 4011 ends up as the factoradix notation for 99. Longer yes, but with a simpler choice of digits.

We don't need to go through the details, but larger numbers make the opposite tradeoff in factoradix. A 1 with 47 zeros behind it becomes 4z7,h0x,ipf,5gr,0bc,l7l,977,460,068,952,315,551,220 which is only 39 digits long. A 1 with 100 zeros is only 69 digits long, but we need some way to encode digits like "58".

What do some more of these representations look like? First, the Perl function below encapsulates the algorithm above.


sub factoradix {
    my $n = shift;
    my $base = Math::BigInt->new(2);
    my (@digits, $digit);
    while ($n->bcmp(0)) {
        ($n, $digit) = $n->bdiv($base);
        unshift @digits, $digit->bstr();
        $base->binc();
    }
    return [ @digits ];
}

Using this function, here's how the powers of ten start out in factoradix:
For 10⁰, we get 1
For 10¹, we get 120
For 10², we get 4,020
For 10³, we get 121,220
For 10⁴, we get 1,651,220
For 10⁵, we get 23,551,220
For 10⁶, we get 266,251,220
For 10⁷, we get 2,750,051,220
For 10⁸, we get 25,551,151,220
For 10⁹, we get 210,564,451,220
For 10¹⁰, we get 1,7a5,726,651,220
For 10¹⁵, we get 2d,caa,584,234,451,220
For 10²⁰, we get 1k2,13c,54a,a81,881,151,220
For 10²⁵, we get g2i,h8c,8f7,bc3,5b8,250,051,220
For 10³⁰, we get 3,7mf,cdg,584,64c,f8b,c01,182,251,220
For 10³⁵, we get c,4tr,pn8,9ef,g2b,d3f,34b,225,975,551,220
For 10⁴⁰, we get x,tkt,18i,jep,8bh,g9j,f7e,1bb,652,056,651,220
For 10⁶⁴, we get g,lqd,ila,9ii,ju0,a5m,bas,91k,7l5,m66,1ii,4h5,462,7a5,726,651,220

Every power of ten larger than 10⁶⁴ seems to use a digit that we don't have a letter for (and I checked up to 10¹⁴⁰⁰!). Of course, all we need to do is add more symbols, maybe hearts or that thing The Artist Formerly Known as Prince uses...

What do you think is the next factoradix question to investigate?

From the Outbox: a Balanced Diet

2008-03-02T16:11:00.000-08:00

From: Me
Subject: Re: The 20 Worst Foods in America]
Date: March 1, 2008 5:44:56 PM CST
To: xxxxxxx@xxxxx.xxx

On Feb 29, 2008, at 9:48 AM, Xxxxx Xxxxxxx wrote:

> Thought this was interesting.

> Xxxxx

> > 1. The Worst Food in America
> > Outback Steakhouse Aussie Cheese Fries with Ranch Dressing

> >

> > 2,900 calories
> > 182 g fat 240 g carbs

Of course, there's nothing inherently wrong with calories taken out of context of all food one eats. The Outback Steakhouse Aussie Cheese Fries with Ranch Dressing is a perfect complement to some diet, somewhere. For instance, if the only other thing we ate was grasses and roots that we dug up on the hllls, the aussie cheese fries might balance it out nicely.

Clothing's destiny?

2008-02-25T12:29:00.001-08:00

If you ran a shirt through the dryer sufficiently many times, would it eventually turn completely into lint?

The Computer Scientific Method

2008-02-13T17:44:00.000-08:00

I was sent a presentation called How to Have a Bad Career in Research/Academia by David A. Patterson.

The best slide concerns the "Computer Scientific Method;" funny because it's true...

Physics Question: Leaky Inflatable Chair

2008-02-12T14:10:00.000-08:00

At OSCON 2006, some O'Reilly developers and I were lounging in the expansive round upper-level of the Oregon Convention Center. It turns out that the someone had spread around a bunch of inflatable chairs which were molded after an overstuffed cushy easy chair.

Ryan Grimm had claimed a partially-deflated one. As I eyed it, I posed the following question:

Suppose that the air-filled chair had a pinhole leak on the side. Could it deflate faster depending on how you sat on it? In other words, would the air leave faster, slower or at the same rate if you spread your weight out as evenly as possibly in a wide slouch compared to if you stood on one foot and put all your weight on a few square inches?

I posed this to a handful of people, and none of them ever agreed with my answer. Maybe we can put this to rest now. What do you think and why?

Update with Legal Fine Print
All your weight is on the chair. You're not blocking the pinhole. In both scenarios, your weight is the same. The question is about over how wide of a space your weight is distributed.

Updated Example
You could rephrases this problem as something like:
"Will your inflatable mattress retain its pressure longer if you curl up in a cannonball or if you spread out like a pancake?"

Cookie Recipe

2008-02-10T16:16:00.000-08:00

This recipe has served me well for the last 15 years.

3/4 cup butter
1 cup brown sugar
1/2 cup sugar
teaspoon vanilla
2 eggs
3 cups flour
1 teaspoon baking soda
1 teaspoon salt
2 cups chocolate chips

The butter must be softened, but not melted. Melting it was a disastrous mistake I made a number of times.

The line suggesting 1 teaspoon baking soda is a pack of lies. You must use at least 2.5 teaspoons.

Don't overbake. I would tell you how long, but ovens vary so you will have to eyeball it.

2008 Election Correctly Predicted

2007-11-30T10:57:00.000-08:00

Three European scientists have produced a document which correctly states who will win the 2008 US presidential election.

They don't need to give you the document (although they do) because they can give you the MD5 checksum. A checksum, which is a kind of fingerprint for the document, accordingly to the conventional wisdom can only come from that one document. In principle, other documents may exist with the same fingerprint, but are technically infeasible to find. Then, after the election is over, they will make the PDF available and invite you to measure its MD5. If it matches, that proves it has to have been the same one they fingerprinted back in Nov 30, 2007.

The fingerprint analogy goes pretty far. Imagine that they had said,
We know who will win the 2008 presidential election. To prove it, we found someone with his name and fingerprinted him. Here's the fingerprint ....

On the morrow of Election day, the person will visit your house, let you take his fingerprints and show his driver's license to prove his name is that of the person who won.

The catch, of course if that MD5s aren't really as good as fingerprints, despite widespread belief, even among experts. Marc Stevens, Arjen Lenstra and Weger have simply found an appealing way to exploit duplicatability of MD5s, constructing 12 documents with the same MD5, each with the name of different candidate (and some non-candidates). In our metaphor, this is coming up with 12 different people named after the candidates and then bioengineering them to have the same fingerprints. No matter who wins in 2008, they are "correct," simply by choosing which one to reveal.

Excellent work!

My best way to get out of bed in the morning

2007-11-25T22:20:00.000-08:00

Something I wrote in a chat log

12:17:34 AM: I was wondering once what would be the best possible way to wake up
12:17:57 AM: but which would force you to get up
12:17:58 AM: and I decided that if I was the richest person alive
12:18:11 AM: I would have a bed built so that when the alarm clock went off
12:18:34 AM: it would unhinge in the middle so the two halves would swing down and gently drop me
12:18:36 AM: into a hot tub
12:19:00 AM: which would be a great way to start the day, and there's no going back to sleep

Women's Rights are Human Rights

2007-11-13T16:56:00.000-08:00

Maybe one day this will be reality, when women have the same definition of decency as men do.

The next step is naturally for social acceptability, then dare we entertain it, for it to be just as acceptable for men to wear bras and dresses. MLK had a dream too!

Starbucks' 87,000 options

2007-11-13T09:39:00.001-08:00

I picked up a nutrition facts pamphlet at Starbucks that promises that with all the choices of creamer, syrup, spices, etc. "87,000" different beverages are possible.

Here's a computer science/reverse engineering problem. Find the number that is most likely to be the exact value of the number of options as Starbucks calculates it. Some things you might assume:

It's likely to be within 500 of 87,000.
It's factorization makes it look the most like the product of 2's, 3's or other small numbers reflecting many choices. For instance, it's unlikely to be 87011, which is prime. However, 87480 is a candidate since 87480 = 2 * 2 * 2 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 5. It's possible that there are 3 ingredients which you can have or not, explaining the 3 twos. Maybe there are 3 sizes, 2 types of toppings (and the option to have nothing), 2 kinds of creamer (or none), something else with 5 options, and finally 27 (3*3*3) different beverages. I don't know if this is how the Starbucks menu works and it doesn't matter: 87480 is definitely more likely than 87011.

I'd like to hear of good algorithms to solve this problem, and if anyone who reads this knows more about Starbucks, that's a fine way to answer too.

If we can't figure it out, let's not sweat it. I'm pretty sure that 87,000 is way too low anyway...

Woods

2007-09-29T16:28:00.000-07:00

This is the forest primeval.