bossylobster

Tuesday, August 23, 2011

Conway's Topograph Part 1

This is the first in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.

Definition: A binary quadratic form $f$ is an equation of the form:

\[f(x, y) = A x^2 + H x y + B y^2.\]

That is, a function of two variables which is homogeneous of degree two. The coefficients $A$, $H$, and $B$ and variables $x$ and $y$ are often real numbers, rational numbers or integers. $\Box$

When we require the coefficients $A$, $H$, and $B$ as well as the variables $x, y$ to be integers, we get an integer--valued form. In his Disquisitiones Arithmeticae, Gauss asked (and largely answered) the fundamental question: what integer values can each form take? For example, you may have seen the form

\[f(x, y) = x^2 + y^2,\]

where it was determined that the only primes (Gaussian primes) occuring were $2$ and those odd primes congruent to 1 modulo 4.

As each form $f$ is homogenous degree two, $f(\lambda x, \lambda y) = \lambda^2 f(x, y)$. As a result, if we can understand the values of $f$ for pairs $(x, y)$ which don't share any factors, we can understand the entire set of values that $f$ takes. Also, letting $\lambda = -1$, there is no change in the value of $f$ since $\lambda^2 = 1$, hence it suffices to think of $v = (x, y)$ as $\pm v$, i.e. $\left\{(x, y), (-x, -y)\right\}$.

For integers $x$ and $y$, any point $(x, y)$ can be expressed as an integral linear combination of the vectors $e_1 = (1, 0)$ and $e_2 = (0, 1)$. So if we like, we can express all relevant inputs for $f$ in terms of two vectors. However, instead considering $e_2 = (1, 1)$, we have

\[(x - y) \cdot e_1 + y \cdot e_2 = (x, y)\]

and realize a different pair $e_1, e_2$ which again yield all possible integer valued vectors as integral linear combinations.

Definition: A strict base is an ordered pair $(e_1, e_2)$ whose integral linear combinations are exactly all vectors with integer coordinates. A lax base is a set $\left\{\pm e_1, \pm e_2\right\}$ obtained from a strict base. $\Box$

Definition: A strict superbase is an ordered triple $(e_1, e_2, e_3)$, for which $e_1 + e_2 + e_3 = (0, 0)$ and $(e_1, e_2)$ is a strict base (i.e., with strict vectors), and a lax superbase is a set $\langle\pm e_1, \pm e_2, \pm e_3\rangle$ where $(e_1, e_2, e_3)$ is a strict superbase. $\Box$

