maths « Reenigne blog

Archive for the ‘maths’ Category

Evolution of morality

Sunday, May 11th, 2008

In my university days I would often have philosophical debates with religious friends. One of them once tried to convince that, if there was no God, there would be no reason to "be good" - that the root of morality had to be spiritual in nature.

As reasons for believing in Gods go, that one seems to be a particularly bad one. Most atheists don't go around raping and murdering people.

My friend presented me with a thought experiment. "Suppose you could kill someone you didn't like, in such a way that it would be provably impossible for anyone to find out it was you - would you do it? A Christian wouldn't, because it's against the wish of God, but an atheist would have no such compunction." Well, first of all it's ridiculous to speculate about an impossible hypothetical situation - no matter what form the proof took, it's impossible to be sure that no mistake was made and that you could never be found out, so as far as you can tell there is always an element of risk. Also, my friend was effectively arguing that the only reason he wouldn't kill is because someone (God, if no-one else) would always find out and dole out punishment. Avoiding a potential punishment seems to me to be the least moral reason for avoiding murdering people - the golden rule is a much better one.

My friend could not conceive of how a sense of morality could have arisen in the human race by evolution alone. But after a small amount of though I realized that there are many evolutionary advantages to helping the other members of your community. If you help your community, the community as a whole is strengthened. The other members of this community are likely to share more of your DNA than members of rival communities. So any advantage to your community improves your DNA's chance of surviving and reproducing. Thus, communities with a sense of morality will tend to be favored by the evolutionary process over communities with no sense of morality.

It isn't just individual survival and reproduction that drive evolution - groups of related individuals exhibit all prerequisites for evolution as well (variation in hereditary characteristics producing survival and reproduction advantages) so social behavior can evolve just as well as body shape.

In order to evolve, social behavior does not have to be encoded in DNA. Ideas can (and do) evolve and propagate just as genes do. The human mind provides an environment that is fertile for memes to breed and evolve. This is good, as speeding memetic evolution gives a survival advantage for our species (arguably, it the one thing that has allowed us to be so spectacularly more successful in control and adaptation than any other).

But just as we apparently have some "junk DNA" in our chromosomes which is reproduced faithfully but doesn't actually do anything useful, we may have accumulated some "junk memes" as well. Perhaps these aided our survivability in the past but now serve no useful purpose. I'll leave you to speculate as to what these memes may be.

Posted in economics, philosophy | No Comments »

The Land of Infinite Fun

Saturday, May 10th, 2008

I've only read one of Iain M. Banks's books Excession) so far but hopefully I will get around to reading some more, because the guy has an incredible imagination. One concept in particular has stuck with me:

Technically, it was a branch of metamathematics, usually called metamathics. Metamathics; the investigation of the properties of Realities (more correctly, Reality-fields) intrinsically unknowable by and from our own, but whose general principles could be hazarded at. Metamathics led to everything else, it led to the places that nobody else had ever seen or heard of or previously imagined.

It was like living half your life in a tiny, stuffy, warm grey box, and being moderately happy in there because you knew no better. and then discovering a little hole in one corner of the box, a tiny opening which you could get a finger into, and tease and pull at, so that eventually you created a tear, which led to a greater tear, which led to the box falling apart around you. so that you stepped out of the tiny box's confines into startlingly cool, clear fresh air and found yourself on top of a mountain, surrounded by deep valleys, sighing forests, soaring peaks, glittering lakes, sparkling snowfields and a stunning, breathtakingly blue sky. And that, of course, wasn't even the start of the real story, that was more like the breath that is drawn in before the first syllable of the first word of the first paragraph of the first chapter of the first book of the first volume of the story.

Metamathics led to the Mind equivalent of that experience, repeated a million times, magnified a billion times, and then beyond, to configurations of wonder and bliss even the simplest abstract of which the human-basic brain had no conceivable way of comprehending. It was like a drug; an ultimately liberating, utterly enhancing, unadulterably beneficial, overpoweringly glorious drug for the intellect of machines as far beyond the sagacity of the human mind as they were beyond its understanding. This was the way the Minds spent their time. They imagined entirely new universes with altered physical laws, and played with them, lived in them and tinkered with them, sometimes setting up the conditions for life, sometimes just letting things run to see if it would arise spontaneously, sometimes arranging things so that life was impossible but other kinds and types of bizarrely fabulous complication were enabled.

