Wednesday, October 31, 2012

Just some random thoughts

Today's blog was inspired by a good friend and co-worker, Pat. He sent me a link to a brilliant piece of erudition / social commentary.

Random math paper generation


A fellow by the name of Nate Eldredge wrote a program called MathGen that built on the previous program called SCIgen. This clever piece of work will randomly generate math papers. Papers in pure math, ready for submission to a journal. Gibberish papers. 

It seems that someone actually took the challenge and submitted this randomly generated paper to the journal Advances in Pure Mathematics. I am sure that most of my readers have a copy of this journal on their nightstand. I know I keep mine handy.

The paper was accepted. Well, to be honest, it was provisionally accepted. The editor had the gall to ask for a few things to be cleaned up. This oppressive editor complained that he couldn't quite catch the main thought of the article from the abstract.

Naturally, I had to try generating my own paper. And since I am more or less a vain fellow, hell-bent on self aggrandizement, I put my name on the paper. Here is the abstract of my paper.


I will admit to being quite proud of my efforts. I haven't a clue what it means, although I recognize several of the words. But still, I am proud to have my name at the top.

Commentary

That was the erudite part. Taken is small pieces, the text is hard to distinguish from virtually any paper on pure math. Clever little program.

What about the social commentary part of this? Here are some of the conclusions that I could draw from this story.

Conclusion 1 - The journal that provisionally accepted this manuscript? They certainly have egg on their face. What else can I say?

Conclusion 2 - The papers that MathGen writes look a lot like every other pure math paper that I have gone out of my way to not read, so I can hardly fault the editor for not taking the time to understand this random paper. Let's face it. The truth is, pure math papers are all gibberish anyway. I have seen several pure math papers that supply proofs of this.

I should explain here that "John the Math Guy" is not my full name. My full name is "John the Applied Math Guy". I should further explain that applied and pure math guys are not always the best of friends. This is not well known, but applied and pure mathematicians have been at odds ever since Aristotle got in a fistfight with Archimedes over an urn that one of them broke during some bacchanalia. The remnants of those pottery shards and ancient arguments can still be seen in the applied versus pure math jokes that have been going around. I am sure you have heard all of them [1]. 

Conclusion 3 - The MathGen program has demonstrated some level of artificial intelligence, perhaps not quite up to the Turing test [2], but it was up to the task in a rather limited scope. This is perhaps not all that surprising, since the Turing test is not all that hard, given the circumstances are narrow enough. The 1966 program ELIZA did a decent job of convincing people that it was a psychotherapist. 

Many lines of code have passed through the compiler since ELIZA. What is the state of the art now? Are other programs capable of producing creative work that rivals humans?  

Random song generation

Years ago, when I got my first computer (it was a Radio Shack Color Computer with 48K of RAM), I played with writing a program that would generate songs at random. The first approach was, well, lousy. It sounded a lot like music by John Cage. This is not all that strange, since Cage wrote one of the first totally aleatoric music pieces, meaning "music composed by throwing dice".


Many times I have pondered ways to make random music sound, well, less random. Rules could be added like "the piece should end on the tonic", and "small steps in pitch are more likely than large ones", and "there is an underlying chord pattern in the song that the notes might want to follow", and, an important one, "breaking the rules once in a while makes the song interesting." I have never taken this idea any further. I guess I am just too lazy to sit around and have my computer write music for me. 

I would assume that I am not the only one who has thought along these lines. I did a very tiny amount of searching and found that Wolfram [3] has put at least some effort into this.  This is cool, cuz these folks are really sharp and they know lots of stuff and everything.

Here is their music generator website. I played with this a while, trying to get a little blues riff going. Blues is one of the choices they have for genre. I figgered this would be a good choice, since the eight-bar blues chord progression is a piece of cake to master [4]. I selected a few instruments that I might like to hear doing blues.

I can't express my level of disappointment. If John Lee Hooker ever met John Cage... Clearly since this percolated up to the top of the Google search, it must represent the absolute bestest available in random music generation technology. Sad.

Random artwork generation

Maybe random generation of art is more state-of-the art? I poked around the internet a bit and found a website where I could generate my own random artwork. I used the title "Random art?" and got the fabulous image below. (This program evidently uses the words you type in to reseed their random number generator, since the same name always gives you the same artwork.)

Random Art?

I don't have to tell you that this piece is absolutely gorgeous. I had it printed on a 2 ft by 2 ft canvas and framed it for my wall. But, is this up to par with what a human artist can do? Have a look at the piece below, and you be the judge [5].


Yes, I agree. Monet couldn't hold a candle to either of these incredible pieces of art.

Random poetry generation

Poetry is another field where the old dice can give a practitioner a run for his money. 

The algorithm for one automatic poetry generator is pretty transparent. You give the poetry generator lists of nouns and of adverbs and all that. You give it a template for the poem, telling it what part of speech to use where. You push the button and it will fill in the blanks with randomly selected words from your lists. Tedious, simple, and boring.

On the other hand, it is my understanding that the algorithm used by this program is not all that different from the one used at the heart of MathGen.

You know what would be nice? It would just be nice if the poetry generator would save me the effort of typing in words and just go out and search the web for seed words. I dunno, maybe I could give it a list of my patents, and it could turn them into some love sonnets. I am sure that would get me the babes.

This next one was quite a bit less work for me, and it actually sounds like poetry  At least to me, someone who really doesn't dig poetry. I guess a poetry aficionado would read this and make sense of it. Maybe even think it's deep?

asphalt lines, slicked with tar in the sun 
radiation in the stormclouds 
bubble cloud air and water mixed 
smooth flat memories of past 
blood becomes timebomb 
flower petals 
forest deer 
rainstorms 
leaves 

Here is yet another random poetry generator, one that has been around for quite some time.

