Starlight Temple

Project management

2010-03-07T10:15:00.004-06:00

Kevin posted this quote at The Smallest Minority:

There Comes a Time
in the
History of Every Project
When It Becomes Necessary
to
Shoot the Engineers
And Begin Production

Top engineers already know this, saying "Just shoot me already" near the end of a big project.

Reinvention

2009-10-03T11:21:00.004-05:00

DNA searching is basically a cross-correlation process, implemented with what amounts to a convolution algorithm if you use numbers to symbolize DNA nucleotides. The same is true for searching amino acid sequences. In fact, amino acids can be coded by chemical similarity, similar chemical properties being assigned nearby numbers.

The thing is, straight-up convolution is sloooow. If the sequence to be searched is N units long, and the sequence searched for is M units long, then it takes O(N*M) work to do a full convolution. If N=10e+9 and M=1e+3, typical values for genome searching, that's 1e+12 computations per query. Ouch.

It occurred to me that there is a much better way of doing this. The Fourier transform of a convolution turns out to be the point-wise product of the Fourier transform of the things being convolved:

F[ convolution(f, g) ] = F[f] * F[g]

For our digital data, the Fourier transform can be done with the Fast Fourier Transform, a clever algorithm with a computing workload of O(N * log N), loads better than O(N²) for naive convolution. The inverse FFT, F^-1, is equally fast.

With a little rearrangement, our convolution becomes simply a pair of FFTs, a pointwise product, and an inverse FFT:

convolution(f, g) = F^-1[ F[f] * F[g] ]

The Fourier transform of the sequence library you are searching can be precomputed and stored, saving computation. The Fourier transform of the sequence you are searching for can probably be computed with a simplified algorithm, since it contains so little data compared to the library sequence.

So you can do full point-by-point DNA alignment with reasonable computer workload. You just have to be willing to take the Fourier transform of a chemical structure, which is a bit unconventional. Although not really unconventional compared to the things quantum physicists take the Fourier transform of.

But it turns out it was already invented [ref 2] when I was 8 years old.

Dang. Why are all the good ideas already taken?

References:

1. Sequence Alignment by Cross-Correlation.

2. An efficient method for matching nucleic acid sequences.

3. MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform

Moldy software build systems

2009-09-28T03:09:00.006-05:00

James Hague points out that many software build systems are baroque, and used infrequently enough that only the truly hardcore ever become competent:

I'm pretty sure there's a standard old build system to do this kind of thing, but in a clunky way where you have to be careful whether you use spaces or tabs, remember arcane bits of syntax, remember what rules and macros are built-in, remember tricks involved in building nested projects, remember the differences between the versions that have gone down their own evolutionary paths. I use it rarely enough that I forget all of these details. There are modern variants, too, that trade all of that 1970s-era fiddling for different lists of things to remember. ...

Not to mention properly quoting pathnames that have spaces in them. Especially if there are wildcards involved.

But there's no need. ... It's easier and faster to put together custom, micro-build systems in the high-level language of your choice.

Hear, hear!

Lately I have been using ANTLR—a parser generator—to make a compiler for a new programming language. (Everybody needs their own programming language!) It appears to be a wonderful package ... but the build system uses Apache Maven.

Oh. Dear.

Somebody noticed that obtaining the prerequisites was a lot of work when building open source projects. Apparently that somebody decided to tackle the challenge by integrating the dependency tracker, package manager, and download tool into the build manager.

However, if you are operating under a restricted environment or behind a firewall, you might need to prepare to run Maven, as it requires write access to the home directory (~/.m2 on Unix/Mac OS X and C:\Documents and Settings\username\.m2 on Windows) and network access to download binary dependencies.

That's certainly reassuring. The build control file is written in XML:

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>org.codehaus.mojo</groupId> <artifactId>my-project</artifactId> <version>1.0</version> </project>

As a wise man once said, "As God is my witness, I thought turkeys could fly."

Update: fixed XML. And title. And fixed the XML again. This time for sure. No, this time for sure.

A brief, incomplete, and mostly wrong history of programming languages

2009-05-10T16:01:00.004-05:00

This hilarious history of computer programming has been making the rounds. But the comments are as full of win as the post itself.

mx1 said...
HAI
CAN HAS STDIO?
VISIBLE "What about LOLCODE?!?!!"
KTHXBYE
May 8, 2009 12:25 PM

Sarah Newman said...
1999 - Dissatisfied with the lack of portability and abstraction in hardware design, a consortium of Electronic Design Automation companies create SystemC, allowing software engineers to design hardware and EDA companies to make lots of money selling separate compilers for CMOS and TTL based designs. Manufacturers later complain of reduced yields because of debug symbols not being stripped, increasing die sizes.
May 8, 2009 10:26 PM

