eternal ramblings of an empty mind

## Month: October, 2012

### Four-Fifty-One

With the Kindle/Kindle app(s), I have absurd quantities of books at my fingertips. And, since my wiki doesn’t work without regular restarts of the server (I’ll nail down that problem eventually, I’m sure), I’m putting the list here. The ones in italics I already own, and are therefore (mostly) at the top of my list. Those struck through I’ve finished. The precise order is also very much subject to change, but I wanted to get it down so I don’t forget any of these books.

This is not to discount anything by Terry Pratchett: I would simply rather have all Discworld books in dead tree form, to make lending their awesomeness to others a much simpler prospect.

I have an asterisk by Warbreaker. I “own” it, in that I have downloaded the PDF and sent it to my Kindle. However, the PDF text is tiny. I made a half-hearted attempt to convert the HTML to a Kindle ebook, and realized that, with 58 chapters, formatting would be a bear. So I gave up. I’d rather support an incredible author and get the book that someone else has done the work. But! I have a bunch of books to read first.

• Glamour in Glass (Mary Robinette Kowal)
• Shades of Milk and Honey (Mary Robinette Kowal)
• The Hollow City (Dan Wells)
• Pump Six and Other Stories (Paolo Bacigalupi)
• Magic for Beginners (Kelly Link)
• Old Man’s War (John Scalzi)
• Pirate Cinema (Cory Doctorow)
• The Secret World Chronicles: Invasion (Mercedes Lackey)
• Zoo City (Lauren Beukes)
• Signal to Noise (Neil Gaiman & Dave McKean)
• Save Yourself, Mammal! (Zach Weiner)
• The Most Dangerous Game (Zach Weiner)
• Attack of the Bacon Robots (Jerry Holkins & Mike Krahulik)
• Epic Legends of the Magic Sword Kings (Jerry Holkins & Mike Krahulik)
• xkcd: volume 0 (Randall Munroe)
• Warbreaker (Brandon Sanderson)*
• Space Eldritch (Howard Tayler &c.)
• Gone Girl (Gillian Flynn)
• Sharp Objects (Gillian Flynn)
• Dark Places (Gillian Flynn)
• Elantris (Brandon Sanderson)
• Elantris: The Emperor’s Soul (Brandon Sanderson)
• Mistborn: The Final Empire (Brandon Sanderson)
• Mistborn: The Well of Ascension (Brandon Sanderson)
• Mistborn: The Hero of Ages (Brandon Sanderson)
• Mistborn: The Alloy of Law (Brandon Sanderson)
• Alcatraz Versus the Evil Librarians (Brandon Sanderson)
• Alcatraz Versus the Scrivener’s Bones (Brandon Sanderson)
• Alcatraz Versus the Knights of Crystallia (Brandon Sanderson)
• Alcatraz Versus the Shattered Lens (Brandon Sanderson)
• I Am Not a Serial Killer (Dan Wells)
• Mr. Monster (Dan Wells)
• I Don’t Want to Kill You (Dan Wells)
• Partials (Dan Wells)
• Fragments (Dan Wells)
• A Night of Blacker Darkness (Dan Wells)
• Ringworld (Larry Niven)
• The Ringworld Engineers (Larry Niven)
• The Ringworld Throne (Larry Niven)
• Ringworld’s Children (Larry Niven)
• Sundiver (David Brin)
• Startide Rising (David Brin)
• The Uplift War (David Brin)
• Brightness Reef (David Brin)
• Infinity’s Shore (David Brin)
• Heaven’s Reach (David Brin)
• Prelude to Foundation (Isaac Asimov)
• Forward the Foundation (Isaac Asimov)
• Foundation (Isaac Asimov)
• Foundation and Empire (Isaac Asimov)
• Second Foundation (Isaac Asimov)
• Foundation’s Edge (Isaac Asimov)
• Foundation and Earth (Isaac Asimov)
• Foundation’s Triumph (David Brin)
• I, Robot (Isaac Asimov)
• The Rest of the Robots (Isaac Asimov)
• The Complete Robot (Isaac Asimov)
• Robot Dreams (Isaac Asimov)
• Robot Visions (Isaac Asimov)
• The Positronic Man (Isaac Asimov)
• The Caves of Steel (Isaac Asimov)
• The Naked Sun (Isaac Asimov)
• The Robots of Dawn (Isaac Asimov)
• Robots and Empire (Isaac Asimov)
• Caliban (Roger MacBride Allen)
• Inferno (Roger MacBride Allen)
• Utopia (Roger MacBride Allen)
• The Stars, Like Dust (Isaac Asimov)
• The Currents of Space (Isaac Asimov)
• Pebble in the Sky (Isaac Asimov)
• Existence (David Brin)
• Redshirts: A Novel with Three Codas (John Scalzi)
• Player Piano (Kurt Vonnegut)
• The Sirens of Titan (Kurt Vonnegut)
• Mother Night (Kurt Vonnegut)
• God Bless You, Mr. Rosewater, or Pearls Before Swine (Kurt Vonnegut)
• Slapstick, or Lonesome No More! (Kurt Vonnegut)
• Jailbird (Kurt Vonnegut)
• Galápagos: A Novel (Kurt Vonnegut)
• Bluebeard, the Autobiography of Rabo Karabekian (1916-1988) (Kurt Vonnegut)
• Hocus Pocus (Kurt Vonnegut)
• Timequake (Kurt Vonnegut)
• VALIS (Philip K. Dick)
• The Divine Invasion (Philip K. Dick)
• The Transmigration of Timothy Archer (Philip K. Dick)
• Solar Lottery (Philip K. Dick)
• The Cosmic Puppets (Philip K. Dick)
• The World Jones Made (Philip K. Dick)
• Eye In The Sky (Philip K. Dick)
• The Man Who Japed (Philip K. Dick)
• Time Out of Joint (Philip K. Dick)
• Confessions of a Crap Artist (Philip K. Dick)
• The Man in the High Castle (Philip K. Dick)
• We Can Build You (Philip K. Dick)
• Martian Time Slip (Philip K. Dick)
• Dr. Bloodmoney (Philip K. Dick)
• The Simulacra (Philip K. Dick)
• The Three Stigmata of Palmer Eldritch (Philip K. Dick)
• The Zap Gun (Philip K. Dick)
• Now Wait For Last Year (Philip K. Dick)
• Counter-Clock World (Philip K. Dick)
• Ubik (Philip K. Dick)
• Galactic Pot-Healer (Philip K. Dick)
• A Maze of Death (Philip K. Dick)
• Our Friends from Frolix 8 (Philip K. Dick)
• Flow My Tears, the Policeman Said (Philip K. Dick)
• Radio Free Albemuth (Philip K. Dick)
• The Divine Invasion (Philip K. Dick)
• Catch-22 (Joseph Heller)
• The Catcher in the Rye (J.D. Salinger)
• Harry Potter and the Philosopher’s Stone (J.K. Rowling)
• Harry Potter and the Chamber of Secrets (J.K. Rowling)
• Harry Potter and the Prisoner of Azkaban (J.K. Rowling)
• Harry Potter and the Goblet of Fire (J.K. Rowling)
• Harry Potter and the Order of the Phoenix (J.K. Rowling)
• Harry Potter and the Half-Blood Prince (J.K. Rowling)
• Harry Potter and the Deathly Hallows (J.K. Rowling)
• Tears in Rain (Rosa Montero)
• Consider Phlebas (Iain M. Banks)
• The Player of Games (Iain M. Banks)
• Use of Weapons (Iain M. Banks)
• Excession (Iain M. Banks)
• Inversions (Iain M. Banks)
• Look to Windward (Iain M. Banks)
• Matter (Iain M. Banks)
• Surface Detail (Iain M. Banks)
• The Hydrogen Sonata (Iain M. Banks)