The Rando-Dylan poetry generator

Here is some poetry generated by this random poetry generator:

You never turned around to see the frowns on the jugglers and the clowns
When they all come down and did tricks for you
You never understood that it ain’t no good
You shouldn’t let other people get your kicks for you
You used to ride on the chrome horse with your diplomat
Who carried on his shoulder a Siamese cat
Ain’t it hard when you discover that
He really wasn’t where it’s at
After he took from you everything he could steal

I understand that some people think that Rando-Dylan produces some deep poetry, as well.

Random prose generation

The first random poetry generator picked words at random, but it had the advantage of being fed information about whether a given word was a noun or preposition. This, combined with a template, was enough to create some semblance of proper grammar.

Claude Shannon [6] suggested a different algorithm. Imagine starting by creating a word probability array. The array contains a list of a lot of words along with their probability of occurrence. In this first order approach, the computer merely selects the next word according to the likelihood in the array.

Simply, but it sounds like total gibberish. There is no knowledge of grammar.

Shannon's second order approach is stochastic. The next word in the sequence depends upon current word. The first step is to create a two dimensional histogram of words. Position i,j in this array is the probability that word i will be followed by word j. Such an array could be quite easily created by downloading public domain novels from the internet.

I don't think Shannon did any downloading from the internet, but he did generate the following second-order stochastic prose:

THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE
CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE
LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN
UNEXPECTED.

Gibberish? Well, yeah. But consider doing third order, where each word is generated based on the two previous words. Thus, three word sequences would only appear in the output if they occurred somewhere in the text that built the histogram.

Or why not fourth order, or... Clearly at some point this go from being from a cool way to write novels to plagiarism. I don't care how many books you fed into the program to create the multidimensional histogram, If the computer has a sequence of 50 words, the next word will probably come from the novel that the first 49 words came from. 

Political speech generation

Since I know that both Obama and Romney rush to read my blog every Wednesday morning when it posts, I will end with something that will be of great use to both of them. Yes, there is a random generator of political speeches! I rolled the dice a few times and here is what I got:

My opponent is conspiring with Halliburton board members, street gangs and military-industrial warmongers. I will work for an America where pedophiles and socialists cannot sabotage our love for the Bible. Unlike my opponent, I will protect our right to kill foreigners, our sense of trust and our right to free speech.

I certainly think this passes the Turing test.

-----------------   Notes  --------------------------

[1] A fellow becomes a pure mathematician when it realizes he doesn't have enough personality to be an applied mathematician. Or an accountant. How can you tell the difference between a pure and an applied mathematician? An applied mathematician will look at your shows when he talks to you, rather than his own. A pure and an applied mathematician walk into a bar. The rest of the joke is obvious.

[2] The early computer scientist propose a simple test of whether a computer can "think". If the computer can be mistaken in a conversation with a human being, then the machine can be said to think, or to have artificial intelligence, or at least, can be said to have passed the Turing test.

[3] Wolfram makes the program Mathematica, which I have been using since around 1985.

[4] I haven't quite mastered the eight-bar blues. I am usually stumbling by the third or fourth bar. And I have never made it all the way through the circle of fifths.

[5] I have been accused of stretching the truth sometimes, but this is truth. The image was generated by the online program that I mentioned. You can try it yourself. The painting was indeed painted by Mark Rothco. You can click the link to see. The uncanny resemblance of these two is clearly proof of the fundamental connectedness of all things.

[6] Claude Shannon (1948). The Mathematical Theory of Communication. Bell Systems Technical Journal 27, pp. 379–423, 623–656
  




Wednesday, October 24, 2012

It's all in how you shuffle the deck

The Astounding card trick

Ladies and gentlemen, I will now perform for you the celebrated John the Math Guy card trick. Without the use of PhotoShop or other devious means of deception, I will shuffle an ordinary deck of cards not once (as in tricks performed by the far less talented Rupert the Math Guy), but twice. 

Yes, my friends, I said that two times I will invoke the Goddess Tyche, the Greek (or Roman or whatever) goddess of luck. Twice I will knock on her gates and implore her to make my deck of cards be like unto a random ordering in her sight.

Please turn your attention to the first photograph below - an actual unretouched photograph of the order in which I have placed the deck before my heretofore unprecedented act of prestidigitation. Note the orderliness of the cards, as befits an applied mathematician of my lofty stature. I have proof of the veracity and authenticity of this picture on file in the form of a document to which has been affixed the paw prints of my dear and most honorable dog, Scrabble, attesting to the undeniable fact that all I am relating is the absolute truth.
The actual cards used in this actual experiment before the actual experiment takes place

Now, please watch carefully as I perform the act of shuffling this ordinary deck of cards. The procedure is tripartite in that there are three parts. First the deck is cut roughly in half. (Preferably, it is cut lengthwise and parallel to the face of the cards.) The right and the left hand take the first and second half of the deck, respectively.

Second, the two half-decks are "riffle shuffled", as shown below. The cards are flexed and the thumbs are slowly moved to allow the cards to be flapped downward under the inducement of the flexing. As is well known to one skilled in the art, the order that the cards fall, left or right, is governed solely by the whims of Lady Tyche.

The riffle step of the riffle shuffle

In the third and final step of this tripartite procedure, one applies a reverse flexing of the cards so as to propel them out over the table to the embarrassment of the dealer. The random nature of collecting the cards back into a deck is how randomness is attained.

Friends, with Dog as my witness [1], I am here to tell you that I performed this very procedure exactly twice. Surely if Tyche has provided us with a completely random order by virtue of the first riffle shuffle, then the second process of riffle shuffling should leave us with an even more random order. But to the amazement and perplexification of all in my reading audience, the following unretouched photo shows but a sampling of the bewildering arrangement of the deck. I show the top ten cards of the deck, which include the unbelievable quantity of no less than four kings, and the even more unbelievable quantity of four queens... all in the very topmost ten cards. 