1963 - Ken Iverson invents APL and bases its syntax on some gold tablets given to him by the angel Moroni.
May 8, 2009 5:34 PM

Happy and Sad

2009-04-25T23:11:00.004-05:00

Edit: Dammit, Blogger, when I say I want a large image, give me the full-size version.

Software transactional memory

2009-03-29T06:09:00.002-05:00

Software transactional memory (STM) applies the concept of database transactions to program variables. In a simple implementation, a thread simply executes a transaction without regard to concurrent threads, recording what it reads and what it changes as it proceeds. At the end of the transaction, it checks if any of the variables it accessed were concurrently altered. If they were, it rolls back all of its changes and retries the transaction from the start. If they were not, the transaction succeeds and any changes become permanent.

I don't like this naive approach because it gives up consistency. Because a transaction's input may be randomly altered by other transactions in progress, it may receive corrupt input, triggering foolish actions. The Wikipedia article gives an example of an inconsistency that sends one thread into an infinite loop, for which there are no good or general ways to recover.

Consistency could be provided by the standard means used by relational databases—snapshot copies, global version counters, etc.—but the cost of locking on large numbers of processors would be prohibitive.

STM strikes me as vulnerable to hijinks, since the first transaction to finish wins. A network attacker simply has to identify a fast, innocuous transaction that writes to the same data used by an important transaction that takes a long time to complete. The attacker can prevent the slow transaction from ever completing by simply sending requests slightly more often than the long transaction takes. One could say "Well, that is the system engineer's fault for putting an atomic { ... } clause around such a long process", but that dodges that (1) mistakes happen when complicated systems are being extended, and (2) any slowness larger than network jitter opens the vulnerability.

The more I think about concurrency on computers with many cores, the more sensible message passing seems. A datum lives on a single core, or in a small group of cores, and all manipulation of it is by requests that travel to the datum's personal hardware. Global synchronization across the many-core computer is just too expensive.

Unicide

2009-02-26T19:27:00.002-06:00

Originally it was a typo, but then I realized just how irritating Unicode and encoding conversions can be.

Politicians donating stolen money to charity

2009-02-20T17:30:00.002-06:00

Sen. Dodd is doing it.

Sen. McCain is doing it.

Pres. Obama is doing it.

What. The. Fuck.

Shouldn't the money be sent back to, you know, the people it was stolen from? With this sort of "morality" running the "stimulus", the market bottom is a long way off.

American Digest on the unread Stimulus Bill

2009-02-15T09:59:00.001-06:00

Sweet dreams, perishing Republic.

Our feudal future

2009-02-15T07:25:00.006-06:00

Friedrich von Blowhard points out that Wall Street is just about to turn America into a Third World financial oligarchy.

Well, the DEA is trying to start a massive new program of regulations that would ban most doctors from prescribing extended-release controlled substances.^**

If this program is approved, I reckon it will give a substantial revenue boost to the DEA's pet Mexican drug oligarchs, by reducing market competition for their expensive black market products.

We care because the drug oligarchs' insurgency, indirectly funded by the DEA apparat, is giving northern Mexico the rough equivalent of a 9-11 attack every three months. The insurgency already operates openly in many American cities, carefully ignored by politicians who are in the pay of the "undocumented immigrant" caucus. For instance, the LA suburb of Compton and its neighbors are experiencing black flight^## as the insurgency's violence exceeds what even black gangbangers are willing to tolerate. Phoenix, AZ has achieved the distinction of being runner up in the competition for kidnapping capital of the world (the winner is Mexico City), where the insurgency ransoms and decapitates almost with impunity.

In the long run, this situation is untenable and will stop. In the short term, it is likely to turn into open warfare, with bombings and widespread banditry.

It is not unlikely that within five years, the American Southwest could become occupied territory, with martial law, curfews, checkpoints for internal passports, and so forth.

And that is one of the better scenarios. If the 10th Amendment/secession movement takes hold before the insurgency ripens and bombings start making the evening news, it is likely the Army will intervene against those evil racist secessionists, giving us a double insurgency and civil war. (A real civil war, fought to annihilate the opposition, not a mere war between the states.)

^**Contrary to what they say, extended-release formulations are generally safer than their immediate release counterparts, because during an overdose they give the human body time to desensitize and compensate. You can live through quite a bit of poisoning as long as the full dose doesn't hit your bloodstream within a few minutes. Yes, some people are killed by misusing these formulations, but that's because thrill seekers and junkies are substituting the extended release drugs for much more expensive black market product. The historical evidence shows that such people kill themselves at an appalling rate no matter the context; by and large, the only thing society can affect is how much they spend on their way out.