I know there are books missing, but my website is now totally MIA.

### Good Times

The BBC has done it again. Sherlock is the best modern day Sherlock Holmes story, Benedict Cumberbatch the best Holmes since Jeremy Brett. Affectations, mannerisms, they’re “spot on.” I would very much suspect that the greatest consulting detective of all time would do much the same as this one, given today’s technology. I’ve only seen “A Study In Pink” and “The Blind Banker” so far, and while they’ve done the sensational stories first, I hope they delve deeper into development of the characters as the series progresses. It’s been too long since I’ve read the books, but I recognized so much of these episodes, and they remind me of “A Study In Scarlet” (obviously), “The Sign of the Four”, and “The Five Orange Pips” along with a hint of “The Adventure of the Dancing Men”. Had her name been Mary Morstan…but perhaps she’ll show up later.

The discrete Fourier transform. Simple enough, sure:

$\mathcal{F}_n=\sum_{k=0}^{N-1}{f_ke^{-2\pi ink/N}}$

I have no problems with this. Or the conversion to a matrix formula:

$\mathcal{F}_n=\begin{bmatrix}f_0 & f_1 & \cdots & f_{N-1}\end{bmatrix}\begin{bmatrix}W^{(0)(0)} & W^{(1)(0)} & \cdots & W^{(N-1)(0)} \\ W^{(0)(1)} & W^{(1)(1)} & \cdots & W^{(N-1)(1)} \\ \vdots & \vdots & \ddots & \vdots \\ W^{(0)(0)} & W^{(1)(N-1)} & \cdots & W^{(N-1)(N-1)}\end{bmatrix}$