First ten cards in the deck after two riffle shuffles

Explanation

There is no trick here. It took me a few tries to get these results, but these are actual results. I am not a skilled magician, and definitely not a skilled card player. I have been to Vegas only once, and that was for a convention. Let me tell you, the gaming tables are pretty lonely when the annual Math Guy convention hits town! But at least the bars are busy. And the show girls.

If one has executed the riffle shuffle perfectly, the last card down is (let's say) the king of spades. The next to last down will be king of clubs from the other hand. Prior to that, the queen of spades falls, and prior to that, the queen of clubs, and so on. When the deck is split in half for the second riffle, the deck is cut between the two black aces and the two red kings. (Ok... truth be told, I cheated and glanced at the cards as I cut the deck so I could get the correct split. Scrabble didn't catch that.)

It does not take a whole lot of practice to be able to amaze your own friends with this trick. A reasonably well controlled riffle will readily produce a pattern after two shuffles that is clearly not random. This is not rocket science, but anyone who has settled for two shuffles of the deck clearly has not thought this through.

How many times should you shuffle?

Which brings me to the practical question... how many times should you shuffle? I am sure there are many statistically valid ways to look at this question, but I offer one approach that is relatively simple. I start by considering the very top card, which in the illustration of the virgin deck was the king of spades.

I make the simplifying assumption that corresponding cards (that is, the fifth card of the half-deck on the right side, and the fifth card of the half-deck on the left side) will square off and the two will fall in random order. Thus, after the first "perfect" riffle, the king of spades might still be on top, or he might have dropped to the position of the second card.

"No... you go first, I insist"

If the king fell to the second position after the first riffle shuffle, then he will square off with the second card on the other side and wind up in either the third or fourth position after the second riffle. If he makes it down to the fourth position he has a chance to make it to the eighth position after the next riffle. With each additional riffle shuffle, the possible extent that the king may have traveled is doubled.

Thus, under these simplifying assumptions, one needs to shuffle the deck at least six times in order to make it possible for the top card to move to any other position. Wow. I can't imagine any group of card players having the patience to allow someone to shuffle that much!

Scrabble playing poker with some of his buddies

Schafkopf and the riffle shuffle

If you happen to be from Wisconsin, you will know that "Schafkopf" (also known as sheepshead) is a card game. If you are lucky enough to have had someone try to teach you the game, you will know that the queen of clubs takes all, but is only worth two points (or was it three?), whereas the tens are all worth ten points, but don't take many tricks at all. Kings, of course, are four points. The seven of diamonds (which is worth no points at all) will take the ace of spades, which is a good thing, since the partner (one of four players aside from the fellow who picked) has the called ace and has to play it when someone leads that suit. And that's eleven points. I mean the ace is eleven points. If this happens (I mean the seven of diamonds thing) and you are the picker, you better hope you buried some points in the blind so you can at least get schneider, cuz people are likely to schmear!

Sheepshead is often played with five people, and most frequently with a sixth player alternately sitting out so they can deal and then refill everyone else's beer. If you happen to be from Wisconsin, you will be familiar with this amber liquid. If you happen to be from Wisconsin and play sheepshead (but I repeat myself), you will understand that it is impossible to remember all the darn rules for sheepshead without large quantities of this amber liquid. Some have gone so far as to say that beer was invented just so that that people would be able to play sheepshead. 

I mention sheepshead first off because it is the only thing in Wisconsin that is sillier than a cheesehead hat [2]. But more importantly, I mention it because I have a secret to tell - one that up until now, no one else has known.