For our (and Conway's) purposes, it is useful to consider the lax notions and leave the strict notions as an afterthought since a binary quadratic form is unchanged given a sign change. From here forward, for a vector $v$, we use the notation $v$ interchangeably with $\pm v$ and when referring to a base/superbase, we are referring to the lax equivalent of these notions.

Follow along to Part 2.

Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.

Wednesday, August 17, 2011

The Lesson V8 Can Teach Python and Other Dynamic Languages

Being unable to completely give up math for computers, I am naturally drawn to Project Euler and as a result solved a ridiculous number of the problems posted there while learning Python. A few months ago (March 13), after reading Secrets of a Javascript Ninja, I decided to begin converting my solutions to Javascript. A month and a half later I came back to it, and then finally two months after that, I began to take it seriously.

After making this decision, I noticed the prime Sieve of Eratosthenes was mighty fast when I ran it in Chrome, maybe even faster than my beloved Python. I tabled the thought for a little, but never really forgot it. So a few weeks ago (early August 2011), I finally got a working install of node running on my machine and was able to make more of this thought. (I say finally installed because on two previous tries I gave up because of conflicts with my version of gcc, coupled with the fact that I had no good reason to use node.)

When I originally did the conversion, I had skipped problem 8, because my implementation required pulling in the problem data as text from a file. While hanging out with Boris and Eric from on the Chrome Developer Relations team, I decided to give it another go on node (xhr requests not allowed) and found it to be quite simple with readFileSync in the node native fs module. After witnessing this, over this weekend, I decided to harness the power of V8 -- the Javascript engine that powers Chrome and node -- and run all my scripts locally with node. So over a two day period, I hack-hack-hacked my way into converting the Python solutions for problems 11 through 50 (the remaining unconverted) into their Javascript equivalents, while also converting a good portion of my hefty functions module.

Once this was done, I had also found I could replace most of the nice parts about Python with my own equivalent. For example, I was able to replace functionality I needed from the Python set datatype with

function uniq(arr) {
  var result = {};
  for (var i = 0, val; val = arr[i]; i++) {
    result[val] = true;
  }

  return Object.keys(result);
};

and I was able to replace the (amazingly) useful Python handling of long integers with a non-native node package called bigint that uses libgmp among other usings. Of course, for Python's secret sauce -- the list comprehension -- I was able to substitute enough filter, reduce and map statements to almost make it seem like I had never left Pythonland. After doing all this, I also ended up writing my own operator.js to replace the wonderful Python native module operator, and my own timer.js to stand in for the Python native module time.

Finally, I had working code and could do a side by side comparison of V8 and the Python interpreter. Update: I added a column for PyPy, a just in time implementation of Python. Here is what I found (averaging the runtime over 10 separate calls to each function, the results are):

Problem	Answer	Python	Javascript	Ratio (PY/JS)	PyPy
1*	233168	1804ms	1215ms	1.48	385ms
2*	4613732	247ms	102ms	2.42	85ms
3*	6857	4725ms	1508ms	3.13	582ms
4	906609	8708ms	149ms	58.44	282ms
5*	232792560	136ms	186ms	0.73	114ms
6*	25164150	10ms	4ms	2.50	6ms
7	104743	656ms	12ms	54.67	11ms
8*	40824	18045ms	5014ms	3.60	7042ms
9	31875000	610ms	3ms	203.33	8ms
10	142913828922	6628ms	167ms	39.69	116ms
11	70600674	49ms	2ms	24.50	11ms
12	76576500	5127ms	203ms	25.26	100ms
13*	5537376230	1795ms	10710ms	0.17	1423ms
14	837799	5572ms	1712ms	3.25	362ms
15*	137846528820	54ms	18ms	3.00	55ms
16*	1366	1844ms	265ms	6.96	462ms
17	21124	87ms	4ms	21.75	7ms
18*	1074	2291ms	1790ms	1.28	1090ms
19*	171	2254ms	336ms	6.71	342ms
20*	648	1061ms	9154ms	0.12	374ms
21	31626	18910ms	1038ms	18.22	728ms
22	871198282	188ms	7ms	26.86	8ms
23	4179871	83318ms	1120ms	74.39	1295ms
24*	2783915460	206ms	210ms	0.98	139ms
25	4782	5865ms	35ms	167.57	232ms
26	983	28ms	18ms	1.56	4ms
27	-59231	645738ms	22536ms	28.65	28288ms
28*	669171001	8509ms	1037ms	8.21	981ms
29	9183	184ms	96ms	1.92	20ms
30	443839	52167ms	1037ms	50.31	877ms
31	73682	9606ms	257ms	37.38	154ms
32	45228	206888ms	12096ms	17.10	4266ms
33	100	300ms	6ms	50.00	15ms
34	40730	7462ms	2447ms	3.05	247ms
35	55	8617ms	848ms	10.16	242ms
36	872187	189788ms	2183ms	86.94	3532ms
37	748317	2389022ms	71845ms	33.25	61551ms
38	932718654	506ms	10ms	50.60	12ms
39	840	178ms	6ms	29.67	12ms
40*	210	326ms	202ms	1.61	119ms
41	7652413	2627ms	133ms	19.75	65ms
42	162	65ms	7ms	9.29	8ms
43	16695334890	38ms	2ms	19.00	2ms
44	5482660	384013ms	27744ms	13.84	6621ms
45*	1533776805	17ms	4ms	4.25	8ms
46	5777	2864ms	202ms	14.18	65ms
47	134043	400967ms	12838ms	31.23	4425ms
48	9110846700	46ms	16ms	2.88	6ms
49	296962999629	115ms	8ms	14.38	13ms
50	997651	3277ms	80ms	40.96	51ms
*These were very quick to run, so the runtimes are the time taken to run 10000 times.

As you'll notice, standard Python gets its butt kicked. I was kind of saddened by this, but in the end, just giddy that our web is faster because of it (90% of my life is digital) and also that we can do scripting faster on the server side (attribute to Boris Smus) because of the node project (thanks Ryan Dahl).

Standard Python is actually slower in 46 of the 50 problems. In 28 of the 46 node is faster by a factor of 10 or greater, in 9 of those 28 by a factor of 50 or greater and in 2 of the 9 by a factor of 100 or greater! The only 4 in which Python was faster were from the n = 10000 sample. In fact, I was able to pinpoint exactly why:

#5 - My own Javascript implementation of gcd is slower than the native (from fractions import gcd) Python library (resulting in a difference of 50 ms over 10000 iterations)
#13 - The node package bigint is slower than the Python native long int (Javascript is slower by a factor of 6)
#20 - The node package bigint is slower than the Python native long int (Javascript is slower by a factor of 8.5)
#24 - Having to perform two slices is slower in Javascript than in Python and there is no good way to just remove one element (resulting in a difference of 4 ms over 10000 iterations; a little bit about that here)

So what, you ask, is that lesson I speak of? Well, Javascript didn't used to be this fast. How did it get that way? The brilliant and inspired people behind V8 rethought the Javascript compile steps and after much work, we now have code that is closer to the metal (attribute to: Eric Bidelman, i.e. closer to machine code) than we had ever had before. The use of just-in-time compilation and other incredible techniques has taken a formerly slow and clunky language (Javascript) which was used well beyond its original intended scope, and turned it into a damn fast dynamic language. Hopefully, this movement will make its way to Python and other dynamic languages and we can all have our code end up this close to the metal.

Update: In response to the comments, I ran the same code on the same machine, but with PyPy in place of Python. This is the direction I hope standard Python goes in and commend the guys pumping out faster and faster just in time implementations over at PyPy. I went through and counted 20 node wins, 29 PyPy wins and 1 tie. (I reserve the right to update the post with more detailed metrics.) While I do commend them, the results don't really belong in this post because PyPy is still an offshoot. (However, as I understand, they both have ties to C, as PyPy uses GCC to compile to bytecode and V8 is written in C++. Feel free to supplement my knowledge in the comments.)

Update: All benchmarking was run on my Mac Pro Desktop with a 3.2 GHz Quad-Core Intel Xeon processor and 4 cores for a total of 12 GB 1066 MHz DDR3 memory. I used Python version 2.6.1, node version 0.4.9, and PyPy version 1.5 (running on top of Python 2.7.1 with GCC 4.0.1).

Friday, July 22, 2011

Woo hoo

It's official, I am a grown up!
http://code.google.com/apis/inapppayments/articles/index.html

Monday, July 18, 2011

Continued fraction expansions of irrational square roots

I had no idea (until this Thursday, July 16) that I had never seen a proof of the fact that the continued fraction expansion of $\sqrt{D}$ is periodic whenever $D$ is not a perfect square. But have no fear, I found out about something called a reduced quadratic irrational and now have a proof. Here we go.

Definition: An irrational root $\alpha$ of a quadratic equation with integer coefficients is called reduced if $\alpha > 1$ and its conjugate $\tilde{\alpha}$ satisfies $-1 < \tilde{\alpha} < 0$. $\Box$

Solutions (since assumed real) of such quadratics can be written as $$\alpha = \frac{\sqrt{D} + P}{Q}$$ where $D, P, Q \in \mathbf{Z}$ and $D, Q > 0$. It is also possible (though not required) to ensure that $Q$ divides $D - P^2$. This is actually a necessary assumption for some of the stuff I do, is mentioned here and generally frustrated the heck out of me, so that. As an example for some enlightenment, notice $$\alpha = \frac{2 + \sqrt{7}}{4}$$ is reduced but $4$ does not divide $7 - 2^2$. However, if we write this as $\frac{8 + \sqrt{112}}{16}$, we have our desired condition.

Definition: We say a reduced quadratic irrational $\alpha$ is associated to $D$ if we can write $$\alpha = \frac{P + \sqrt{D}}{Q}$$ and $Q$ divides $D - P^2$. $\Box$

Lemma 1: Transforming a reduced irrational root $\alpha$ associated to $D$ into its integer part and fractional part via $$\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},$$ the resulting quadratic irrational $\alpha'$ is reduced and associated to $D$ as well. (This is what one does during continued fraction expansion, and as I did with $\sqrt{2}$ during my last post.)