Some of the universes possessed just one tiny but significant alteration, leading to some subtle twist in the way things worked, while others were so wildly, aberrantly different it could take a perfectly first-rate Mind the human equivalent of years of intense thought even to find the one tenuously familiar strand of recognisable reality that would allow it to translate the rest into comprehensibility. Between those extremes lay an infinitude of universes of unutterable fascination, consummate joy and absolute enlightenment. All that humanity knew and could understand, every single aspect, known, guessed at and hoped for in and of the universe was like a mean and base mud hut compared to the vast, glittering cloud-high palace of monumentally exquisite proportions and prodigious riches that was the metamathical realm. Within the infinities raised to the power of infinities that those metamathical rules provided, the Minds built their immense pleasure-domes of rhapsodic philosophical ecstasy.

That was where they lived. That was their home. When they weren't running ships, meddling with alien civilisations or planning the future course of the Culture itself, the Minds existed in those fantastic virtual realities, sojourning beyondward into the multi-dimensioned geographies of their unleashed imaginations, vanishingly far away from the single limited point that was reality.

The Minds had long ago come up with a proper name for it; they called it the Irreal, but they thought of it as Infinite Fun. That was what they really knew it as. The Land of Infinite Fun.

It did the experience pathetically little justice.

I think that is my idea of heaven - it would be sort of like doing maths with brain orders of magnitude more complex than my own.

Posted in maths, philosophy | 1 Comment »

Real-time Mandelbrot set zooming

Thursday, September 6th, 2007

A while ago, I discussed a data structure which makes real-time Mandelbrot zooming possible. I finally got around to implementing it and the result is here (source code). Windows only for now, but it could be ported to other platforms with some effort.

As well as real-time zooming, the program has a logarithmic palette, progressive resolution, progressive dwell limit and anti-aliasing.