Sheepshead uses a deck of 32 cards. (That's not the secret, by the way.) If you were to do five perfect riffle shuffles (where the cards fall first from the right side, then the left, then the right, and so on, always starting from the right side) on a sheepshead deck, you will be back exactly where you started. The deck will appear to have not been shuffled at all.

How do I happen to know this? I am glad you asked, because it allows me to brag. Way back in 1984, when most computers were built from Tinkertoys, I built an image processing computer that could perform two dimensional fast Fourier transforms on images. Exciting stuff. Good resume fodder. I mean, what real applied mathematician hasn't taken a youthful foray into Fourier space? I spent at least four years being spaced out in the foyer.
I envisioned at the time a faster fast Fourier transform computer, one which utilized 16 or 32 or 1,024 individual processors, each working on their own part of the data. The difficulty in this design is that eventually the processors would need to share data with other processors - not just any processors, but very specific ones. The riffle shuffle provided exactly the right connections for the proper data sharing. In the first pass, the deck (the data array) is split in half, and adjacent pairs are combined. In the second pass, the array is once again split in half... and so on.

Looking at the FFT flowchart below, it looks as though that second pass does not split the deck in half, but rather into quarters. The difference is that in the traditional algorithm, the results of the combination of the first and the n/2th entry goes in the first location and the n/2th location. There is no shuffling in the traditional algorithm, as there is in my riffle shuffle FFT algorithm. As a result, the data points to combine are always the same in the RS FFT - data points in the first half of the array are always combined with the corresponding points in the second half. This is the magic that makes this the perfect algorithm for a group of 2n processors. The processors that need to pass data amongst themselves are always the same.

FFT butterflies follow the perfect shuffle

When implemented in a standard processor, there is a small benefit to the RS FFT algorithm. The standard FFT requires a final step of de-scrambling the array. The RS FFT algorithm does not require this. The final results are in the correct order.

And that's how I figgered out that five perfect riffle shuffles will restore a deck of cards to it's original order.


I never built this processor or even filed for a patent, but I still think about it whenever I am playing sheepshead and my deal comes up.

------------------------------------------

[1] The Dog in question can be plainly seen in the painting that can be seen between my wrists in the riffle shuffle photo. This is a painting of Scrabble the Shitsu. For more examples of my sister's excellent portraiture, please have a look at Jean Kelly's website. Scrabble was also the model for my blog post on mathematical misnomers.

[2] Disclaimer - While I mention the cheesehead hat, show a picture, and provide a link for where to buy one, I neither promulgate nor disparage wearing the C.H. hat. Those who choose to wear one on a first date, job interview, or wedding ceremony do so at their own risk.

Wednesday, October 17, 2012

Red is the color of....

I ran across an interesting blog today. Jeff Yurek writes a blog called "dot color". If you like my blog, you will like his. It's good stuff.
Jeff's blog

I found his blog because he wrote a blog post about one of my blog posts. Jeff, you have become my instant buddy. (Please take note of this, any of you who wish to become my buddy! I can be had that cheap.)

As I read through his posts (all very interesting), I came across one post that got me thinking. The blog was about the psychological effect of colors, specifically about whether color can have an effect on our buying habits. We would all like to think that we are ultimately in charge of whether we open up our wallet, but maybe the subconscious brain reacts emotionally to colors and clouds our thinking. I like this idea because it is such a good excuse for me to give to my wife when I return from a business trip. Any rationalization that keeps me for accepting responsibility for my bad behavior is a good thing.

Jeff's blog pointed out one bit of research that showed that red is an auspicious color for Olympic wrestlers. Similar research showed that a red background is a good thing for eBay auctioneers as well. People bid higher when there is a red background. Paradoxically, a red background will also lead people to try to negotiate better prices.
Number 316 is clearly excited about bidding because his hair is red

Jeff explains the paradox this way:
"Why? The exact mechanism remains a mystery but researchers see some evidence that aggressive colors like red may actually cause a spike in testosterone levels."

This all got me thinking. There are a lot of designers who will tell you how to use color to manipulate mood. Should I put all this advice into the same bucket where I store advice from palm readers, astrologists, political candidates, and psychotherapist who seem to have this psychological need to make me into a better person? Or is there some science behind the effect of color on mood?  If there is a general consensus on the effect of colors, then perhaps there is some underlying psycho-physical basis.

To answer this, I looked at three books for designers and three websites (see list at the end). Do they basically agree on the psychological effect of seeing red?

"Reds are bright and warm, cheerful and inviting." (Kobayashu)

"Red is passionate, the color of hearts and flames; it attracts our attention, and actually speeds up the body's metabolism." (Chijiiwa)

"[If red is your color] you crave excitement and live for the moment. Easily bored, you also enjoy having the power to get things done quickly. Red lovers are passionate about life." (Sutton and Whelan)

True Red was chosen as the 2002 Pantone color of the year. They had this to say about red in their press release: "This red is a deep shade and is a meaningful and patriotic hue. Red is known as a color of power and/or passion and is thus associated with love."

And here are the comments from from color consultant Kate Smith:
"Recognized as a stimulant, red is inherently exciting and the amount of red is directly related to the level of energy perceived. Red draws attention and a keen use of red as an accent can immediately focus attention on a particular element.
Increases enthusiasm
Stimulates energy and can increase the blood pressure, respiration, heartbeat, and pulse rate
Encourages action and confidence
Provides a sense of protection from fears and anxiety" (Smith)
Kate Smith, not to be confused with Kate Smith

Kate, incidentally, has an active blog on color with 1.32 zillion posts.

Here is what another color consultant, Angela Wright, has to say about red:
"Physical, Positive: Physical courage, strength, warmth, energy, basic survival, 'fight or flight', stimulation, masculinity, excitement. Negative: Defiance, aggression, visual impact, strain." (Wright)

Angela Wright, not to be confused with Angela Cartwright

Do these descriptions of the effect of red all agree? 

One could easily just read through them and say, "yeah, they match". This is a bit problematic though, because of the Forer effect. Bertram Forer was a psychologist who gave his students a personality test, and then handed each one a sheet of paper allegedly being a description of their personality. The students overwhelmingly felt that the descriptions fit them. Unbeknownst to the students, however, each one received the same evaluation, which was a compilation of vague statements from horoscopes. So, it could be that the descriptions of red sound harmonious because they are vague and general enough to sound like they agree.

My opinions on astrology are colored by the fact that I am a Scorpio,
and scorpios don't believe in astrology

Here is a simple test, though, that might even be considered somewhat objective, provided you are not being terribly critical, and have low standards for scientific, un-peer-reviewed research. And provided you are cool with my scientific process of selection of these six references as random, uncorrelated, and authoritative. And, of course, if you are not particularly demanding about doing actual science.

The original premise from Jeff's blog was that red revs people up. How about we look through the descriptions for phrases that say red excites, and phrases that say that red mellows. Scanning through the descriptions of red, I find the following words or phrases that are consonant with revving up:
   
"passion or passionate" (three times)
"speeds up metabolism"
"exciting or excitement" (three times)
"energy" (three times)
"fight or flight"
"stimulant or stimulation" (twice)
"aggression"
"enthusiasm"
"increase bodily functions"
"encourages action"

I see no words that suggest that red will mellow one out. 

This research is incomplete. Ideally, I would identify three or four dimensions (like exciting/relaxing, happy/sad, and fattening/slimming) that colors can be described in. Each color would be given a position in this three or four dimensional space, as well as a tolerance range. If the tolerance ranges overlap a lot, then this is all mumbo-jumbo. If not, then there might be something to the idea that colors elicit emotions.

In an ideal world, of course, the National Institute of Giving Money to Brilliant Applied Mathematicians would knock on my door and give me an embarrassing amount of cash to research this question that is absolutely vital to sustaining our economy. And I would work hard to sustain the economy by throwing elaborate gala events for a hundred or so of my favorite color consultants.

Until I get that know on my door, the tentative conclusion is that red is a color that revs people up. Or, maybe I should say that, based on this research, I can't reject the hypothesis that people believe that the color red revs people up.

-------------  References ---------------
Shigenobu Kobayashi, A Book of Colors, 1987, Nippon Color 
Hideaki Chijiiwa, Color Harmony, a Guide to Creative Color Combinations, 1987, Rockport Publishers
Tina Sutton and Bride M. Whelan, Complete Color Harmony, 2004, Rockport Publishers
Angela Wright, Colour Affects website

   


Wednesday, October 10, 2012

How many colors are there - Addendum

I am reminded today of a line from the song "Alice's Restaurant Masacree" by Arlo Guthrie. He and his friends were off to the garbage dump on Thanksgiving day, when they found the dump closed. Here Arlo takes over the narrative


... we drove off into the sunset looking for another place to put the garbage. We didn't find one. Until we came to a side road, and off the side of the side road there was another fifteen foot cliff and at the bottom of the cliff there was another pile of garbage. And we decided that one big pile is better than two little piles, and rather than bring that one up we decided to throw our's down.

I am quite happy about all the responses I have had to my post on counting the number of colors, ranging from the highly technical to the downright flippant. These responses were posted in a variety of places, and I have decided that one big list of comments is better than five different small lists of comments.

Here's how others answered the question of how many colors there are.


My co-worker Parker Will, who always cracks me up, sent me a link to one person's very imaginative answer. 512 cubic inches. This book simply contains all the colors that are fit to print. It reminds me of a book that may still be in my basement... a book which is a times table from 1 to 999 by 1 to 999.


The RGB Colorspace Atlas


Here are some answers from various LinkedIn groups. I have added some of my own snarky comments.

Nancy Eagan ...as much as there is sunlight ..?

Wei Ji • I think the ultimate question is: how to define "a" colour? the unit that enables us to count how many colours are there.

[Me - Excellent point!]


Mark Taylor • Very thoughtful article. You missed "4" - which is the answer an inkjet printer would give you ;-) 