Proof: Letting $$\alpha = \frac{\sqrt{D} + P}{Q}$$ and $X = \lfloor \alpha \rfloor$, we have $$\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.$$

Since $\sqrt{D}$ is irrational, we must have $\frac{1}{\alpha'} > 0$ and since $\frac{1}{\alpha'}$ is the fractional part we know $$0 < \frac{1}{\alpha'} < 1 \Rightarrow \alpha' > 1.$$
Transforming $$\alpha' = \frac{Q}{\sqrt{D} - (QX - P)} \cdot \frac{\sqrt{D} + (QX - P)}{\sqrt{D} + (QX - P)} = \frac{\sqrt{D} + (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)},$$ we have $P' = QX - P$ and $Q' = \frac{1}{Q}\left(D - (QX - P)^2\right)$ and need to show $Q' \in \mathbf{Z}$. But $D - (QX - P)^2 \equiv D - P^2 \bmod{Q}$ and since $\alpha$ is associated to $D$, $Q$ must divide this quantity, hence $Q'$ is an integer.
Since $X = \lfloor\frac{\sqrt{D} + P}{Q}\rfloor$ is an integer and $\alpha$ is irrational, we know $X < \frac{\sqrt{D} + P}{Q}$ hence $P' = QX - P < \sqrt{D}$ forcing $\tilde{\alpha}' < 0$.
Since $\alpha > 1$ we know $X \geq 1 \Leftrightarrow 0 \leq X - 1$. Thus \begin{align*}\tilde{\alpha} = \frac{P - \sqrt{D}}{Q} &< 0 \leq X - 1 \\ \Rightarrow Q &< \sqrt{D} + (QX - P) \\ \Rightarrow Q(\sqrt{D} - (QX - P)) &< D - (QX - P)^2 \\ \Rightarrow -\tilde{\alpha}' = \frac{\sqrt{D} - (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)} &< 1 \end{align*} hence $\tilde{\alpha}' > -1$ and $\alpha'$ is reduced.
Since $Q' = \frac{1}{Q}\left(D - (P')^2\right)$, we know $$D - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}$$ hence $\alpha'$ is associated to $D$.

