« April 2014 | Main | June 2014 »

Saturday, May 31, 2014

Reading List: Miss Leavitt's Stars

Johnson, George. Miss Leavitt's Stars. New York: W. W. Norton, 2005. ISBN 978-0-393-32856-1.
Henrietta Swan Leavitt was a computer. No, this is not a tale of artificial intelligence, but rather of the key discovery which allowed astronomers to grasp the enormity of the universe. In the late 19th century it became increasingly common for daughters of modestly prosperous families to attend college. Henrietta Leavitt's father was a Congregational church minister in Ohio whose income allowed him to send his daughter to Oberlin College in 1885. In 1888 she transferred to the Society for the Collegiate Instruction of Women (later Radcliffe College) in Cambridge Massachusetts where she earned a bachelor's degree in 1892. In her senior year, she took a course in astronomy which sparked a lifetime fascination with the stars. After graduation, she remained in Cambridge and the next year was volunteering at the Harvard College Observatory and was later put on salary.

The director of the observatory, Edward Pickering, realised that while at the time it was considered inappropriate for women to sit up all night operating a telescope, much of the work of astronomy consisted of tedious tasks such as measuring the position and brightness of stars on photographic plates, compiling catalogues, and performing analyses based upon their data. Pickering realised that there was a pool of college educated women (especially in the Boston area) who were unlikely to find work as scientists but who were perfectly capable of doing this office work so essential to the progress of astronomy. Further, they would work for a fraction of the salary of a professional astronomer and Pickering, a shrewd administrator as well as a scientist, reasoned he could boost the output of his observatory by a substantial factor within the available budget. So it was that Leavitt was hired to work full-time at the observatory with a job title of “computer” and a salary of US$ 0.25 per hour (she later got a raise to 0.30, which is comparable to the U.S. federal minimum wage in 2013).