By the way I've also wondered about what the limits of CIELAB space were, and just assumed as a self-taught color scientist I hadn't yet read the right book!


Gary FieldResearch on the number of colors issue usually starts with reference to the Dorothy Nickerson and Sidney Newhall paper of 1943 (JOSA, pp. 419-422). They conclude that there are about 7,500,000 surface colors at "supraliminal" viewing conditions, and 1,875,000 colors when viewing conditions approximate those used for color matching work.

Some experimental work of mine (1996 TAGA Proceedings, pp. 14-25) from a printing industry perspective suggested that the offset lithographic process could produce about 1,200,000 colors, while the gravure process could achieve about 1,500,000. A later estimate by Andreas Paul of FOGRA was about 1,000,000 colors for 4-color offset lithography, and around 1,400,000 for seven-color lithography.

Mike Pointer and Geoff Attridge concluded that there were about 2,280,000 discernible colors in their 1998 CR&A article (pp. 52-54).

A "color" could be said to exist when an observer indicates that the perceived new sensation differs from a previous sensation. The "16.7 million colors" touted for color monitors means, in my opinion, that there are 16.7 million different combinations of RGB radiation, but because many of these combinations are visually identical, they are not distinct colors from a human perspective. The estimates reported in previous paragraphs are based upon color difference equations of one type or other. Different equations will produce different results, and the illumination level exerts a powerful influence upon the visual color discrimination task.

A TAGA essay of mine, with more detail and some extra references, entitled "The number of printable colors" appears in a collection published under the title of "Color Essentials - Volume 2" that was published by the Printing Industries of America.


http://store.piworld.com/store/p/120-Color-Essentials-Volume-2.aspx

[Me - I am honored to have you comment, Gary. I have one of your books in my bookcase! I have read through your paper, Gary. If I understand correctly, the number is more or less based on the original deltaE formula? Better estimates could be arrived at through DE2000, although this would be a lot of work. I agree with your assessment of the 16.7 million number.]

David Albrecht - There are 4 million colors, give or take a few. This is based on the observations and surveys done over the years for a trained human eye and what it can observe. As Gary points out, a monitor may be able to display more combinations of RGB, but we will only be able to see about 1/4 of the combinations. And according to the rules of observation, if we can't observe them, they do not exist. The "if a tree falls in the woods" concept.

From this 4M or so we drop to untrained human eye, to "compromised" human eye (color blind/deficient), printable colors, etc. It's still amazing that we can reproduce those 1M colors with just 4!

[Me - Nice to have a comment from an old friend.  If a color falls in the woods, will someone walk by and return it to the box?]

Gary Field • Adding to David's comment, color discrimination capability for those with normal color vision peaks between the late teens and early 20s. This brings to mind Keith McLaren's observation concerning "correct" color vision; it is "... always that of the observer having the power to accept the batch as a good commercial match". 

So, the young do indeed have a more colorful world, but the older people who usually wield the 'OK' stamp of approval, establish the color boundaries.

Alessandro Rizzi • Let me suggest an interesting paper about the impossibility of counting the number of colors:
"Why we don’t know how many colors there are"
by Ján Morovic, Vien Cheung, and Peter Morovic
presented at CGIV 2012 conference this year
http://www.slideshare.net/jmorovic/why-we-dont-know-how-many-colors-there-are

Gary Field • @Alessandro: Thank you for that link to the CGIV paper about why we don't know how many colors there are; I found the authors' slide presentation online. Except for very constrained conditions (observer, viewing source; or, if computed, the formula), a definitive, universal number is not likely. I will be happy when claims of "billions" or "a few thousand" colors no longer appear in print (yes, a low bar!).