Thus $\alpha'$ is both reduced and associated to $D$. $\Box$

Lemma 2: There are finitely many reduced quadratic irrationals associated to a fixed $D$.

Proof: As above write an arbitrary reduced irrational as $\alpha = \frac{\sqrt{D} + P}{Q}$. Since $\alpha > 1$ and $\tilde{\alpha} > -1$, we know $\alpha + \tilde{\alpha} = \frac{2P}{Q} > 0$ hence with the assumption $Q > 0$ we have $P > 0$. Since $\tilde{\alpha} < 0$ we also have $P < \sqrt{D}$. Also, since $\alpha > 1$ by assumption we have $Q < P + \sqrt{D} < 2\sqrt{D}$ thus there are finitely many choices for both $P$ and $Q$, forcing finitely many reduced quadratic irrationals associated to a fixed $D$ (this amount is strictly bounded above by $2D$). $\Box$

Claim: The continued fraction expansion of $\sqrt{D}$ is periodic whenever $D$ is not a perfect square.

Proof: We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to $D$ and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.

Write $a_0 = \lfloor \sqrt{D} \rfloor$ and $\sqrt{D} = a_0 + \frac{1}{\alpha_0}$. From here, we will prove

$\alpha_0$ is a reduced quadratic irrational associated to $D$.
By defining $a_{i+1} = \lfloor \alpha_i \rfloor$ and $\alpha_i = a_{i + 1} + \frac{1}{\alpha_{i + 1}}$, $\alpha_{i + 1}$ is also a reduced quadratic irrational associated to $D$ (assuming all $\alpha$ up until $i$ are as well).