^##Black flight! You know the shit has gotten crazy when the negroes haul ass. In fact, looking around the world, that is a pretty good litmus test for the question "Does civil government exist at these grid coordinates?"

Memoirs of Extraordinary Popular Delusions and the Madness of Crowds

2009-02-07T09:42:00.001-06:00

"In reading the history of nations, we find that, like individuals, they have their whims and their peculiarities; their seasons of excitement and recklessness, when they care not what they do. We find that whole communities suddenly fix their minds upon one object, and go mad in its pursuit; that millions of people become simultaneously impressed with one delusion, and run after it, till their attention is caught by some new folly more captivating than the first. We see one nation suddenly seized, from its highest to its lowest members, with a fierce desire of military glory; another as suddenly becoming crazed upon a religious scruple; and neither of them recovering its senses until it has shed rivers of blood and sowed a harvest of groans and tears, to be reaped by its posterity."

The demographics of research achievement

2009-01-20T02:28:00.003-06:00

This review of The Global Bell Curve: Race, IQ, and Inequality Worldwide explains something that had long perplexed me: why the University of Sao Paulo has an uncannily high quality and quantity of research output compared to typical Central and South American universities.

Lynn's new book provides fascinating historical vignettes to describe all the migrations and mixing of peoples. It also provides clear tables of data, which allow the reader to check the facts for themselves. For example, in Brazil, it is the Japanese who are the highest achieving population. They were brought in as indentured labourers to work the plantations after slavery was abolished in 1888. Yet, today, the Japanese outscore Whites on IQ tests, earn more, and are over-represented in university places. Although they are less than 1% of the total population they comprise 17% of the students at the elite University of Sao Paulo.

Fedthink

2008-12-22T08:57:00.002-06:00

"Stability" — price stability, financial stability — are to my mind like "liquidity": qualities widely considered virtues that are often actually vices. Nevertheless, the Fed pursues these goals, ...
— Interfluidity

Did the trade deficit cause the economic collapse?

2008-11-21T23:20:00.002-06:00

Was it a policy matter beyond the Fed's control? I don't buy it. If the Fed had simply stood pat with the money supply, the newly-opened markets would have drained dollars, causing a stable deflation resembling the situation of the late 1800s. Dropping American prices would have increased exports, while resource competition would have inflated commodities and choked off excessively fast growth in imbalance. The arrangement is reasonably self-stabilizing.

The losers would have been those who had borrowed lots of money for enterprises with thin profit margins. But on a long-enough time scale they are doomed anyway—an inevitable market fluctuation will eventually wipe them out—deflation just blows them up a little sooner. They can only survive with eternal credit expansion. Naturally, this is what the Fed did. The mistake was not treating Chinese goods as a windfall, but propping up marginal enterprises and mistaking the results for efficiency. The more they inflated the money supply, the more illusory "efficiency" sprang out of the woodwork.

Take a look at these charts of the monetary base, the denominator of our fractional reserve monetary system.

Look at the bottom chart. In 1985, the monetary base was growing on a dead steady exponential curve: fractional reserve banking was causing inflation, but the system was net profitable, and the profits were being reinvested in the basis of the system.

Now look at 1995. The monetary base jumped off the tracks as the effective reserve fraction was dialed up. Money was being created fast, but not producing profits fast enough to maintain the new rate of creation. The dot-com bubble promptly inflated and burst from the pressure of all that money creation.

That should have been a wake up call to dial up the effective reserve fraction, but Greenspan decided to try it again, only harder this time.

Now look at early 2008, the last data on the graph. The monetary base actually shrank ever so slightly! Malinvestment was finally destroying money faster than it was being created. That marks the point where our economic system went off the edge of the abyss. The Fed has since manipulated the system so that the graph went vertical, but it is far too late to avoid tremendous destruction of productivity.

Congressional immunity: blessing or plague?

2008-11-20T14:42:00.002-06:00

Firehand thinks that Congressional immunity from extra-Congressional prosecution is a bad idea.

Utter bastard though he might be, Murtha is exactly right about immunity: if lawmakers can be prosecuted at will, then the faction with the sleaziest lawyers can make them write whatever laws they want, and we will be ruled from the shadows. The FBI and DEA are nearly as good at blackmail as the Stasi was, and if they start routinely using those techniques on senators, then the final death of the Republic will be at hand. It is by far the lesser evil to let a few of The Elect get away with retail crime for a few years, and vote them out in due course. The Founders designed a large Congress with immunity and frequent elections for exactly this reason.