Arnaud Fabre • Everybody agrees on the fact that the conditions to compute the number of colors are : 
- a well defined set of observation conditions 
- a perceptually homogeneous colorimetric space 
I did not read the paper of CGIV, but I assume that it only ask how we can do serious science with at the basis a vision test applied to 30 persons more or less. And of course Lab is not so perceptually homogeneous, and even with the dE2000 patch, the parameters and the threshold are not so obvious to set. 
But it is the only thing we have, right ? and it did not work so bad most of the time. So the basic idea is more : 
"how can we compute the number of color that are available with those assumptions ?"


Paul Lindström • John – on DE2000 – What is commonly repeated is that a DE of 1 when using the DE Lab formula from 1976, is a reasonable threshold for where humans with reasonable colour vision see a difference between hue shades (colours). When using DE2000 my guess is that the threshold should be somewhere be between 0.5 and 0.75. Might not sound much of a difference, but using 0.5 would double the number of colours (if my layman use of math is correct).

[Me - Math Guy time... if 0.5 DE were to be used instead of 1.0 DE, the number of colors would go up by a factor of 8, since there would be twice as many in all three directions.]

Ryan Stanley • John,

I noticed that in this question vs. your blog you phrase the question two ways:
1: How many colors are there?
2: How many colors are in your rainbow?
The way you interpret those questions can give different answers. Further I think this is where confusion in the industry comes; from laymen to scientist.
I say this because the first question is more scientific; how many colors are there…actually?
For this discussion, let’s look at the “reflectance curve” of light or what “makes” our color as a guide.
If we use what has been defined as the “visible spectrum” of electromagnetic radiation, we find ourselves roughly between 380nm-700nm. Over the years we’ve had spectrophotometers break this down for us with % reflectance across this band. Leaving out fluorescents for this exercise and saying that 0% reflectance is absolute Black (absence of light) and 100% is absolute White (all light). The earlier models commercially available could read every 20nm; now we have models widely available that ready every 10nm; newer models becoming available that can read every 5nm. But let’s just say every 1nm; for if there is a difference in reflectance then there is a difference in color (were not talking about perceivable color just yet).
That’s means from 380 to 700 we have 321 distinct points available for our reflectance curve across the visible spectrum.
Each point has the potential to reflect all light 100% or no light 0%, as well as all points in-between; leaving out decimals for simplicity’s sake (we should measure out to at least two however 000.00) that gives us at least 101 points to choose from.
So we find our % reflectance or “n” is the number of things to choose from, and we choose 321 of them or “r”. With order not being important, and repetition allowing, we have our formula for “how many colors are there?”:
(n+r-1)!/r!(n-1)!
The answer is striking, so I’ll give the short one: 7.83532204e+98
-This is roughly (we only used 0%-100% as whole values) how many colors are available in the visible spectrum for us “to be able” to perceive.

The next question is ambiguous; “how many color are in your rainbow”, or how I read it; how many colors can you see?
You showed a chromaticity diagram in your blog, with that as a reference;
The way humans perceive light can be compared to how we engineer color as well. We have rods, cones, and available “opsins” (light sensitive chemicals) in our eyes that allow us to perceive shades. This is inverse but still comparable to the Red, Green, and Blue LED’s that make up our computer monitors, or the CMYK pigments in our printers. In the diagram you show what we can see vs. what we can produce or what’s in or out of gamut.
Similar to how you mention “it is impossible to build a computer monitor with three fixed lights that will display all possible colors” , it is additionally impossible for the opsins in our eyes to “perceive” all colors that are available to “receive”.
So depending on who you are, how old you are, your gender, race, which eye you use and even what species you are we all “perceive” color differently. This is what makes color so hotly debated and unique! There are even tetrachromats, or women who can see FOUR distinct ranges of color; making their world much more rich I can imagine.
This is the number where no one really has the right answer and as you state in your blog: “Pick a number between 3 and 16,777,216” .

I would be curious to know if anyone has performed a study or has information on the ability of the opsins to receive light at various levels?
This would allow us to create a similar chromaticity diagram for what we “should” be able to perceive vs. what is available to receive.
Interesting topic; I look forward to other responses.
-Ryan Stanley

[Me - I am going to disagree a little bit, Ryan, on a semantic basis, with your scientific answer. It comes down to what the word "color" means. I think the definition that you have given is something like "unique spectral stimulus". If you go down this path, then I think the number you should come up with is a zillion to the zillionth power, since each of the zillion photons received by the eye could have any of the zillion available wavelengths. But, I don't think it's fair to call each unique spectra a "color". Color does not occur at least until the photons enter the eye. This is, of course, semantics.]


Amrit Bindra • There are as many colors as one could perceive or as a community we all could jointly perceive.

Gary Reif • This is all a reminder that we live in an analog world.

George Dubois If you go by the L,a*,b* color sphere where virtually all colors go from a= -60 to +60 and b=-60 to +60 and L goes from 0 to 100 then you have a color space of 1.13 E 6 (1,130,000). If taking a Delta E for most people of 1.0 being distinguishable then there are 1.13 million colors. If you prefer to say that good people can see to .5 Delta E then the number would be 4.5 m.
[Me - This is a quite reasonable "back of the napkin" estimation. You have assumed a cylinder with average radius of 60... ehhh... sounds good. The choice between cube, cylinder and ellipsoid would give a range between 0.7 and 1.4 million. The assumption that 1 deltaE (or 0.5 deltaE) is the limit of human perceptibility is a bit more iffy, I think. A change of 5 delta E in the chroma of bright yellow is barely perceptible, whereas a change od 0.5 deltaE near gray is barely perceptible.]   

