Sunday, March 07, 2010

Project management

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.

Labels: ,


Saturday, October 03, 2009

Reinvention

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(N2) 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

Labels:


Monday, September 28, 2009

Moldy software build systems

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.


Sunday, May 10, 2009

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

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

Saturday, April 25, 2009

Happy and Sad

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

Labels:


Sunday, March 29, 2009

Software transactional memory

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.


Thursday, February 26, 2009

Unicide

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

Labels:


Friday, February 20, 2009

Politicians donating stolen money to charity

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.

Labels:


Sunday, February 15, 2009

American Digest on the unread Stimulus Bill

Sweet dreams, perishing Republic.

Labels:


Our feudal future

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?"


Saturday, February 07, 2009

Memoirs of Extraordinary Popular Delusions and the Madness of Crowds

"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."

Tuesday, January 20, 2009

The demographics of research achievement

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.

Labels: ,


Monday, December 22, 2008

Fedthink

"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


Friday, November 21, 2008

Did the trade deficit cause the economic collapse?

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.

Labels:


Thursday, November 20, 2008

Congressional immunity: blessing or plague?

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.


Thursday, November 13, 2008

Toss 'em back, God will know his own.

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.

Labels: , ,


Monday, November 10, 2008

Why do matter and anti-matter annihilate?

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.

Labels:


Saturday, November 08, 2008

Books are weapons in the war of ideas


Friday, September 26, 2008

Blast from the past

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!


Tuesday, July 08, 2008

I CAN HAZ BAKSTOP

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!


This page is powered by Blogger. Isn't yours?