Since $\frac{1}{\alpha_0}$ is the fractional part of the irrational $\sqrt{D}$, we have $$0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.$$ By simple algebra, we have $$\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \tilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.$$ Since $a_0$ is the floor, we know $a_0 - \sqrt{D} < 0 \Rightarrow \tilde{\alpha_0} < 0$. Since $D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1$ and $\sqrt{D} > a_0$, we have $$1 < \sqrt{D} + a_0 \Rightarrow \sqrt{D} - a_0 < D - a_0^2 \Rightarrow a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \tilde{\alpha_0} > -1.$$ Thus $\alpha_0$ is a reduced quadratic irrational. Since $P_0 = a_0$ and $Q_0 = D - a_0^2 = D - P_0^2$, $Q_0$ clearly divides $D - P_0^2$ so $\alpha_0$ is associated to $D$ as well.

Following the recurrence defined, since each $\alpha_i$ is a reduced quadratic irrational, each $a_i \geq 1$. Also, by Lemma 1, each $\alpha_{i + 1}$ is reduced and associated to $D$ since $\alpha_0$ is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest $k$ for which $\alpha_k = \alpha_0$. Since $\alpha_{i + 1}$ is determined completely by $\alpha_i$ we will then have $\alpha_{k + j} = \alpha_j$ for all $j > 0$, hence the $\alpha_i$ are periodic. Similarly, as the $a_i$ for $i > 0$ are determined completely by $\alpha_{i - 1}$, the $a_i$ must be periodic as well, forcing the continued fraction expansion $$\sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$$ to be periodic.$\Box$

Update: I posted this on

Sunday, July 10, 2011

Continued Fractions for the Greater Good part 1

OK, maybe not for the greater good, but still fun. This first post will be relatively short and sweet, intended to give an introduction for the posts that will follow.

Before the introduction, some motivation courtesy of Wikipedia:

“...decimal representation has some problems. One problem is that many rational numbers lack finite representations in this system. For example, the number $\frac{1}{3}$ is represented by the infinite sequence $(0, 3, 3, 3, 3, \ldots )$. Another problem is that the constant $10$ is an essentially arbitrary choice, and one which biases the resulting representation toward numbers that have some relation to the integer $10$. For example, $\frac{137}{1600}$ has a finite decimal representation, while $\frac{1}{3}$ does not, not because $\frac{137}{1600}$ is simpler than $\frac{1}{3}$, but because $1600$ happens to divide a power of $10$ ($10^6 = 1600 \times 625$). Continued fraction notation is a representation of the real numbers that avoids both these problems. Let us consider how we might describe a number like $\frac{415}{93}$, which is around $4.4624$. This is approximately $4$. Actually it is a little bit more than $4$, about $4 + \frac{1}{2}$. But the $2$ in the denominator is not correct; the correct denominator is a little bit more than $2$ about $2 + \frac{1}{6}$, so $\frac{415}{93}$ is approximately $$4 + \cfrac{1}{2+\cfrac{1}{6}}.$$ But the $6$ in the denominator is not correct; the correct denominator is a little bit more than $6$, actually $6+\frac{1}{7}$. So $\frac{415}{93}$ is actually $$4 + \cfrac{1}{2+\cfrac{1}{6 + \cfrac{1}{7}}}.$$ This is exact...”

With this in mind, one can define an infinite continued fraction to be $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}.$$ With the denominators $a_0, a_1, a_2, \ldots$, we can define a recurrence for the finite approximations (convergents) of this value. For example, the zeroth is $a_0$ and the first is $a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1}$.

The other motivation (the one I actually learned first in real life) for continued fractions comes from $\sqrt{2}$ being represented by an infinite continued fraction. (Instead of saying a probability of $0.01876$, people would rather say a $1$ in $53$ chance.) So we try to write $\sqrt{2} = 1.41421356\ldots$ as $1 + \frac{1}{2.414}$. But, instead, notice that $$\sqrt{2} = 1 + (\sqrt{2} - 1) = 1 + \frac{1}{\sqrt{2} + 1}.$$ Plugging this into itself, we have $$\sqrt{2} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}}}$$ and notice it can be represented by $(1; 2, 2, 2, \ldots)$.