Ryan Stanley As with all topics concerning color or colour, it can be debated to include a greater portion of the UV and IR portion of the spectrum (why i stated roughly) as 380-700 is more universally accepted. To your point however, if we expand it out further and add 20nm on each end, we only find ourselves with an even larger number of potential colors available to receive.
In reference to "how many NM are there between viable differences" I would ask;
what is the definition of viable in this case, or what are you looking to achieve?
Further to the point, "do we get too complex abou how we look at colour?" And bringing both topics together, I would say;

Color and the science of color or more succinctly the interaction between matter and radiated energy is so much more than just what we can see. From instruments that can tell us what metals we have in seconds to unlocking the composition of the atmosphere on a planet in another solar system. We've even been able to identify the expanse of the universe through Doppler or the red/blue shift of distant stars. All through our understanding of "Light".
Armed with the knowledge of color, we begin to use it and shine that light back on the mysteries of the universe. Only through a complex walk can we arrive at simplicities door.
To quote Albert Einstein:
"A man should look for what is, and not for what he thinks should be",
"The most beautiful thing we can experience is the mysterious. It is the source of all true art and science."

Interesting topic; I look forward to other responses.
-Ryan Stanley


[Me - Here are the other responses, Ryan! Thanks for the suggestion.]

John Wells But if you are colour blind, how many colours can you see? I have seen colours matched to less than 0.5 dE and would say they do not match! The colour matchers eye is critical. The analog version is merely a tool to aid those with less critical vision and to overcome the human foibles. For instance put two similar colours side by side, after about 30 seconds the brain, which does not like differences, will try and merge the colours, hence some colour matches are worse than others. The human eye is king (So long as you are not colour blind) and all following analog based matchings, should be based on the total conditions observed at the time the eye passed the colour.

[Me - If someone is colorblind, the number drops appreciably, since color space is two dimensional or one dimensional. As for discerning changes of 0.5 deltaE, that points out a problem with deltaE 76.]
[Me - This one below was my favorite. It was posted on the blog itself. Anyone who knew me in my previous incarnation as John the Revelator knows that music has always been a big part of my life.]