Damn the country club Republicans for setting this wolf loose with their perpetual legal campaign against the Clinton administration. The professional ass-clowns would never have figured out how to do it on their own if Gingrich's misguided children had not written a how-to manual and rubbed their noses in it for eight long years.

Toss 'em back, God will know his own.

2008-11-13T12:01:00.004-06:00

ShrinkWrapped talks about a journalist who had the misfortune to mention the Trig Palin abortion sentiments in public.

Barone's comment was not "much too close to the truth", it was the truth. I was flabbergasted to see numerous people writing about how giving birth to Trig was unfair and immoral, to the gleeful approval of other lefties. And it wasn't couched in elliptical or insinuating terms, people were coming right out and saying he should have been aborted to prevent his suffering, or so that society would not be burdened with a useless eater. For a moment the mask slipped and we saw their true ethos of tolerance and acceptance: certain people are disposable. It was no lesson from a dusty history book or a wry Vonnegut story—the door of the eugenics oven stood open and we could feel the heat.

It opened my eyes about something that had been a mystery to me: Why does the Left Reich have such a violent, reactive hatred of IQ tests? Because, according to their ethos, if there existed a group of people with an average IQ of 70, there would be nothing to do but plow them under as fertilizer. And that must not be said out loud.

Why do matter and anti-matter annihilate?

2008-11-10T22:05:00.003-06:00

Trivially, it is because the particles have a "matter charge" that is conserved. Add a particle to its anti-particle and they cancel out the matterness, leaving the more ephemeral aspects to come squirting out, often in the form of simple, energetic force carriers.

Why matterness should be conserved is an open question in physics. Things like momentum are conserved because of symmetries. If all positions in space are equivalent, then the rate of change of position has to be constant in the absence of "action". Thus momentum is conserved.

What the symmetrical thing might be for matterness/antimatterness is not obvious, nor is "action" in this context. The Schrödinger wave equation does not explain any sort of substructure we can sink our hooks into. Surely particles must get their properties for reasons, but clues as to how they do it are few.

Particle models based on topology and shape are attractive because they allow complicated relationships to flower from simple foundations. For example, we can pick two knots that fall apart into a simple loop when cut and spliced to each other. Or a pair of complementary Möbius strips that untwist when spliced together. Alas, deducing fields and forces from tangles seems to be a hard problem.

Books are weapons in the war of ideas

2008-11-08T09:49:00.000-06:00

Blast from the past

2008-09-26T15:40:00.003-05:00

An Amazon customer review of DOW 36,000:

Strong evidence for a market with P/E's of 100+
September 28, 1999
By A Customer
Glassman & Hassett pose a strong argument that the market is undervalued. In a nutshell, his reasoning is that, long term, stocks are no more risky than fixed return investments like bonds. Yet, because earnings tend to grow, they have higher rates of return. This suggests that stocks will rise in price until that gap is closed, which conservatively indicates a 36,000 Dow. Impressive data to back up a strong thesis!

I CAN HAZ BAKSTOP

2008-07-08T15:10:00.002-05:00

I got this email today from Chase:

Today's low rates make it a great time to use the equity in your home to do the things you need!

As a Chase customer, simply apply online or call before August 11, 2008. In just minutes you'll be on your way to doing what you want.

A Chase Home Equity Line lets you have the cash to do what you want...make home improvements, pay off high-interest rate bills, or make other purchases. And the interest you pay may be fully tax deductible. (Consult your tax advisor.)

Do More:
Consolidate debt and pay off bills

Make home improvements

Make major purchases—autos, appliances, furniture—whatever you need!

Gay marriage

2008-06-18T02:27:00.004-05:00

This started out as a comment on NCO Brief.

It is not unreasonable for the State to encourage the raising of children in families, by giving tax breaks, simplifying paperwork, and the like. To the extent that marriage means anything, it is about the making and raising of children, something that every self-sustaining government must take an interest in. It is not practical (or desirable) for the government to review every child to determine how much their parents should be rewarded, but it is possible to give useful general support with marriage subsidies. (IMHO divorce rates don't refute this. Marriage subsidies do help keep an extra parent around for the first few years of the kid's life, a time when extra social contact is uniquely valuable.)

To put a simple lifestyle choice on the same footing, with the same subsidies and benefits, is corrosive to those interests. It must either take money away from other needs, or the taxpayer must be held up at gunpoint for more money, while at the same time trivializing the real purpose of the laws. Proponents of government-subsidized homosexuality cannot plausibly pretend surprise that taxpayers might object to money being frittered away for their private gratification.