where $W=e^{-2\pi in/N}$ (so $W^N=1$, these are roots of unity or de Moivre numbers).

Eventually I found the Danielson-Lanczos lemma, which gives

$\mathcal{F}_n=\sum_{k=0}^{N-1}{f_ke^{-2\pi ink/N}}$

$=\sum_{k=0}^{N/2-1}{e^{-2\pi ikn/(N/2)}f_{2k}}+W^n\sum{k=0}^{N/2-1}{e^{-2\pi ikn/(N/2)}f_{2k+1}}$

$=\mathcal{F}_n^e+W^n\mathcal{F}_n^o$

This is all fine and good. Then it comes to working the FFT, using the Danielson-Lanczos lemma and the Cooley-Tukey algorithm, I’m suddenly stumped. Not the mechanics, but the programming bit. I know I’ve done this successfully before, certainly in college and at least once since then—I had a Python script that used this, first to compute DFTs, then to multiply numbers. Obviously unnecessary with Python supporting arbitrary precision arithmetic built in, but the purpose was (and is) to bolster my own understanding of one of the principles behind APM.

So, University at Buffalo to the rescue. Found some C++ code that gave me what I needed. So here’s (hopefully) a more-or-less plain English version of the method (with an example):

Given a vector (we’ll start small, a size of 8) $f=\begin{bmatrix}7 & 3 & 9 & 1 & 3 & 7 & 3 & 5\end{bmatrix}$.

If the number of elements in the vector is even, split the odd and even parts of the vector into separate vectors (so I cheated and chose a nice number. But the method doesn’t help if the above isn’t true). We’ll call those $f_o$ and $f_e$, respectively:

$f_o=\begin{bmatrix}3 & 1 & 7 & 5\end{bmatrix}$

$f_e=\begin{bmatrix}7 & 9 & 3 & 3\end{bmatrix}$

These are still divisible by two, so repeat:

$f_{oo}=\begin{bmatrix}1 & 5\end{bmatrix}$

$f_{oe}=\begin{bmatrix}3 & 7\end{bmatrix}$

$f_{eo}=\begin{bmatrix}9 & 3\end{bmatrix}$

$f_{ee}=\begin{bmatrix}7 & 3\end{bmatrix}$

Still even!

$f_{ooo}=\begin{bmatrix}5\end{bmatrix}$

$f_{ooe}=\begin{bmatrix}1\end{bmatrix}$

$f_{oeo}=\begin{bmatrix}7\end{bmatrix}$