The program should run on Windows 98 or later and has no dependencies. It uses GDI for drawing - DirectX is not needed. It'll work best if your video mode is set to 32-bit colour depth. It's reasonably fast on my 2GHz Core Duo machine (even though it only uses one core at the moment), but the faster your machine the better. It can be a bit memory hungry (I've seen it use over 200Mb for a detailed 1600x1200 image).

The program is controlled with the mouse - hold down the primary button to zoom in, the secondary button to zoom out and drag with the middle button to pan. I was surprised to learn after implementing them that they are exactly the same as for XaoS. I'd like to think that it's convergent evolution but I probably just subconsciously remembered them from the previous time I used XaoS some months previously.

If you zoom in too far (by a factor of 30 billion or so) you'll reach the limit of double-precision arithmetic and the image will dissolve into rectangles. Eventually I plan to implement multiple precision arithmetic which will make it possible to zoom in much further. Though there will always be a practical limit of just how long it takes to multiply two numbers of sufficient precision.

If you leave it for a while without zooming it will gradually refine the image to sub-pixel level and make some really gorgeous images. It will calculate faster if the window is covered up - redrawing is quite slow, especially once the image is quite highly refined. This is also why the zooming is a bit jerky if you leave it for a while. I'm thinking of ways to improve the rendering speed - I'm wondering if I can do better (at least for highly refined areas) by rendering to a grid-aligned array first and then resampling, instead of rendering each block directly.

I've experimented with SOI (using linear interpolation and a quadrilateral method for divergence detection) but so far it doesn't seem to make much difference (though the fact that it doesn't slow things down terribly is encouraging). This version doesn't include those experiments. Perhaps I need to use a higher-order method. AlmondBread and Fractint use quadratic interpolation. I'm wondering if better results can be achieved by iterating some derivatives of the Mandelbrot formula instead of extra points. Then I wouldn't need to interpolate at all - just evaluate the Taylor expansion when I need to subdivide. And divergence detection would just be a matter of looking at the highest order derivative.

Posted in fractals | 4 Comments »

Recursive subdivision

Tuesday, May 8th, 2007

Recently I was experimenting with drawing some Mandelbrot sets. Rather than scanning across the window pixel by pixel and doing one escape per pixel I generated a sequence of complex numbers within the window by repeatedly adding a complex number with irrational real and imaginary parts (the tangent of the argument of which was also irrational) and wrapping the real and imaginary parts into the window. This scatters points across the window evenly in such a way that no point is ever hit twice (within the bounds of precision) and that the pixel grid becomes gradually more dense. Thus the image sort of "rezzes in" and is gradually refined. Anti-aliasing is sort of built in - as the distance between samples gradually decreases, the effective resolution gradually increases. The program never completely stops but you can tell when it's done as the picture seems perfectly anti-aliased and stops changing. I didn't build this in, but the generated points could potentially be redrawn in a larger window to do a sort of (limited) real-time zoom (a la XaoS but hopefully with less artifacting - though it might take a lot of memory to store all that data).

This is kind of neat but I think we can do much better:

The program doesn't take advantage of the natural structure of the Mandelbrot set (large "lakes" of high iteration count, which have detail only at the edges)
The iteration limit is fixed (it would look wrong if some pixels had different iteration limits) - it would be nice if the iteration limit could be gradually increased (for points near the boundary) at the same time as resolution was gradually increased.
There is no way of reusing the calculation for one point for a nearby point (Synchronous Orbit Iteration, which can really speed things up for very deep zooms)

I think all these things are possible with the right data structure. My idea is to form a sort of 2-dimensional linked list. The image is divided into rectangles. Each rectangle has iteration data (corresponding to its center) and 8 pointers to other rectangles, two on each edge. The two pointers may point to the same rectangle or to different rectangles. Suppose both right-pointers of rectangle A point to rectangle B. Then either the two left-pointers of rectangle B can point back to rectangle A, or only one of them does. Thus, each rectangle is bordered on each side by either two rectangles, one rectangle or half a rectangle. And by a process analogous to linked-list insertion, any rectangle can be subdivided horizontally (if it doesn't have half rectangles on either of the horizontal edges) and/or vertically (if it doesn't have half rectangles on either of the vertical edges).

Thus at any point we can increase resolution (by splitting rectangles) or iteration count (by iterating on existing rectangles). If a rectangle is bounded by lake on all sides it is probably also full of lake and we can avoid subdividing or iterating, meaning that we do less work (or defer work) in the boring areas. We also have a natural way of doing SOI (copying the iteration data when we split a rectangle).

We can also do real-time zooming, by noticing that the relationship between rectangle dimension and pixel dimension need not be fixed, and (if necessary) throwing away or paging out rectangles that are outside the window.

There are some fiddly parts, like "how do you divide your priorities between iterating and subdividing" and "what do you do at the edges" which are the reason why I haven't explored this any futher, but it's an interesting project.

Posted in computer, fractals | 3 Comments »

No competition

Saturday, May 5th, 2007

I've never really liked competing with others. As a child I would often refuse to play party games even at my own birthday party - I preferred to just sit out and watch instead. I suspect that this is because I actually have a fiercely competitive nature, and don't like the feelings that this nature inspires in me (the feeling that I must be better than others, regardless of their feelings, lest I be marked the "loser".)

For the same reason I've never really liked sports (playing or watching) and I suspect I would do better at work if on being told that I will be ranked against my peers my natural inclination was not to think "well I just won't play that game then - I'll just sit it out and do my own thing".

During one electronics class at school, I was helping one of the other students understand something that he was having trouble with. Another student advised me that I should not help him because we were to be graded on a curve, and helping one student implicitly hurts all the others. I don't want to live in a world where nobody helps anybody else - life isn't a zero sum game.

I think competition is overrated as a motivator for human accomplishment anyway. The great works of art of the world weren't created to prove their creators superior to all the other artists, and I think most of the accomplishments in academia happen in spite of the great competition for funding (and publish or perish rather than because of it.

I also suspect that the software industry could have achieved much more were it not for the duplication of effort caused by having competing companies solving essentially the same problems (particularly because of the exponential increase in complexity caused by having to interoperate). Different ideas should be allowed to compete on their own merits rather than on the merits of the companies that sell them.

Having a free market with competition to provide the best prices/best customer service/least environmental harm seems like a good idea in theory but from the individual customer's point of view, their only power is to take their business elsewhere. So my choice is between the supermarket that's close, the one that treats their employees well, the one that's cheap or the one that has the chocolate muffins I like. And (other than writing a letter that is likely to be ignored) I don't really have a way to tell the other two supermarkets why I'm not choosing them. The system only works on the aggregate level - individual consumers with requirements different from the profitable herd are basically screwed.

What's the answer? I'm not sure. Clearly some forms of competition are necessary (since communism didn't work out so well) and some people do great things precisely because of competitive pressures. But I think I would like to see a shift in policy towards rewarding cooperation and "absolute performance" and away from rewarding "performance relative to competition". Unfortunately that's rather more difficult to set up than a free market - in some disciplines (like computer programming) absolute performance is extremely difficult to measure absolutely (almost any metric you choose can be gamed). Also, if different factors become important (for example if we as a species suddenly decide than environmentalism is important) we all have to agree to change the metrics to take this into account, whereas in a free market we just have to have enough consumers decide "environmentalism is important to me - I will choose the environmentally friendly product even though it is more expensive".

Posted in economics, philosophy | No Comments »

Interesting blog

Friday, May 4th, 2007

Scott Aaronson's lecture serious Quantum Computing since Democritus is brilliant - fascinating and hilarious. If I had been taught by this guy at university I might still be in academia. A quote:
Oracles were apparently first studied by Turing, in his 1938 PhD thesis. Obviously, anyone who could write a whole thesis about these fictitious entities would have to be an extremely pure theorist, someone who wouldn't be caught dead doing anything relevant. This was certainly true in Turing's case -- indeed he spent the years after his PhD, from 1939 to 1943, studying certain abstruse symmetry transformations on a 26-letter alphabet.
The sheer range of material just stunning too, and there are lots of in-jokes for those with a passing familiarity with the subjects covered. Plus really smart people like Greg Kuperberg and Bram Cohen read his blog. (And he uses the same hosting provider as me.)

Posted in computer, maths | No Comments »

The mathematics underlying music

Saturday, April 28th, 2007

Did you know that almost all Western music is based on an approximation? 524288 = 531441 to be precise (which is true to an accuracy of about 1.3%). These numbers are quite special:
524288 = 2¹²
531441 = 3¹⁹
Their ratio is called the Pythagorean comma and is the difference between 12 perfect fifths and 7 octaves. In Western music this ratio is treated identically to 1 (i.e. if you go up a fifth 12 times you'll end up on the note you started with, 7 octaves up). This approximation caused an enormous amount of trouble for early piano tuners.

Making this sort of approximation is quite important otherwise there would be an infinite number of notes (if you keep going up in intervals of fifths and going down in intervals of octaves you never get to exactly where you started).

But if we're using computers instead of more primitive instruments to make music, having an infinite number of possible notes doesn't really matter - the computer can represent them as exactly or approximately as you like, making it possible to do perfect just intonation and use any intervals you like without approximating.

The really interesting thing about thinking about intervals instead of "the 12 notes" is (for me) not so much that the different sounds are possible but that the underlying harmonic structure of the music is made explicit. The musical stave with its lines, spaces, sharps and flats has evolved rather than being designed and as such seems to hide the underlying intervals rather than revealing them. A fifth, for example, can be represented by 2 units, 2 units plus an accidental or 2 and half units plus an accidental depending on the note and key signature. But when the music is played they all sound like the same interval.

A much more logical stave would have time going down the vertical axis and frequency along the horizontal axis. Vertical lines would represent notes of constant pitch and horizontal lines would represent particular intervals. The horizontal scale should be made logarithmic so that a particular interval would be the same length no matter what its absolute pitch is. Intervals would be marked with their ratio to make it clearer what they really mean (though with practice it would probably be possible to read this kind of stave by eye without the interval markings). So if an octave is represented by 30mm, a perfect fifth (marked $\frac{3}{2}$ ) would be represented by 17.5mm ( $\displaystyle 30\frac{\log \frac{3}{2}}{\log 2}$ ) and a major third ( $\frac{5}{4}$ ) by 9.7mm ( $\displaystyle 30\frac{\log \frac{5}{4}}{\log 2}$ ).

I ought to try drawing various pieces of music like this to see how it looks. It would also be much easier to write music using "weird" intervals like 7/4 and 12/11 using this stave.

Posted in maths, music | 1 Comment »

What a carry on

Thursday, August 10th, 2006

Suppose you run an airline. Times are hard for you. Fuel costs keep going up, but you can't raise your ticket prices too much or your pleasure customers will holiday closer to home and your business customers will videoconference instead.

You have to find some ways of cutting costs. You can't cut the salaries or benefits of your staff because they'd go on strike. You're already charging passengers extra for their in-flight meal and the movie. What do you do?

Apart from fuel costs, the bane of your existence is passengers:

They bring their own food, drink and cosmetics on board instead of buying your $5 bottled water, $10 sandwiches and $20 moisturizer.
They bring their own books, magazines, MP3 players and movie players aboard, preventing you from making a tidy profit selling entertainment to them.
They cause delays by talking on their cellphones during pre-flight checks, messing up the navigation instruments.
They increase the percentage of time your planes spend on the ground by taking forever to put their huge carry-on bags in the overhead bins. They invariably use these bins selfishly, causing later passengers to have to spend ages rearranging things in order to get everything to fit.
They take forever to get their carry-on bags out of the overhead bins and get off the plane, further increasing the ground-time factor.
They listen to noise-cancelling headphones and are therefore unable to hear instructions from flight crew.

But the passengers pay the bills, so you put up with them.

Hang on a sec, though - all those peeves above aren't so much with the passengers themselves but with all the junk they bring aboard. Almost none of it is really needed, especially given that you can sell them equivalents on board at great profit.

Of course, you can't just say "no non-essential carry on items" - how would you enforce it? The only way to prevent passengers from sneaking in a book or drink is to somehow get the security screeners involved. But how could you possibly convince the world that every piece of carry on baggage is a possible security risk? Well, I'll leave that one up to you.

Whenever new security measures are introduced into your life, ask yourself the following questions:

Will it really improve security?
Regardless of actual improvements in security, who stands to gain from the introduction of these measures?
How could those who make the decision to implement these measures be influenced by those who stand to gain? (Clue... follow the money).

Now, this may sound like a bit of a conspiracy theory but I would not be at all surprised if the security measures introduced in the UK today stick, and spread to other countries. I will also be completely unsurprised if business and first class passengers are exempted from the rule, which would pretty much prove that this is a money-making scheme rather than a security improving one (just like the photo ID requirement).

Posted in economics | No Comments »

Normal freehand

Tuesday, March 28th, 2006

I was talking to my mentor at work a couple of weeks ago and was telling him about a some of the statistics stuff I was doing for the Performance Regression Prevention System analysis tools. In the course of my explanation I drew a bell curve on his whiteboard (as mathematicians, statisticians and physicists are wont to do). He was very impressed by how well I drew the curve freehand.

I guess that's thing I learned at university that I never really thought about. I wonder if I can still draw Zeta and Xi. I remember the first time one of our lecturers drew a Xi on the blackboard at university - half the students didn't believe it was a real Greek letter.

Talking of alphabets, Wikipedia has some fascinating articles about obscure/old alphabets and characters.

Posted in maths | No Comments »

Charity cold calls

Wednesday, March 8th, 2006

Is my karma going to hell because I hang up on charities that phone me asking for money? I always feel a little bit bad for doing so (which happens about once a weekend), but I logically I know I really shouldn't. If everyone donated money to every charity that ever called them, then charity cold calling would just explode and everyone's phone would be continually ringing. The amount of money these charities received would probably increase at first but then fall back to normal levels as people found themselves having to donate smaller and smaller amounts per phone call.

On the other hand, if no-one ever donated money to charities that called them, the calls would soon stop, the people employed to make the phone calls would be able to put their energies towards more constructive uses (such as promoting that charity's cause in less invasive ways, or working more directly to help the people that the charity is trying to help) and I could go back to expecting to speak to family or friends whenever I heard the phone ring.

I figure the best thing to do with charity phone calls is just to hang up as quickly as possible (without even saying anything) after discovering that it's not somebody I know or some kind of emergency. That way I have used up as little of that charity's money/time as possible (not to mention my own valuable time). Doing this feels kind of rude but it really isn't - the call in itself is rude so the social contract of politeness has already been broken and there should be no expectation of politeness from me.

I'm not against the concept of charity altogether (I donate money through work so it gets taken out of my paycheck before the tax withholding, my employer matches my contribution and I don't have to remember what I donated when I come to file my taxes).

Posted in economics, random | No Comments »

Reenigne blog