Define the $n$th convergent to be $\frac{h_n}{k_n}$, so above we have $h_0 = a_0, k_0 = 1$ and $h_1 = a_0 a_1 + 1, k_0 = a_1$.

Claim: $h_n$ and $k_n$ satisfy \begin{align*}h_n &= a_n h_{n - 1} + h_{n - 2} \\ k_n &= a_n k_{n - 1} + k_{n - 2} \end{align*} along with $h_{-1} = 1, h_{-2} = 0$ and $k_{-1} = 0, k_{-2} = 1$.

Proof: The fraction $\frac{h_n}{k_n}$ is converted into $\frac{h_{n + 1}}{k_{n + 1}}$ simply by changing $a_n$ to $a_n + \frac{1}{a_{n + 1}}$ in the final denominator. Since $$\frac{h_n}{k_n} = \frac{a_n h_{n - 1} + h_{n - 2}}{a_n k_{n - 1} + k_{n - 2}}$$ we similarly have \begin{align*} \frac{h_{n + 1}}{k_{n + 1}} &= \frac{\left(a_n + \frac{1}{a_{n + 1}}\right) h_{n - 1} + h_{n - 2}}{\left(a_n + \frac{1}{a_{n + 1}}\right) k_{n - 1} + k_{n - 2}} \\ &= \frac{a_{n + 1}(a_n h_{n - 1} + h_{n - 2}) + h_{n - 1}}{a_{n + 1}(a_n k_{n - 1} + k_{n - 2}) + k_{n - 1}} \\ &= \frac{a_{n + 1} h_n + h_{n - 1}}{a_{n + 1} k_n + k_{n - 1}}\end{align*}
Thus $h_{n + 1}$ and $k_{n + 1}$ satisfy the same recurrence.

It remains to check the initial conditions work, but note \begin{align*}h_0 &= a_0 h_{-1} + h_{-2} = a_0 \cdot 1 + 0 = a_0 \\ k_0 &= a_0 k_{-1} + k_{-2} = a_0 \cdot 0 + 1 = 1\end{align*} and \begin{align*}h_1 &= a_1 h_{0} + h_{-1} = a_0 a_1 + 1 \\ k_1 &= a_1 k_{0} + k_{-1} = a_1 \cdot 1 + 0 = a_1\end{align*} as we checked above. $\Box$

Check out my next post, where I actually accomplish something with fractions (or at least prepare to accomplish something).

Sunday, July 3, 2011

Verifying 1and1 Site Ownership with Google Apps

Hello freens. I purchased bossylobster.com from 1&1 recently with the intent of hosting it on Google App Engine. I soon found out how delightful this process is. I made a 0.1 version for my site at bossylobster.appspot.com and decided to launch by clicking "Add Domain" in the "Application Settings".

After clicking this I was greeted with a note: "You must sign up for Google Apps to register this domain or prove that you already own it." Great, so now I had to sign up for Google Apps. (As a side note, at the time this seemed an unnecessary, annoying wrinkle to add my App, but I now realize the integration with GMail, Calendar, Docs, etc. is fantastic.)

So here is my ish: prove that you already own it.

Yesterday morning, I spent several hours trying to verify ownership of bossylobster.com (which I had purchased a week prior). While I realize the DNS propagation process takes some time, I didn't want to try one method, wait 24 hours and then realize at that point it hadn't worked.

So, Google Apps gives four options on how to verify:

Create a TXT record
Upload an HTML file to a specific path on your site
Add a <meta> tag to your home page
Verify using your Google Analytics tracking code

Well, since I hadn't set my website up, the last three options were off limits to me (or so I thought). I had a bare minimum package from 1&1, so hosting was pretty much off limits. Apparently I picked one of the inept domain hosts because they don't support creation of a CNAME TXT record!! A quick Google search reveals "Yes, we do understand what an SPF record is. Unfortunately we do not support in on our hosting plans. We apologize for any inconvenience."

So here I am back to square one, just trying to prove I own something, an inherently basic task made incredibly frustrating. Hopefully I can help people avoid some frustration with the following instructions.