There was no shortage of work for Leavitt and her fellow computers (nicknamed “Pickering's Harem”) to do. The major project underway at the observatory was the creation of a catalogue of the position, magnitude, and colour of all stars visible from the northern hemisphere to the limiting magnitude of the telescope available. This was done by exposing glass photographic plates in long time exposures while keeping the telescope precisely aimed at a given patch of the sky (although telescopes of era had “clock drives” which approximately tracked the apparent motion of the sky, imprecision in the mechanism required a human observer [all men!] to track a guide star through an eyepiece during the long exposure and manually keep the star centred on the crosshairs with fine adjustment controls). Since each plate covered only a small fraction of the sky, the work of surveying the entire hemisphere was long, tedious, and often frustrating, as a cloud might drift across the field of view and ruin the exposure.

But if the work at the telescope was seemingly endless, analysing the plates it produced was far more arduous. Each plate would contain images of thousands of stars, the position and brightness (inferred from the size of the star's image on the plate) of which had to be measured and recorded. Further, plates taken through different colour filters had to be compared, with the difference in brightness used to estimate each star's colour and hence temperature. And if that weren't enough, plates taken of the same field at different times were compared to discover stars whose brightness varied from one time to another.

There are two kinds of these variable stars. The first consist of multiple star systems where one star periodically eclipses another, with the simplest case being an “eclipsing binary”: two stars which eclipse one another. Intrinsic variable stars are individual stars whose brightness varies over time, often accompanied by a change in the star's colour. Both kinds of variable stars were important to astronomers, with intrinsic variables offering clues to astrophysics and the evolution of stars.

Leavitt was called a “variable star ‘fiend’ ” by a Princeton astronomer in a letter to Pickering, commenting on the flood of discoveries she published in the Harvard Observatory's journals. For the ambitious Pickering, one hemisphere did not suffice. He arranged for an observatory to be established in Arequipa Peru, which would allow stars visible only from the southern hemisphere to be observed and catalogued. A 24 inch telescope and its accessories were shipped around Cape Horn from Boston, and before long the southern sky was being photographed, with the plates sent to Harvard for measurement and cataloguing. When the news had come to Harvard, it was the computers, not the astronomers, who scrutinised them to see what had been discovered.

Now, star catalogues of the kind Pickering was preparing, however useful they were to astronomers, were essentially two-dimensional. They give the position of the star on the sky, but no information about how distant it is from the solar system. Indeed, only the distances of few dozen of the very closest stars had been measured by the end of the 19th century by stellar parallax, but for all the rest of the stars their distances were a complete mystery and consequently also the scale of the visible universe was utterly unknown. Because the intrinsic brightness of stars varies over an enormous range (some stars are a million times more luminous than the Sun, which is itself ten thousand times brighter than some dwarf stars), a star of a given magnitude (brightness as observed from Earth) may either be a nearby star of modest brightness or an brilliant supergiant star far away.

One of the first intrinsic variable stars to be studied in depth was Delta Cephei, found to be variable in 1784. It is the prototype Cepheid variable, many more of which were discovered by Leavitt. Cepheids are old, massive stars, which have burnt up most of their hydrogen fuel and vary with a characteristic sawtooth-shaped light curve with periods ranging from days to months. In Leavitt's time the mechanism for this variability was unknown, but it is now understood to be due to oscillations in the star's radius as the ionisation state of helium in the star's outer layer cycles between opaque and transparent states, repeatedly trapping the star's energy and causing it to expand, then releasing it, making the star contract.

When examining the plates from the telescope in Peru, Leavitt was fascinated by the Magellanic clouds, which look like little bits of the Milky Way which broke off and migrated to distant parts of the sky (we now know them to be dwarf galaxies which may be in orbit around the Milky Way). Leavitt became fascinated by the clouds, and by assiduous searches on multiple plates showing them, eventually published in 1908 a list of 1,777 variable stars she had discovered in them. While astronomers did not know the exact nature of the Magellanic clouds, they were confident of two things: they were very distant (since stars within them of spectral types which are inherently bright were much dimmer than those seen elsewhere in the sky), and all of the stars in them were about the same distance from the solar system, since it was evident the clouds must be gravitationally bound to persist over time.

Leavitt's 1908 paper contained one of the greatest understatements in all of the scientific literature: “It is worthy of notice that the brightest variables have the longer periods.” She had discovered a measuring stick for the universe. In examining Cepheids among the variables in her list, she observed that there was a simple linear relationship between the period of pulsation and how bright the star appeared. But since all of the Cepheids in the clouds must be at about the same distance, that meant their absolute brightness could be determined from their periods. This made the Cepheids “standard candles” which could be used to chart the galaxy and beyond. Since they are so bright, they could be observed at great distances.

To take a simple case, suppose you observe a Cepheid in a star cluster, and another in a different part of the sky. The two have about the same period of oscillation, but the one in the cluster has one quarter the brightness at Earth of the other. Since the periods are the same, you know the inherent luminosities of the two stars are alike, so according to the inverse-square law the cluster must be twice as distant as the other star. If the Cepheids have different periods, the relationship Leavitt discovered can be used to compute the relative difference in their luminosity, again allowing their distances to be compared.

This method provides a relative distance scale to as far as you can identify and measure the periods of Cepheids, but it does not give their absolute distances. However, if you can measure the distance to any single Cepheid by other means, you can now compute the absolute distance to all of them. Not without controversy, this was accomplished, and for the first time astronomers beheld just how enormous the galaxy was, that the solar system was far from its centre, and that the mysterious “spiral neublæ” many had argued were clouds of gas or solar systems in formation were entire other galaxies among a myriad in a universe of breathtaking size. This was the work of others, but all of it was founded on Leavitt's discovery.

Henrietta Leavitt would not live to see all of these consequences of her work. She died of cancer in 1921 at the age of 53, while the debate was still raging over whether the Milky Way was the entire universe or just one of a vast number of “island universes”. Both sides in this controversy based their arguments in large part upon her work.

She was paid just ten cents more per hour than a cotton mill worker, and never given the title “astronomer”, never made an observation with a telescope, and yet working endless hours at her desk made one of the most profound discoveries of 20th century astronomy, one which is still being refined by precision measurements from the Earth and space today. While the public hardly ever heard her name, she published her work in professional journals and eminent astronomers were well aware of its significance and her part in creating it. A 66 kilometre crater on the Moon bears her name (the one named after that Armstrong fellow is just 4.6 km, albeit on the near side).

This short book is only in part a biography of Leavitt. Apart from her work, she left few traces of her life. It is as much a story of how astronomy was done in her days and how she and others made the giant leap in establishing what we now call the cosmic distance ladder. This was a complicated process, with many missteps and controversies along the way, which are well described here.

In the Kindle edition (as viewed on the iPad) the quotations at the start of each chapter are mis-formatted so each character appears on its own line. The index contains references to page numbers in the print edition and is useless because the Kindle edition contains no page numbers.

Posted at 21:54 Permalink

Saturday, May 17, 2014

Reading List: Science Set Free

Sheldrake, Rupert. Science Set Free. New York: Random House, 2011. ISBN 978-0-7704-3672-8.
In this book, the author argues that science, as it is practiced today, has become prisoner to a collection of dogmas which constrain what should be free inquiry into the phenomena it investigates. These dogmas are not the principal theories of modern science such as the standard models of particle physics and cosmology, quantum mechanics, general relativity, or evolution (scientists work on a broad front to falsify these theories, knowing that any evidence to the contrary will win a ticket to Stockholm), but rather higher-level beliefs, often with remarkably little experimental foundation, which few people are working to test. It isn't so much that questioning these dogmas will result in excommunication from science, but rather that few working scientists ever think seriously about whether they might be wrong.

Suppose an astrophysicist in the 1960s started raving that everything we could see through our telescopes or had experimented with in our laboratories made up less than 5% of the mass of the universe, and the balance was around 27% invisible matter whose composition we knew nothing about at all and that the balance was invisible energy which was causing the expansion of the universe to accelerate, defying the universal attraction of gravity. Now, this theorist might not be dragged off in a straitjacket, but he would probably find it very difficult to publish his papers in respectable journals and, if he espoused these notions before obtaining tenure, might find them career-limiting. And yet, this is precisely what most present-day cosmologists consider the “standard model”, and it has been supported by experiments to a high degree of precision.

But even this revolution in our view of the universe and our place within it (95% of everything in the universe is unobserved and unknown!) does not challenge the most fundamental dogmas, ten of which are discussed in this book.

1. Is nature mechanical?

Are there self-organising principles of systems which explain the appearance of order and complexity from simpler systems? Do these same principles apply at levels ranging from formation of superclusters of galaxies to the origin of life and its evolution into ever more complex beings? Is the universe better modelled as a mechanism or an organism?

2. Is the total amount of matter and energy always the same?

Conservation of energy is taken almost as an axiom in physics but is now rarely tested. And what about that dark energy? Most cosmologists now believe that it increases without bound as the universe expands. Where does it come from? If we could somehow convert it to useful energy what does this do to the conservation of energy?

3. Are the laws of nature fixed?

If these laws be fixed, where did they come from? Why do the “fundamental constants” have the values they do? Are they, in fact, constants? These constants have varied in published handbooks over the last 50 years by amounts far greater than the error bars published in those handbooks—why? Are the laws simply habits established by the universe as it is tested? Is this why novel experiments produce results all over the map at the start and then settle down on a stable value as they are repeated? Why do crystallographers find it so difficult to initially crystallise a new compound but then find it increasingly easy thereafter?

4. Is matter unconscious?

If you are conscious, and you believe your brain to be purely a material system, then how can matter be unconscious? Is there something apart from the brain in which consciousness is embodied? If so, what is it? If the matter of your brain is conscious, what other matter could be conscious? The Sun is much larger than your brain and pulses with electromagnetic signals. Is it conscious? What does the Sun think about?

5. Is nature purposeless?

Is it plausible that the universe is the product of randomness devoid of purpose? How did a glowing plasma of subatomic particles organise itself into galaxies, solar systems, planets, life, and eventually scientists who would ask how it all came to be? Why does complexity appear to inexorably increase in systems through which energy flows? Why do patterns assert themselves in nature and persist even in the presence of disruptions? Are there limits to reductionism? Is more different?

6. Is all biological inheritance material?

The softer the science, the harder the dogma. Many physical scientists may take the previous questions as legitimate, albeit eccentric, questions amenable to research, but to question part of the dogma of biology is to whack the wasp nest with the mashie niblick. Our astounding success in sequencing the genomes of numerous organisms and understanding how these genomes are translated (including gene regulation) into the proteins which are assembled into those organisms has been enlightening but has explained much less than many enthusiasts expected. Is there something more going on? Is that “junk DNA” really junk, or is it significant? Is genetic transfer between parents and offspring the only means of information transfer?

7. Are memories stored as material traces?

Try to find a neuroscientist who takes seriously the idea that memories are not encoded somehow in the connections and weights of synapses within the brain. And yet, for half a century, every attempt to determine precisely how and where memories are stored has failed. Could there be something more going on? Recent experiments have indicated that Carolina Sphinx moths (Manduca sexta) remember aversions which they have learned as caterpillars, despite their nervous system being mostly dissolved and reconstituted during metamorphosis. How does this work?

8. Are minds confined to brains?

Somewhere between 70 and 97% of people surveyed in Europe and North America report having experienced the sense of being stared at or of having another person they were staring at from behind react to their stare. In experimental tests, involving tens of thousands of trials, some performed over closed circuit television without a direct visual link, 55% of people could detect when they were being stared at, while 50% would be expected by chance. Although the effect size was small, with the number of trials the result was highly significant.

9. Are psychic phenomena illusory?

More than a century of psychical research has produced ever-better controlled experiments which have converged upon results whose significance, while small, is greater than that which has caused clinical drug trials to have approved or rejected pharmaceuticals. Should we reject this evidence because we can't figure out the mechanism by which it works?

10. Is mechanistic medicine the only kind that really works?

We are the descendants of billions of generations of organisms who survived and reproduced before the advent of doctors. Evidently, we have been well-equipped by the ruthless process of evolution to heal ourselves, at least until we've reproduced and raised our offspring. Understanding of the causes of communicable diseases, public health measures, hygiene in hospitals, and surgical and pharmaceutical interventions have dramatically lengthened our lifespans and increased the years in which we are healthy and active. But does this explain everything? Since 2009 in the United States, response to placebos has been increasing: why? Why do we spend more and more on interventions for the gravely ill and little or nothing on research into complementary therapies which have been shown, in the few formal clinical tests performed, to reduce the incidence of these diseases?

This is a challenging book which asks many more questions than the few I've summarised above and provides extensive information, including citations to original sources, on research which challenges these dogmas. The author is not advocating abolishing our current enterprise of scientific investigation. Instead, he suggests, we might allocate a small fraction of the budget (say, between 1% and 5%) to look at wild-card alternatives. Allowing these to be chosen by the public from a list of proposals through a mechanism like crowd-funding Web sites would raise the public profile of science and engage the public (who are, after all, footing the bill) in the endeavour. (Note that “mainstream” research projects, for example extending the mission of a spacecraft, would be welcome to compete.)

Posted at 22:30 Permalink

Tuesday, May 13, 2014

Reading List: The Curmudgeon's Guide to Getting Ahead

Murray, Charles. The Curmudgeon's Guide to Getting Ahead. New York: Crown Business, 2014. ISBN 978-0-8041-4144-4.
Who, after reaching middle age and having learned, through the tedious but persuasive process of trial and error, what works and what doesn't, how to decide who is worthy of trust, and to distinguish passing fads from enduring values, hasn't dreamed of having a conversation with their twenty year old self, downloading this painfully acquired wisdom to give their younger self a leg up on the slippery, knife-edged-rungs of the ladder of life?

This slim book (144 pages) is a concentrated dose of wisdom applicable to young people entering the job market today. Those of my generation and the author's (he is a few years my senior) often worked at summer jobs during high school and part-time jobs while at university. This provided an introduction to the workplace, with its different social interactions than school or family life (in the business world, don't expect to be thanked for doing your job). Today's graduates entering the workforce often have no experience whatsoever in that environment and are bewildered because the incentives are so different from anything they've experienced before. They may have been a star student, but now they find themselves doing tedious work with little intellectual content, under strict deadlines, reporting to superiors who treat them as replaceable minions, not colleagues. Welcome to the real world.

This is an intensely practical book. Based upon a series of postings the author made on an internal site for interns and entry-level personnel at the American Enterprise Institute, he gives guidelines on writing, speaking, manners, appearance, and life strategy. As the author notes (p. 16), “Lots of the senior people who can help or hinder your career are closeted curmudgeons like me, including executives in their forties who have every appearance of being open minded and cool.” Even if you do not wish to become a curmudgeon yourself as you age (good luck with that, dude or dudette!), your advancement in your career will depend upon the approbation of those people you will become if you are fortunate enough to one day advance to their positions.

As a curmudgeon myself (hey, I hadn't yet turned forty when I found myself wandering the corridors of the company I'd founded and silently asking myself, “Who hired that?”), I found nothing in this book with which I disagree, and my only regret is that I couldn't have read it when I was 20. He warns millennials, “You're approaching adulthood with the elastic limit of a Baccarat champagne flute” (p. 96) and counsels them to spend some of those years when their plasticity is greatest and the penalty for errors is minimal in stretching themselves beyond their comfort zone, preparing for the challenges and adversity which will no doubt come later in life. Doug Casey has said that he could parachute naked into a country in sub-saharan Africa and within one week be in the ruler's office pitching a development scheme. That's rather more extreme than what Murray is advocating, but why not go large? Geronimo!

Throughout, Murray argues that what are often disdained as clichés are simply the accumulated wisdom of hundreds of generations of massively parallel trial and error search of the space of solutions of human problems, and that we ignore them at our peril. This is the essence of conservatism—valuing the wisdom of the past. But that does not mean one should be a conservative in the sense of believing that the past provides a unique template for the future. Those who came before did not have the computational power we have, nor the ability to communicate data worldwide almost instantaneously and nearly for free, nor the capacity, given the will, to migrate from Earth and make our species multi-planetary, nor to fix the aging bug and live forever. These innovations will fundamentally change human and post-human society, and yet I believe those who create them, and those who prosper in those new worlds will be exemplars of the timeless virtues which Murray describes here.

And when you get a tattoo or piercing, consider how it will look when you're seventy.

Posted at 00:15 Permalink

Saturday, May 10, 2014

Reading List: Honor Bound Honor Born

Howe, Steven D. Honor Bound Honor Born. Seattle: Amazon Digital Services, 2011. ASIN B005JPZ4LQ.
During the author's twenty year career at the Los Alamos National Laboratory, he worked on a variety of technologies including nuclear propulsion and applications of nuclear power to space exploration and development. Since the 1980s he has been an advocate of a “power rich” approach to space missions, in particular lunar and Mars bases.

Most NASA design studies for bases have assumed that almost all of the mass required to establish the base and supply its crew must be brought from the Earth, and that electricity will be provided by solar panels or radiothermal generators which provide only limited amounts of power. (On the Moon, where days and nights are two weeks long, solar power is particularly problematic.) Howe explored how the economics of establishing a base would change if it had a compact nuclear fission reactor which could produce more electrical and thermal power (say, 200 kilowatts electrical) than the base required. This would allow the resources of the local environment to be exploited through a variety of industrial processes: “in-situ resource utilisation” (ISRU), which is just space jargon for living off the land.

For example, the Moon's crust is about 40% oxygen, 20% silicon, 12% iron, and 8% aluminium. With abundant power, this regolith can be melted and processed to extract these elements and recombine them into useful materials for the base: oxygen to breathe, iron for structural elements, glass (silicon plus oxygen) for windows and greenhouses, and so on. With the addition of nutrients and trace elements brought from Earth, lunar regolith can be used to grow crops and, with composting of waste many of these nutrients can be recycled. Note that none of this assumes discovery of water ice in perpetually shaded craters at the lunar poles: this can be done anywhere on the Moon. If water is present at the poles, the need to import hydrogen will be eliminated.

ISRU is a complete game-changer. If Conestoga wagons had to set out from the east coast of North America along the Oregon Trail carrying everything they needed for the entire journey, the trip would have been impossible. But the emigrants knew they could collect water, hunt game to eat, gather edible plants, and cut wood to make repairs, and so they only needed to take those items with them which weren't available along the way. So it can be on the Moon, and to an even greater extent on Mars. It's just that to liberate those necessities of life from the dead surface of those bodies requires lots of energy—but we know how to do that.

Now, the author could have written a dry monograph about lunar ISRU to add to the list of technical papers he has already published on the topic, but instead he made it the centrepiece of this science fiction novel, set in the near future, in which Selena Corp mounts a private mission to the Moon, funded on a shoestring, to land Hawk Stanton on the lunar surface with a nuclear reactor and what he needs to bootstrap a lunar base which will support him until he is relieved by the next mission, which will bring more settlers to expand the base. Using fiction as a vehicle to illustrate a mission concept isn't new: Wernher von Braun's original draft (never published) of The Mars Project was also a novel based upon his mission design (when the book by that name was finally published in 1953, it contained only the technical appendix to the novel).

What is different is that while by all accounts of those who have read it, von Braun's novel definitively established that he made the right career choice when he became an engineer rather than a fictioneer, Steven Howe's talents encompass both endeavours. While rich in technical detail (including an appendix which cites research papers regarding technologies used in the novel), this is a gripping page-turner with fleshed-out and complex characters, suspense, plot twists, and a back story of how coercive government reacts when something in which it has had no interest for decades suddenly seems ready to slip through its edacious claws. Hawk is alone and a long way from home, so that any injury or illness is a potential threat to his life and to the mission. The psychology of living and working in such an environment plays a part in the story. And these may not be the greatest threat he faces.

This is an excellent story, which can be read purely as a thriller, an exploration of the potential of lunar ISRU, or both. In an afterword the author says, “Someday, someone will do the missions I have described in this book. I suspect, however, they will not be Americans.” I'm not sure—they may be Americans, but they certainly won't work for NASA. The cover illustration is brilliant.

This book was originally published in 1997 in a paperback edition by Lunatech Press. This edition is now out of print and used copies are scarce and expensive. At this writing, the Kindle edition is just US$ 1.99.

Posted at 21:54 Permalink

Friday, May 9, 2014

Floating Point Benchmark: ALGOL 60 Added

I have posted an update to my trigonometry-intense floating point benchmark which adds ALGOL 60 to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including ALGOL 60 is now available for downloading.

ALGOL 60 was one of the first languages designed to be machine-independent, a standard produced by an committee unaffiliated with any computer manufacturer. ALGOL 60 was also intended to be a means of formally specifying and publishing algorithms in academic journals. Due to this goal, and because at the time input/output (I/O) was considered highly machine-specific, the language specification included no I/O facilities at all. This meant that in order to use it as a programming language, the ALGOL 60 standard had to be extended to include I/O. Each implementation tended to do this in its own way, meaning that while the core language was portable, actual programs could not be moved from one compiler to another without modification. This, along with what was considered the complexity of some aspects of the language, in particular “call by name” procedure parameters, hindered adoption of the language in industry. Further, vendors had already invested heavily in improving the performance of ALGOL 60's principal competitor, FORTRAN, and consequently FORTRAN compilers usually out-performed ALGOL 60. In computationally intense scientific and engineering work, with the slow and costly computers of the time, this gave FORTRAN the edge.

Still, if you look at almost any modern computer language, you'll see the legacy of ALGOL 60. Its generality, machine-independence, support for nested procedures, recursion, and stack-based call structure have become commonplace. Although the term “structured programming” was not invented until years later, ALGOL 60 contained most of the constructs it required.

Programming today in ALGOL 60 is an excellent experience in retrocomputing. While the language was extremely (and, to some, frighteningly) advanced for its time, there are some lacunæ which are striking to the contemporary programmer. Most obvious is the lack of a standard I/O system, but also there is no way to initialise variables (a feature FORTRAN had) except by declaring them and then assigning them values at run time. One cannot define named constants: you either use a literal or declare it as a variable and initialise it (and then someone reading the program can't be sure it's never changed without examining the entire program). There is no standard mechanism for separate compilation: this makes building and maintaining large programs challenging. These facilities were provided by extensions in some implementations of the language, but usually in non-portable ways.

The relative performance of the various language implementations (with C taken as 1) is as follows. All language implementations of the benchmark listed below produced identical results to the last (11th) decimal place.

Language Relative
Time
Details
C 1 GCC 3.2.3 -O3, Linux
Visual Basic .NET 0.866 All optimisations, Windows XP
FORTRAN 1.008 GNU Fortran (g77) 3.2.3 -O3, Linux
Pascal 1.027
1.077
Free Pascal 2.2.0 -O3, Linux
GNU Pascal 2.1 (GCC 2.95.2) -O3, Linux
Java 1.121 Sun JDK 1.5.0_04-b05, Linux
Visual Basic 6 1.132 All optimisations, Windows XP
Haskell 1.223 GHC 7.4.1-O2 -funbox-strict-fields, Linux
Ada 1.401 GNAT/GCC 3.4.4 -O3, Linux
Go 1.481 Go version go1.1.1 linux/amd64, Linux
ALGOL 60 3.951 MARST 2.7, GCC 4.8.1 -O3, Linux
Lisp 7.41
19.8
GNU Common Lisp 2.6.7, Compiled, Linux
GNU Common Lisp 2.6.7, Interpreted
Smalltalk 7.59 GNU Smalltalk 2.3.5, Linux
Forth 9.92 Gforth 0.7.0, Linux
COBOL 12.5
46.3
Micro Focus Visual COBOL 2010, Windows 7
Fixed decimal instead of computational-2
Algol 68 15.2 Algol 68 Genie 2.4.1 -O3, Linux
Python 17.6 Python 2.3.3 -OO, Linux
Perl 23.6 Perl v5.8.0, Linux
Ruby 26.1 Ruby 1.8.3, Linux
JavaScript 27.6
39.1
46.9
Opera 8.0, Linux
Internet Explorer 6.0.2900, Windows XP
Mozilla Firefox 1.0.6, Linux
QBasic 148.3 MS-DOS QBasic 1.1, Windows XP Console

The ALGOL 60 benchmark was developed and run under the GNU MARST ALGOL 60 to C translator. C code was compiled with GCC 4.8.1 with -O3 for the x86_64 architecture. MARST is a reference implementation of ALGOL 60 which includes extensive run-time checking in the C code it generates. A modern purpose-built optimising compiler for ALGOL 60 should, as long as programmers minimise use of call by name procedure parameters, perform at a speed comparable to modern compiled languages.

Posted at 22:45 Permalink

Monday, May 5, 2014

Reading List: Flash Boys

Lewis, Michael. Flash Boys. New York: W. W. Norton, 2014. ISBN 978-0-393-24466-3.
Back in the bad old days before regulation of financial markets, one of the most common scams perpetrated by stockbrokers against their customers was “front running”. When a customer placed an order to buy a large block of stock, which order would be sufficient to move the market price of the stock higher, the broker would first place a smaller order to buy the same stock for its own account which would be filled without moving the market very much. Then the customer order would be placed, resulting in the market moving higher. The broker would then immediately sell the stock it had bought at the higher market price and pocket the difference. The profit on each individual transaction would be small, but if you add this up over all the volume of a broker's trades it is substantial. (For a sell order, the broker simply inverts the sense of the transactions.) Front running amounts to picking the customer's pocket to line that of the broker: if the customer's order were placed directly, it would execute at a better price had it not been front run. Consequently, front running has long been illegal and market regulators look closely at transaction histories to detect evidence of such criminality.

In the first decade of the 21st century, traders in the U.S. stock market discovered the market was behaving in a distinctly odd fashion. They had been used to seeing the bids (offers to buy) and asks (offers to sell) on their terminals and were accustomed to placing an order and seeing it hit by the offers in the market. But now, when they placed an order, the offers on the other side of the trade would instantly evaporate, only to come back at a price adverse to them. Many people running hundreds of billions of dollars in hedge, mutual, and pension funds had no idea what was going on, but they were certain the markets were rigged against them. Brad Katsuyama, working at the Royal Bank of Canada's Wall Street office, decided to get to the bottom of the mystery, and eventually discovered the financial equivalent of what you see when you lift up a sheet of wet cardboard in your yard. Due to regulations intended to make financial markets more efficient and fair, the monolithic stock exchanges in the U.S. had fractured into dozens of computer-mediated exchanges which traded the same securities. A broker seeking to buy stock on behalf of a customer could route the order to any of these exchanges based upon its own proprietary algorithm, or might match the order with that of another customer within its own “dark pool”, whence the transaction was completely opaque to the outside market.

But there were other players involved. Often co-located in or near the buildings housing the exchanges (most of which are in New Jersey, which has such a sterling reputation for probity) were the servers of “high frequency traders” (HFTs), who placed and cancelled orders in times measured in microseconds. What the HFTs were doing was, in a nutshell, front running. Here's how it works: the HFT places orders of a minimum size (typically 100 shares) for a large number of frequently traded stocks on numerous exchanges. When one of these orders is hit, the HFT immediately blasts in orders to other exchanges, which have not yet reacted to the buy order, and acquires sufficient shares to fill the original order before the price moves higher. This will, in turn, move the market higher and once it does, the original buy order is filled at the higher price. The HFT pockets the difference. A millisecond in advance can, and does, turn into billions of dollars of profit looted from investors. And all of this is not only completely legal, many of the exchanges bend over backward to attract and support HFTs in return for the fees they pay, creating bizarre kinds of orders whose only purpose for existing is to facilitate HFT strategies.

As Brad investigated the secretive world of HFTs, he discovered the curious subculture of Russian programmers who, having spent part of their lives learning how to game the Soviet system, took naturally to discovering how to game the much more lucrative world of Wall Street. Finally, he decides there is a business opportunity in creating an exchange which distinguishes itself from the others by not being crooked. This exchange, IEX, (it was originally to be called “Investors Exchange”, but the founders realised that the obvious Internet domain name, investorsexchange.com, could be infelicitously parsed into three words as well as two), would include technological constraints (including 38 miles of fibre optic cable in a box to create latency between the point of presence where traders could attach and the servers which matched bids and asks) which rendered the strategies of the HFTs impotent and obsolete.

Was it conceivable one could be successful on Wall Street by being honest? Perhaps one had to be a Canadian to entertain such a notion, but in the event, it was. But it wasn't easy. IEX rapidly discovered that Wall Street firms, given orders by customers to be executed on IEX, sent them elsewhere to venues more profitable to the broker. Confidentiality rules prohibited IEX from identifying the miscreants, but nothing prevented them, with the brokers' permission, from identifying those who weren't crooked. This worked quite well.

I'm usually pretty difficult to shock when it comes to the underside of the financial system. For decades, my working assumption is that anything, until proven otherwise, is a scam aimed at picking the pockets of customers, and sadly I have found this presumption correct in a large majority of cases. Still, this book was startling. It's amazing the creepy crawlers you see when you lift up that piece of cardboard, and to anybody with an engineering background the rickety structure and fantastic instability of what are supposed to be the capital markets of the world's leading economy is nothing less than shocking. It is no wonder such a system is prone to “flash crashes” and other excursions. An operating system designer who built such a system would be considered guilty of malfeasance (unless, I suppose, he worked for Microsoft, in which case he'd be a candidate for employee of the year), and yet it is tolerated at the heart of a financial system which, if it collapses, can bring down the world's economy.