Steve Fowler
we need look no further than Joseph and the amazing technicolor dreamcoat.
the answer is clearly 29 (or maybe 27, or 26 if you're an art teacher).
red and yellow and green and brown and
Scarlet and black and ochre and peach
And ruby and olive and violet and fawn
And lilac and gold and chocolate and mauve
And cream and crimson and silver and rose
And azure and lemon and russet and grey
And purple and white and pink and orange
And blue
Newton, phah...Tim Rice and Andrew Lloyd Webber have the answers (except for silver and gold.....oh yeah, and black)

Wednesday, October 3, 2012

The apple doesn’t fall far from the Newton


Isaac Newton was sitting in his garden, contemplating nature, when an apple fell on his head. The entire notion of gravity came to him in an instant. He immediately saw how it all must fit together.

Did this really happen?

The story of Newton’s apple is a wonderful story of a sudden flash of insight, that “Eureka!” moment. But I am going to argue here that this is not exactly what happened. Here is what we know for sure.

What Newton had to say
Newton was getting on in years, in his early 80's. He was reminiscing about when he was a young man, and told friends that seeing an apple fall got him to pondering on the idea that whatever drew the apple to the Earth most likely had some effect on the moon as well. From this pondering came his theory of gravity.

There are enough independent accounts of Newton’s reminiscence that we can be sure that Newton actually said this in his old age. Voltaire wrote that he heard it from Newton’s niece, Catherine Barton Conduitt. The husband of Newton’s niece, John Conduitt, also committed this story to paper. An independent account came from William Stukeley. He wrote a biography of Newton in which he recounted that Newton himself had told him this story while they walked in the garden.

Henry Pemberton, a mathematician and a friend of Newton’s, also published a biography of Newton. In this biography he said that Newton was meditating in the garden when the idea occurred to him that the moon must be subjected to the same force that drew a falling body to the Earth.

Thus, it is quite likely that Newton told this little anecdote about how he came to discover gravity in a garden when he was 23.  
    
Was he hit on the head?
It is unlikely that the apple actually hit Newton on the head. None of the first-hand and second-hand accounts – people who heard the story from Newton, or from a second party – mentioned this. The embellishment was apparently the creation of Isaac D'Israeli, who was born about 40 years after Newton’s death.

A dashing gentleman

Among other things, D’Israeli wrote a book of essays called Curiosities of Literature, which contained anecdotes about a number of historical figures. D’Israeli started an essay in this book by saying that “Accident has frequently occasioned the most eminent geniuses to display their powers.” 

Isaac Newton and the alleged story of the cranial collision merited one paragraph in this D'Iraeli's book. The preceding paragraph tells of how a fellow by the name of Corneille was saved from a drab lifetime of lawyer-hood by the act of writing poetry for his mistress. The paragraph following Newton’s story tells how Ignatius Loyola founded the Jesuit Society as a result of his reading while he was convalescing from a battle wound.

D’Israeli’s book sounds pretty much like Star Magazine to me.

The modern day version of D’Israeli’s book

Was the whole apple story a fabrication?
The falling of the apple was to have occurred when Newton was 23. It is somewhat strange that Newton never mentioned the anecdote until he was 83. Then again, maybe not? It may be that he never felt it was important, or it may have been a fabrication?

Then again, it might be that Newton provided this anecdote as a way to lend credence to his claim that he discovered the law of gravity.  
  
Did Newton invent discover gravity?
I distinctly remember learning in third grade that Newton invented gravity. Recently I did a thorough patent search and could not find any evidence of him getting credited for this invention. My own research suggests that gravity was invented sometime around one million years ago, since at that time there were certain objects not yet brought under its control.

Two objects not subject to the force of gravity 1,002,012 years ago

But, did Newton discover gravity?  This was not exactly what Newton has been given credit for. Aristotle had written about gravity, and had his own explanation of why it exists[1]. Galileo, who lived before Newton, also had a few things to say about gravity[2].

It would be a little closer to the truth to say that Newton discovered the inverse square law of gravity – that the gravitational force between two objects is inversely proportional to the square of the distance between them.
The inverse square law as applied to light

That statement is not nearly as fun as “Newton discovered gravity”. It is shrouded in arcane mathematical verbiage. I think it puts Newton’s accomplishments just a bit out of the reach of most third grader’s, no matter how thirsty they are for knowledge. But more importantly, that silly inverse square law bit hides a lot of the historical context. There were a number of brilliant insights buried in this law:

First insight – Gravity is not limited to making objects fall to the Earth. This is a completely non-intuitive concept. Gravitational effects between two objects are just not needed when explaining our day-to-day lives, except perhaps to explain why Julia Roberts was ever attracted to Lyle Lovett. I can think of no other explanation for that attraction[3].

Do the laws of physics explain this strange attraction?

Second insight – Gravity applies to objects out in space, like the moon, the Sun, the planets, and to stars other than Julia Roberts and Lyle Lovett.

Third insight – (This is the big one.)  Kepler’s laws, which describe the elliptical paths that planets take, can be explained by an inverse square law of gravity[4].

Newton gives this account of his discovery:
In the same year I began to think of gravity extending to the orb of the Moon and (having found out how to estimate the force with which globe revolving within a sphere presses the surface of a sphere) from Kepler's rule of the periodical times of the Planets being in sesquialternate proportion to their distances from the centres of their Orbs, I deduced that the forces which keep the Planets in their Orbs must reciprocally as the squares of their distances from the centres about which they revolve: and thereby compared the force requisite to keep the Moon in her Orb with the force of gravity at the surface of the Earth, and found them answer pretty nearly.
This is quite a mouthful for one sentence. Newton could have been a great patent writer, if he decided to turn his hand to that occupation[5]. Maybe if he had, he would have filed a patent for the invention of gravity.

Priority of Hooke
But this was Newton’s account, which doesn’t quite square with other facts about the discovery of the inverse square law.

Newton said his ruminations and discovery of the inverse square law date back to a period from 1665 to 1666, when Newton was 23. But, historical evidence contradicts this. In particular, there were a series of letters between Robert Hooke and Newton starting in 1679 that show that Newton had not yet put all the pieces together. In fact, Hooke may have had a better grasp at that time.

Robert Hooke, another dashing man

In the first letter between them, Hooke asserted without proof, that the elliptical motion of the planets around the Sun was the result of a force pulling them toward the Sun. In the ensuing letters, Hooke stated that an inverse square law of gravity would lead to an elliptical orbit.

Newton replied in one letter that an object falling to the center of the Earth, if unobstructed, would follow a spiral. Later he asserted that with a constant force of gravity the object would follow a clover leaf path. Clearly, he was not thinking about an inverse square law and ellipses at this time.

In 1684, Hooke told Edmund Halley that he (I mean Hooke) had developed a proof that an inverse square law of gravitational attraction between celestial objects would lead to elliptical orbits. He never produced the proof.

Edmund Halley (left), not to be confused with Alex Haley, author of Roots (right)

This idea intrigued Halley. Learned men of his time (sadly) did not have lofty discussion topics like Romney’s tax returns and Obama’s birth certificate. The men[6] in his circles were unfortunately limited to mundane topics like Copernicus’ revolutionary idea that the Earth was not the center of the universe about which the Sun and all that stuff revolved[7]. And the exciting idea of Kepler that Ptolemy’s ridiculously complicated mathematical model of the orbits of the planets could be explained by three simple laws[8].

Halley sought out Newton, and posed the question to him. In (Doctor) Halley’s words:
Sr Isaac replied immediately that it would be an Ellipsis, the Doctor struck with joy and amasement asked him how he knew it, why, said he I have calculated it, whereupon Dr Halley asked him for his calculation without any farther delay, Sr Isaac looked among his papers but could not find it, but he promised him to renew it, and then to send it him.
Newton was not immediately able to provide the proof, but shortly after produced a nine page demonstration. At Halley’s urging[9], this was fleshed out and was eventually published as Philosophiae Naturalis Principia Mathematica[10]. This was the first proof that an inverse square law of gravity implied elliptical orbits.

The acrimonious battle with Hooke over priority ensued, but that will be the topic of another blog.

My conclusions from this historical lesson
The bit about Newton being hit by an apple in the garden is clearly a fabrication. Newton did indeed discover the “law of gravity”, which is to say, he is the first to provide a proof that the inverse square law of gravity explained the paths of the planets. It is not likely, however, that he developed the full idea back when he was 23 sitting in a garden, pondering a falling apple.     




[1] This is fascinating history that will be left to a future blog.
[2] Remember the guy who dropped the balls from the Leaning Tower of Pisa? Well, it probably wasn’t Galileo, but it will be another fascinating future blog.
[3] In a previous blog, “Flies walk on the ceiling”, I suggested that a hypothetical Flysaac Newton might have discovered the laws of surface tension instead of gravity.
[4] This sounds like yet another topic for a future blog.
[5] I introduce this as silliness, but patents did exist in England back to the year 1449, when King Henry IV granted a patent for the making of stained glass.
[6] Sadly, these were mostly men. That sounds like another blog topic.
[7] Grist for a future blog?
[8] Another blog? I sure hope I live long enough to write all the blogs that I have half-written in my head.
[9] Although Newton was a prolific writer, he was extremely reluctant o publish, partly due to the mockery he received from his first publication on the nature of light.
[10] It is a shame that Newton did not have the benefit of Google blogs to publish.