In any event, the ostensible reasons in support of gay marriage are probably a smokescreen. I do not mind if San Francisco and its provinces legalize gay marriage. However their experiment works out, we will all learn valuable lessons in due course, and any people harmed can simply drive over to Sacramento and harass the legislature into making some changes. The real reason gay marriage is being popularized is to set the stage for it being litigated in the Supreme Court, so that one more aspect of American life can be regimented in a single winner-takes-all contest. The statists want to bring to family law what they brought to drug law and race relations. The prospect of child custody cases being decided by a National Family Law Administration is chilling.

ATF versus radiator hose - steel cage death match

2008-06-01T17:49:00.002-05:00

The automatic transmission fluid wins.

I spilled fluid on the hose changing the transmission fluid. I thought "How bad could it possibly be? I'll just wash it off later." After just the test drive to make sure the tranny wasn't leaking, the hose was already sticky and well on its way to leave-fingerprints-in-the-rubber.

Go to bed hungry

2008-05-17T14:50:00.002-05:00

Linear Technology has, er, interesting Application Notes.

Voltage detector

2008-04-06T11:13:00.005-05:00

How did I manage to miss the LMV431 precision voltage detector until now? Internally it's like an ordinary precision shunt regulator, but the shunt transistor and error amplifier input have been brought out to separate pins. That makes it good for all sorts of voltage detector and regulation uses.

Here is an example voltage range detector from the datasheet:

Simple, useful, and cheap.

Update: Fixed typo and added "electronics" label.

The Great Deflation

2008-02-20T02:00:00.005-06:00

Yves Smith at naked capitalism points us to an article on the coming Great Deflation:

People borrowed money because they had to. Income growth simply did not keep pace with prices in housing, health care, transportation, energy and food.

Good grief. People did not run up $20k on credit cards because the price of rice and beans had skyrocketed. People did not take out 40 year loans on land yachts because Saudi transportation moguls bid 10-year-old cars through the roof.

They did it because of their psychological state. Material goods became cheap, plentiful, and fabulously diverse. Money became as easily borrowed as a library book, a chit among gentlemen rather than a serious duty. These trends were not merely obvious, they perceptibly accelerated while you watched. Many people observed these facts and concluded that they were now living in a post-scarcity economy. With no everyday evidence to the contrary, they gradually developed a contempt for scarcity.

And if the goods had come from a self-maintaining robot factory in Montana, they'd have been right. The only constraints would have been their imaginations and the universe's limited supply of ergs and atoms. That sort of technological mastery would upturn society and open bewildering vistas of possibility, a utopia of science. United Federation of Planets, here we come!

But there is no robot factory. The cheap goods came from foreigners working damn hard for little return, held in peonage^* to conventional factories. A lot of domestic production (housing, agriculture) was even done by foreigners, legal and otherwise. The easy money was the purchase price of those goods shipped right back to the First World as the foreign central planners held inflation in check.

What seemed to be a new permanently-high plateau was actually a situation balanced on the edge of a knife. Trade imbalances cannot continue forever; the exporter either implodes in a revolution, or completely industrializes. Either way, the imbalance stops. Borrowing cannot continue forever in any economy; it stops when debt exceeds future income, whatever artifice delays the day of reckoning. Financial derivatives cannot be infinitely re-derivatized; eventually their behavior becomes so opaque that dynamic stability cannot be maintained and the whole web unwinds, maybe in white knuckle trading, maybe in a crash. The boom in non-exportable labor (housing, services) was nothing more than the pent up labor from the off-shored jobs finding an outlet. Like the rest of the universe, economies are governed by unavoidable natural laws.

Like natural laws, ingenuity can harness the laws of economies, make them work for our long-term benefit. Alas, in this matter many of the public and the leaders have chosen by default to be kites instead of making themselves into airplanes, tossed by the wind instead of setting their own course. Yeah, the ride starts out more exciting, but what of the storms?

Many will say to me in that day, Lord, Lord, have we not prophesied in thy name? and in thy name have cast out devils? and in thy name done many miracles?

And then will I profess unto them, I never knew you: depart from me, ye that work iniquity.

Therefore whosoever heareth these sayings of mine, and doeth them, I will liken him unto a wise man, which built his house upon a rock: And the rain descended, and the floods came, and the winds blew, and beat upon that house; and it fell not: for it was founded upon a rock.

And every one that heareth these sayings of mine, and doeth them not, shall be likened unto a foolish man, which built his house upon the sand: And the rain descended, and the floods came, and the winds blew, and beat upon that house; and it fell: and great was the fall of it.
— Warren Buffet

^*In peonage for now. It's a long, hard road that leads to industrial prosperity, but the road does get there. The ephemeral nature of mercantilism is a trap for the idle importers, not for the laborers.