Now, one can argue that it isn't such a big thing if somebody shaves a penny or two off the price of a stock you buy or sell. If you're a medium- or long-term investor, that'll make little difference in the results. But what will make your blood boil is that the stock broker with whom you're doing business may be complicit in this, and pocketing part of the take. Many people in the real world look at Wall Street and conclude “The markets are rigged; the banks and brokers are crooked; and the system is stacked against the investor.” As this book demonstrates, they are, for the most part, absolutely right.

Posted at 21:37 Permalink

Sunday, May 4, 2014

Floating Point Benchmark: Algol 68 Added

I have posted an update to my trigonometry-intense floating point benchmark which adds Algol 68 to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including Algol 68 is now available for downloading.

1968 was a year when all of the extremes were tested. There were riots, revolutions, invasions of countries trying to throw off the yoke of tyranny, and humans orbiting the Moon, sending back pictures of the home planet rising above its alien horizon. It was only fitting that this year should also herald the advent of the most over-the-top programming language of all time: Algol 68. Algol 68 was conceived to be the successor to ALGOL 60, originally imagined more as a way of formally specifying algorithms than a programming language, but later implemented with extensions on a variety of computers.

Algol 68 is an object lesson of what happens when academics are allowed to run riot. What started out as an attempt to create a practical programming language turned into a scholastic exercise whose initial language definition was incomprehensible to almost everybody and involved a language definition which could produce an infinite number of productions. Several members of the committee working on the language resigned in disgust and produced a minority report savaging the design of the language, which was suppressed by the standards organisation promoting Algol 68.