$f_{oee}=\begin{bmatrix}3\end{bmatrix}$

$f_{eoo}=\begin{bmatrix}3\end{bmatrix}$

$f_{eoe}=\begin{bmatrix}9\end{bmatrix}$

$f_{eeo}=\begin{bmatrix}3\end{bmatrix}$

$f_{eee}=\begin{bmatrix}7\end{bmatrix}$

Now the size of these vectors is odd, so the only choice is to do a regular discrete transform. But this turns out to be nice and simple. Using superscripts to denote which of the above vectors I’m refering to, since

$\mathcal{F}^{ooo}=\sum_{k=0}^{N-1}{f_ke^{-2\pi ink/N}}$

we can plug in each of the above into this formula:

$\mathcal{F}^{ooo}=\sum_{k=0}^{0}{f_0e^{-2\pi i\times 0 \times k/1}}$

which nicely reduces to

$\mathcal{F}^{ooo}=f_0$

But this is only the discrete transform of the one-element vector—these need to be recombined to get the DFT of the entire thing.

So if you reduce the vectors to size 1, the DFT of that is trivial. Then we need to combine them. So let’s start that combination one level higher, with the two-element vectors.

$f_{oo}=\begin{bmatrix}1 & 5\end{bmatrix}$

From the Danielson-Lanczos lemma,

$\mathcal{F}_n^{oo}=\mathcal{F}_{n\mod(N/2)}^{ooe}+W^n\mathcal{F}_{n\mod(N/2)}^{ooo}$

Therefore,

$\mathcal{F}_0^{oo}=\mathcal{F}_0^{ooe}+W^0\mathcal{F}_0^{ooo}$

$\mathcal{F}_1^{oo}=\mathcal{F}_0^{ooe}+W^1\mathcal{F}_0^{ooo}$

In this case, $W=e^{-2\pi i/2}=e^{-\pi i}=-1$, so

$\mathcal{F}^{oo}=\begin{bmatrix}1+5 & 1-5\end{bmatrix}=\begin{bmatrix}6 & -4\end{bmatrix}$

So for a two-element vector, $\mathcal{F}=\begin{bmatrix}\mathcal{F}^{e}+\mathcal{F}^{o} & \mathcal{F}^{e}-\mathcal{F}^{o}\end{bmatrix}$

“Solving” the others in a similar manner, we get

$\mathcal{F}^{oo}=\begin{bmatrix}6 & -4\end{bmatrix}$

$\mathcal{F}^{oe}=\begin{bmatrix}10 & -4\end{bmatrix}$

$\mathcal{F}^{eo}=\begin{bmatrix}12 & 6\end{bmatrix}$

$\mathcal{F}^{ee}=\begin{bmatrix}10 & 4\end{bmatrix}$

Of course, each step gets a bit more difficult. Thanks to the DLL, we know

$\mathcal{F}_n^{o}=\mathcal{F}_{n\mod(N/2)}^{oe}+W^n\mathcal{F}_{n\mod(N/2)}^{oo}$

so let’s take it one step at a time.

First, $W=e^{-2\pi i/4}=-i$

So

$\mathcal{F}_0^{o}=\mathcal{F}_0^{oe}+W^0\mathcal{F}_0^{oo}$

$=10+6=16$

$\mathcal{F}_1^{o}=\mathcal{F}_1^{oe}+W^1\mathcal{F}_1^{oo}$

$=-4+-i\times -4=-4+4i$

$\mathcal{F}_2^{o}=\mathcal{F}_0^{oe}+W^2\mathcal{F}_0^{oo}$

$=10+-1\times 6=4$

$\mathcal{F}_3^{o}=\mathcal{F}_1^{oe}+W^3\mathcal{F}_1^{oo}$

$=-4+i\times -4=-4-4i$

Therefore,

$\mathcal{F}^{o}=\begin{bmatrix}16 & -4+4i & 4 & -4-4i\end{bmatrix}$

Do the same thing to find $\mathcal{F}^{e}$:

$\mathcal{F}^{e}=\begin{bmatrix}22 & 4-6i & -2 & 4+6i\end{bmatrix}$

Putting it all together,

$W=e^{-2\pi i/8}={{1}\over{\sqrt{2}}}(1-i)$

$\mathcal{F}_n=\mathcal{F}_{n\mod(N/4)}^{e}+W^n\mathcal{F}_{n\mod(N/4)}^{o}$

$\mathcal{F}_0=\mathcal{F}_0^e+W^0\mathcal{F}_0^o$

$=22+1\times 16=38$

$\mathcal{F}_1=\mathcal{F}_1^e+W^1\mathcal{F}_1^o$

$=(-4+4i)+{{1}\over{\sqrt{2}}}(1-i)(4-6i)=(-4-\sqrt{2})+(4-5\sqrt{2})i$

$\mathcal{F}_2=\mathcal{F}_2^e+W^2\mathcal{F}_2^o$

$=-2+-i\times4=-2-4i$

$\mathcal{F}_3=\mathcal{F}_3^e+W^3\mathcal{F}_3^o$

$=(-4-4i)+{{1}\over{\sqrt{2}}}(-1-i)(4+6i)=(-4+\sqrt{2})+(-4-5\sqrt{2})i$

$\mathcal{F}_4=\mathcal{F}_0^e+W^4\mathcal{F}_0^o$

$=22+-1\times 16=6$

$\mathcal{F}_5=\mathcal{F}_1^e+W^5\mathcal{F}_1^o$

$=(-4+4i)+{{1}\over{\sqrt{2}}}(-1+i)(4-6i)=(-4+\sqrt{2})+(4+5\sqrt{2})i$

$\mathcal{F}_6=\mathcal{F}_2^e+W^6\mathcal{F}_2^o$

$=-2+i\times4=-2+4i$

$\mathcal{F}_7=\mathcal{F}_3^e+W^7\mathcal{F}_3^o$

$=(-4-4i)+{{1}\over{\sqrt{2}}}(1+i)(4+6i)=(-4-\sqrt{2})+(-4+5\sqrt{2})i$

Thus

$\mathcal{F}=\begin{bmatrix}38 & (-4-\sqrt{2})+(4-5\sqrt{2})i & -2-4i & (-4+\sqrt{2})+(-4-5\sqrt{2})i & 6 & (-4+\sqrt{2})+(4+5\sqrt{2})i & -2+4i & (-4-\sqrt{2})+(-4+5\sqrt{2})i\end{bmatrix}$