1. Open terminal and change into the directory with code for bossylobster (your site).
2. Create a Django project in that directory via the command
sudo django-admin.py startproject bossylobster_django.
(If you don't have Django or you are using Windows, read these install instructions, but DON'T SET UP A DATABASE, not necessary here. For a more detailed tutorial see this page. Also note, startproject is the function name in the django-admin module and bossylobster_django can be replaced with your project name.)
4. Change the file bossylobster_django/urls.py to:

from django.conf.urls.defaults import patterns
from django.conf.urls.defaults import url

urlpatterns = patterns('',
  url(r'^$', 'bossylobster_django.views.index', name='home'),
)

5. Change the file bossylobster_django/views.py to:

from django.http import HttpResponse

def index(request):
  content = '\n'.join(['<html>',
    '  <head>',
    '    <meta name="google-site-verification" content="XXXX" />',
    '  </head>',
    '  <body>',
    '    Hello world!',
    '  </body>',
    ' </html>'])
  return HttpResponse(content)

where XXXX should be replaced by the content value provided by Google.
6a. Determine your internal IP address for use in step 7
6b. Determine your router's (external) IP address for use in step 8
7. Set up a port forwarding rule in your router for port 80 (websites) with the IP address you found in 6a
8. (After logging in to 1&1) change IP for bossylobster.com to point to your router (from 6b)
9. From the bossylobster_django directory (or whatever you called it), run the server via
sudo python manage.py runserver 192.168.XX.YY:80
where 192.168.XX.YY is the IP you found in 6b.
10. Check to see if your change has propagated to DNS servers worldwide (wait until it has)
11. Upon propagation, login to Google Apps and verify via the meta tag

Friday, July 1, 2011

Getting Divvy-like functionality on Linux

I love my Divvy, as I'm sure many do, but it's not available for Linux. (I completely understand why it isn't, though the fact that they make Divvy a free demo with full functionality brings into question how much they are trying to monetize it.) Anyhow, not wanting to give away my left hand for a personal computer, I run Ubuntu on my home machine (but OS X at work, kind of funny).

In reality, all I really need from Divvy is the ability to do three things without the mouse that I normally couldn't do.
1. Maximize a window
2a. Make the window take the entire left half of the screen
2b. Make the window take the entire right half of the screen
That's all, I'm not asking for much.

=====================================================================
=====================================================================
=====================================================================
As a brief side not for those who don't know, with Divvy, I start with a window

and then call up Divvy with (a command I set globally) Ctrl-Z

and then once Divvy is up, I just hit the letter L (another command I made) and voila

my window is on the full left half of the screen.

=====================================================================

=====================================================================

So, every other weekend for the last five months, I have tried to find a Divvy-like solution for Linux. I picked up and discarded Bluetile and PyWO along the way, the former because it is way too heavy a solution and the latter because it required the keypad, which my laptop keyboard does not have (of course I could've enabled NumLock to simulate the keypad, but that is too big a PITA).

Finally, last night I came to a solution that I want to share (in case anyone has gone through the pain I have). That solution is Compiz and here is how I did it:
1. Install Compiz from the command line via sudo apt-get install compizconfig-settings-manager
2. Install the extra plugins via sudo apt-get install compiz-fusion-plugins-extra
3. Open Compiz (ccsm from the command line) or

4. Go into the Window Management subsection

5. Enter Grid and set the "Put Left" and "Put Right" bindings to Alt-F8 and Alt-F9, while disabling everything else (my choice, doesn't have to be yours, if you have a Keypad on your keyboard and NumLock is not going to interfere with the letter 'm', then go for it)

(Also, another side note, if you are having trouble figuring out how to change the binding, just click the first box, the ones that say Disabled or whatever the current binding is and then "Grab Key Combination"

to change the binding to your hearts content.)

7. For maximize go to General Options

8. In the Key Bindings tab, make sure "Toggle Window Maximized" is set to it's default value of Alt-F10

So with that, I my conditions satisfied: 1. via Alt-F10, 2a. via Alt-F8 and 2b. via Alt-F9. My search is over (for now...unless I make DivvyBuntu...)

(A little bit more about what you can do with Compiz:

Linux nerds watch Las Vegas, told you so Brent!)