This was a tragedy on many levels. Algol 68 was, for its time, vastly superior to all alternatives. If those defining and promoting it had been humble enough to express its definition in a form comprehensible by actual programmers and encourage its adoption in industry, by the mid 1970s we would have been using a programming language which was portable among architectures, safe from most of the vulnerabilities of languages like C, equipped with modern memory management (heap and stack allocation, garbage collection), and with support for parallel processes and synchronisation. Algol 68 did not include subsequently-developed concepts such as object-oriented programming, but these could have been added to the existing language far more straightforwardly than the kludge ziggurat which is C++.

When you look at C, Pascal, Modula, Java, and other languages, you can see the legacy of Algol 68. While the language was stillborn, its concepts live unto this day.

The relative performance of the various language implementations (with C taken as 1) is as follows. All language implementations of the benchmark listed below produced identical results to the last (11th) decimal place.

Language Relative
Time
Details
C 1 GCC 3.2.3 -O3, Linux
Visual Basic .NET 0.866 All optimisations, Windows XP
FORTRAN 1.008 GNU Fortran (g77) 3.2.3 -O3, Linux
Pascal 1.027
1.077
Free Pascal 2.2.0 -O3, Linux
GNU Pascal 2.1 (GCC 2.95.2) -O3, Linux
Java 1.121 Sun JDK 1.5.0_04-b05, Linux
Visual Basic 6 1.132 All optimisations, Windows XP
Haskell 1.223 GHC 7.4.1-O2 -funbox-strict-fields, Linux
Ada 1.401 GNAT/GCC 3.4.4 -O3, Linux
Go 1.481 Go version go1.1.1 linux/amd64, Linux
Lisp 7.41
19.8
GNU Common Lisp 2.6.7, Compiled, Linux
GNU Common Lisp 2.6.7, Interpreted
Smalltalk 7.59 GNU Smalltalk 2.3.5, Linux
Forth 9.92 Gforth 0.7.0, Linux
COBOL 12.5
46.3
Micro Focus Visual COBOL 2010, Windows 7
Fixed decimal instead of computational-2
Algol 68 15.2 Algol 68 Genie 2.4.1 -O3, Linux
Python 17.6 Python 2.3.3 -OO, Linux
Perl 23.6 Perl v5.8.0, Linux
Ruby 26.1 Ruby 1.8.3, Linux
JavaScript 27.6
39.1
46.9
Opera 8.0, Linux
Internet Explorer 6.0.2900, Windows XP
Mozilla Firefox 1.0.6, Linux
QBasic 148.3 MS-DOS QBasic 1.1, Windows XP Console

The performance figure for Algol 68 should not be taken as representative of the language. The Algol 68 Genie system I used was developed with the goal of being a reference implementation of the language and a teaching tool. It is a compiler/interpreter with extensive run-time checking, and was not implemented with efficiency as a primary goal. There is no reason to believe that an Algol 68 compiler developed with resources comparable to modern compilers for other languages would not be competitive in performance.

Posted at 23:10 Permalink