Seems like a lot of work, I know. But here’s the thing: normally, using the straight definition, you’d be doing 64 multiplications, 64 sums, and 64 exponentiations ($O(N^2$). We did 24 of each ($O(N\log_2{N})$. And that’s without using a trick: if all $f_k$ are real, $\mathcal{F}_{N-n}=\overline{\mathcal{F}_{n}}$

Yes, it’s still a lot of work, but as the vectors get longer, these savings adds up fast:

Vector Size Naive Operations FFT operations
1 1 0
2 4 2
4 16 8
8 64 24
16 256 64
32 1024 160

And once you put it in a computer program (like the following listing), massive data sets become easy to analyze.

### Contact

The Mandelbrot set. Computer visualizations are often beautiful. The deceptively simple equation that produces these gorgeous images, $z_{n+1}=z_n^2+c$, winds up taxing standard calculations rather quickly. A double-precision float has a precision of just 4.44089209850062616169452667236328125e-16. That may sound like a small number, but it isn’t nearly small enough. Utilizing the GMP Bignum Library, it’s dead simple to get resolutions of approx. 1e-53. And this is as deep as Fractint ever went, so far as I could tell, and also appears to be the limitation of most free Mandelbrot programs. Obviously, this frustrates me. I’d like to be able to keep going, and going, and going…

But in creating a dynamic, browseable Mandelbrot visualization, concern number one is raw speed. And the only way I know how to present an image is pixel-by-pixel, whether it’s by generating a bitmap or plotting on an SDL canvas. Neither of these are particularly fast. As a matter of fact, they’re both slower than molasses in midwinter (for a computer program, anyway). Is there a quicker way? Because I’d love to know what that method is…

Wednesday, I spent $263.90.$20.71 of that was tax (I am aware that the number doesn’t come out to 7.3%: gasoline has a state tax rate of 43.4¢/gallon, or 13.5% at today’s price). Anyway, $138.42 of that was for the ability to post this. My Terayon TJ715x cable modem was dead. The company, as it turns out, hasn’t existed for more than 5 years. Anyway, this new modem is DOCSIS 3.0 (finally). How much this affects my speed I’m not entirely sure, because although my theoretical (downstream) limit is apparently 304Mbps, I pay for 22Mbps, and get 20 according to Speedtest.net. And if I base my analysis on theory, DOCSIS 3.0 should therefore have no effect unless I bump my service to the “Ultimate” package. I find it suspicious that, when I test my speed using the tools on my ISP’s website, the results it gives are slightly better than what they claim I should be getting, yet somehow significantly different than the aforementioned “independent” website. I also wonder if such testing websites/servers are “whitelisted” by the ISP somehow, so traffic to those IP addresses is not filtered, logged, or throttled, to give the impression of better speed. All in all, I wonder if my DOCSIS 3.0 modem is more gadgetry for the sake of the latest and greatest rather than practicality. There’s another downside: my Cisco/Linksys/DD-WRT router is currently useless, as the cable modem is also a router. But because it’s Netgear, and so new or so specialized that even they don’t have the product listed on their website, I can’t install DD-WRT. So I can’t (as far as I know) change the router administrator username, and the associated password is restricted to a paltry 15 characters (with a default of “password”—I changed that one in a hurry). Another$53.64 of my hard-earned money went to an over-the-air TV antenna. I pick up a whopping 16 channels, and I hope that the $20 premium I spent on the “better” antenna was worth it, if I ditch cable as I intend. The other obstacle to doing so, even though I now have an Internet-connected Blu-Ray player, is the lack of certain channels and shows. The entire Discovery network is unavailable through that device. No A&E networks. No documentaries to discover by chance, like the backstory to the upcoming movie Argo that was on the Military channel earlier this evening. How much, then, does Hulu Plus actually give me over Netflix Streaming? Since Discovery Networks will only let me watch their shows on my computer until they are released on DVD, A&E apparently won’t even let me watch them there unless/until the DVD release. Hulu Plus gives me the option of watching some TV shows the day after they air. Is it worth$7.99 a month? Will Netflix be worth $7.99 a month to me? I’m still undecided on both those issues. I have 5 more days of Hulu Plus for free, and 28 more days of Netflix Streaming for free. But if I dump cable,$85.98 of that bill goes away each month, and it’s then unlikely that I’ll miss the happenstance documentaries that make The Science Channel and The History Channel so unbelievably addicting, because the temptation won’t be there.

I do find it somewhat interesting the omissions from Hulu Plus, iTunes, and Netflix: Castle Season 1 (Hulu Plus), Top Gear Series 1 (Netflix), and Top Gear Series 5 (iTunes). All rather good, and available on one or more of the other services. But iTunes would require hooking up a computer to the television, which means VGA or HDMI, rather than the more convenient DVI.

Which brings me to my next point: I need to run two network cables (and therefore network jacks) to my front room, right where the entertainment center currently sits, one for the Blu-Ray player and one for a computer to be added at some unspecified future date. My low-voltage wiring in this house is…rather strange, because I did it myself, I had little time to think about where the furniture was going to end up, and subsequently a few outlets for low voltage are rather out of place. And one standard voltage dual outlet is on the wrong wall in one room, causing some cable confusion. My last order to Monoprice should have included the keystone plate and jacks, but I was too shortsighted to add that to my shopping cart. Then again, I don’t even have the CAT-6 cable, so it wouldn’t have done much good unless I bought that as well.

For some reason this seems rather more rambly than usual, and yet I’m sticking to a single topic longer than usual. Odd…