Archive for August, 2008

« Older Entries

Fourier transform of the Mandelbrot set

Sunday, August 31st, 2008

I wonder what the Fourier transform of the Mandelbrot set looks like? More specifically, the 2D Fourier transform of the function f(x,y) = {0 if x+iy is in M, 1 otherwise}. This has infinitely fine features, so the Fourier transform will extend out infinitely far from the origin. It's aperiodic, so the Fourier transform will be non-discrete.

The result will be a complex-valued function of complex numbers (since each point in the frequency domain has a phase and amplitude). That raises the question of its analytical properties - is it analytic everywhere, in some places or nowhere? (Probably nowhere).

Other interesting Mandelbrot-set related functions that could also be Fourier transformed:
M_n(x,y) = the nth iterate of the Mandelbrot equation (\displaystyle f = |e^{-\lim_{n \to \infty}\frac{1}{n}M_n}|).
D(x,y) = distance between x+iy and the closest point in the Mandelbrot set. Phase could also encode direction.
P(x,y) = the potential field around an electrically charged Mandelbrot set.

Posted in fractals | 4 Comments »

Units and measures

Saturday, August 30th, 2008

In the US (and just a handful of other backwards places), children are generally taught the imperial units and nobody seems to know very much about the metric system at all.

In most of the rest of the world, children are generally taught metric units - metres, kilograms, litres and so on, and the imperial system (inches, pounds, gallons) if mentioned at all is generally derided as being an outdated, overly complex system. A teacher at school once gave me a hard time for measuring out a circuit board in inches - I explained that I had done it that way because the spacing between the legs of the microchips I was using is one tenth of an inch. That shut him up, though he seemed quite surprised to encounter these old fashioned units in such a high-tech context.

A few years ago it became the law in the UK that most things that are sold by weight or measure must be measured in metric units rather than imperial units. Not everyone was happy about this.

My opinion is that all children should be taught both systems of measurement - it is an important skill to be able to convert between different units, and it helps with mental arithmetic. Also, physicists often use non-metric systems of units, setting one or more of c (the speed of light in a vacuum), G (Einstein's gravitational constant), hbar (the reduced Planck's constant), the Coulomb force constant and k (the Boltzmann constant) to 1 to simplify the equations. These natural units are arguably much more fundamental than the metric units and their values (while not generally very good for day-to-day use) give important insights about our universe. The metric units aren't particularly fundamental - the metre and the kilogram are based on (inaccurate values of) the size of the Earth and the density of water respectively.

Like natural units, the imperial system is also better for some things (many people find the units more convenient, especially for cooking) and isn't completely going away any time soon. While having multiple existing systems of units has caused problems in the past, software can keep track to avoid this sort of thing as long as units are always specified (and they always should be, even in the metric system, as one could get confused between grams and kilograms for example). Accuracy of the older imperial units isn't a problem as they have all long since been redefined to be exact rational multiples of metric units.

I also think that people ought to be allowed to sell things in whatever units they find convenient, as long as that value is either a recognized standard or the conversion factor is clearly posted.

The one problem with some imperial units (in particular, those for measuring volumes) is that they aren't standardized across the world, as I discovered to my dismay when I moved here and first ordered a US pint of beer.

Posted in maths | No Comments »

Simplicity density function

Friday, August 29th, 2008

A commenter on Tuesday's post wondered what the density function of numbers with low complexity looks like. This seemed like an interesting question to me too, so I wrote some code to find out. This is the result:

Simplicity density function

I actually used a slight modification of the complexity metric (L(exp(x)) == L(-x) == L(log(x)) == L(x)+1, L(x+y) == L(x)+L(y)+1, L(0) == 1) and a postfix notation instead of a bracketing one. These are all the numbers x with L(x)<=20. More than that and my program takes up too much memory without some serious optimization.

The smooth curves and straight lines are functions of the real line (which is quite densely covered). The strong horizontal lines above and below the center (0) lines are +πi and -πi, which occur from taking the logarithm of a negative real number. There is a definite fractal nature to the image and lots of repetition (as one would expect, since every function is applied to every previously generated point up to the complexity limit).

I didn't add duplicate elimination rules for duplicates that didn't appear until L(x)>=8 or so, so some points are hotter than they should be, but I don't think fixing this would make the image look significantly different.

The code is here. This header file is also required for the Complex class, and this in turn requires this and this. The program is actually a sort of embryonic symbolic algebra program as it builds trees of expressions and pattern matches strings against them. It generates a 1280x1280 RGB image which I cropped down to 800x600. The colour palette is based on a thermal spectrum where temperature goes as an inverse seventh root of the number of hits on a pixel (no particular mathematical reason for that - I just think it makes it look nice). The points between black and red are fudged a bit.

Posted in fractals | 1 Comment »

Channelling Roald Dahl

Thursday, August 28th, 2008

Once upon a time there was a little girl called Mary. One night she was rudely snatched from her bed by a giant. The giant told her that he had kidnapped her so that she could make dreams for him and his giant friends. The giant (whose name was Seymour) told Mary that giants don't have any dreams - they just go to sleep at the start of the night and wake up in the morning without the feeling of any time having passed.

Seymour explained that he and the other giants saw humans dreaming and saw how much they talked about their dreams when they were awake. They realised that humans considered these dreams to be very valuable and important things and the giants were jealous that they didn't have these valuable night experiences. They decided that perhaps a human would be able to give them some of her dreams and Mary seemed to be an excellent candidate as she had dreams to spare.

Despite feeling a little bit scared of the giants and sad that she was away from her home and her parents and her baby brother, Mary decided to try to help the giants as best as she could. It was the only way she could be sure that they would send her home, and besides which she felt a little bit sorry for them.

"Okay," she said, "find a bed for me and I'll go to sleep in it and then when I'm asleep you can take some of my dreams from me. Don't take them all, though, or there will be none left for me!"
"How do we take your dreams then?" replied Seymour.
"I don't know - I'm just a little girl. This was your idea - you figure it out" replied Mary.
"All right then."

Once Mary was asleep it soon became clear to the giants that she was dreaming - a little smile appeared on her face and her eyelids twitched. Seymour picked up the sleeping girl by one of her legs, held her over his head and shook her up and down like a salt shaker, hoping that the dreams would sprinkle out of her head and onto him.

Mary, of course, woke up right away.

"Arghh!" she screamed. "How can I sleep when you're shaking me like that?"
"Sorry," replied Seymour. "I suppose dreams aren't like salt after all. I should have thought this out before I took a little girl from her home."
"It's okay, Seymour," Mary said. "We'll just try something else."

Mary thought that maybe dreams come in cakes. Dreams could be lots of fun and cakes are also fun so this made sense to her. So the giants took her to their kitchen and she helped them make a cake. She was too small to hold the giants' wooden spoon, or to pour the flour and sugar from the huge bags that the giants had, so she just told them what to do while they did the work. She knew how to make cakes because she often helped her father to make cakes at home.

The cake was as big as a table and as tall as Mary herself. Once it had cooled, the giants sliced it up and each ate a slice. They were delighted as they had never had cake before. Mary picked up a crumb the size of her fist and ate as well - it was delicious.

Full of cake, the giants drifted off to sleep and - wouldn't you know it - they started to dream! They dreamed about flying, and eating cake and other things that giants like to do. But as they started to dream, they gradually got smaller and smaller. By the time they woke up, they were no bigger than you or me. That's why there aren't any giants any more.

Posted in fiction | No Comments »

Coping with slow API calls

Wednesday, August 27th, 2008

I was thinking some more about this recently. Specifically, APIs are generally implemented as DLLs or shared libraries which you load into your process and which expose functions that can simply be called. But in a world with no DLLs, how do you do API calls?

At a fundamental level, there are two things you can do - write to some memory shared by another process and make system calls. The former is useful for setting up calls but not for actually making them, as the process implementing the API has no way to notice when the memory changes (unless it polls, which is not a good solution). But system calls are expensive - the context switch alone could be many thousands of CPU cycles.

I mentioned in the linked post that bandwidth for inter-process communication should not be a problem but I neglected to mention latency - if you can only make API calls a few tens of thousands of times per second, certain operations could become very slow.

However, the latency of any single call is still far below what could be noticed by a human being - the only perceived speed problems caused by this architecture would be if many thousands of API calls were made as a result of a single user action.

I think the answer is to design APIs that aren't "chatty". Such designs are already in common use in database situations, where high-latency APIs have been the rule for a long time. Instead of having getCount() and getItemAtIndex() calls to retrieve a potentially large array of data, you retrieve a "cursor" which can return many records at once.

Another possibility is for APIs themselves to be able to execute simple programs. Again this is an idea used by databases (SQL, the syntax usually used to access databases, is itself a language in its own right). Such programs should not be native code (since that gives all the same problems as DLLs, just backwards) but can be interpreted or written in some sort of verifiable bytecode (which could even be JIT compiled for some crazy scenarios). The language they are written in need not even be Turing-complete - this is just an optimization, not a programming environment.

If all else fails, there is still another way to get low-latency, high-bandwidth communication between chunks of code which don't know about each others' existence, and that is to create a whole new process. The involved APIs return a chunk of code (perhaps in the form described here) and the calling program compiles these (and some code of its own) into a (temporary) chunk of binary code which then gets an entirely new process to execute in. This moves potentially all of the IPC costs to a one-time startup phase. The resulting design resembles Java or .NET in some respects.

This is kind of like the opposite of the Singularity OS - reliability guarantees enforced by the compiler, but the OS allows you to use all the user-mode features of your CPU (not just the ones supported by your runtime) and processes are isolated by the MMU.

Posted in computer | 2 Comments »

A little mathematical game

Tuesday, August 26th, 2008

Given five things:

  • The number 0, denoted 0
  • The ability to find ex for any number x, denoted {x}
  • The ability to find the principle natural logarithm log(x) for any number x, denoted [x]
  • The ability to find the additive inverse -x for any number x, denoted <x>
  • The ability to find the sum x+y for any pair of numbers x and y, denoted (x+y)

What numbers can you make and how long are their denotations? This gives some sort of metric to how "complicated" a number is. Write the length of the smallest possible denotation for number x as L(x). Then:

  • Subtraction: a-b is denoted as (a+<b>) and L(a-b) <= 5+L(a)+L(b)
  • Multiplication: ab is denoted as {([a]+[b])} and L(ab) <= 9+L(a)+L(b)
  • Division: a/b is denoted as {([a]+<[b]>)} and L(a/b) <= 11+L(a)+L(b)
  • Exponentiation: ba is denoted as {{([a]+[[b]])}} and L(ba) <= 13+L(a)+L(b)

Some interesting numbers, with their complexities:

1 {0} 3
e {{0}} 5
-1 <{0}> 5
2 ({0}+{0}) 9
i {{([[<{0}>]]+<[({0}+{0})]>)}} 29
π <{([[<{0}>]]+[{{([[<{0}>]]+<[({0}+{0})]>)}}])}> 47

Some interesting questions:

  • How does the complexity function L grow with its argument?
  • What interesting numbers do not have finite complexity?
  • How could the game be changed to include them?

Related: Fine structure constant update.

Posted in maths | 1 Comment »

rm for the web

Monday, August 25th, 2008

My first thought on reading this article was "what would an rm for the web look like?". It seems that many of the commenters on that post had the same thought.

One possible way this could work is to set up a proxy that people can set in their browser. Then if they don't want to see a particular website any more, they can visit the "rm" website, enter the address of the website that they don't want to see any more and then it would be blocked by the proxy. The "rm" website should of course also provide some way to remove a site from the blocked list.

There are a few reasons why such a thing might be useful. There are a few "shock websites" out there which most people would not want to visit knowingly. It could significantly cut down on the number of instances of rickrolling and spyware infections. It could enable organizations to take control of their own web filtering needs rather than relying on some off-the-shelf solution which is bound to block some sites that it shouldn't. Of course it would be easy to circumvent, but that's not the point - the idea isn't to prevent people from seeing stuff they really want to see, it's to keep them honest and keep them from accidentally stumbling onto unsavory areas of the web.

Posted in computer | No Comments »

Evidence against God

Sunday, August 24th, 2008

A commenter recently suggested that if I wanted to believe in God and went looking for the evidence, I would find it. Nope. Tried that. It didn't work. Back at university I engaged in some great debates with theists, and I really wanted to believe in it. But a dispassionate look at the evidence really does favour the atheist point of view.

The first piece of evidence that Christians will point towards is the Bible. "It's a historical record" they will say. Evidence it may be, but it's not good quality evidence - it's all second hand. Stories passed along from person to person, distorted by time and translation and plucked from historical context. Let's contrast this with the evidence for quantum mechanics (which seems similarly ridiculous at first glance). This is real evidence - experiments which you can do to convince yourself even if you think the original experimenters lied about their results. Experiments which have been repeated all over the world and verified many times. That's real evidence. A book (even a very popular one) is not good evidence.

The next thing Christians will try is sheer weight of support - "two billion people can't be wrong" they say. Well, of course they can - there are also two billion people who are Muslims and Hindus, who the Christians will say are wrong. And another two billion people are either not religious or believe something other than "the big 3". So whatever the truth is, at least two thirds of the people are wrong about it. And even the 2 billion Christians can't all agree on which particular sect is the right one. Number of people is not good evidence.

The third thing is "the power of prayer" and religious people have lots of anecdotes about how prayer has helped particular people. Anecdotes are not evidence though - they suffer from selection effects. When theists pray for something and it comes true it is seen as evidence for God but when they pray for something and it doesn't come through it "must not be God's will for this to come about". If you do actual scientific, statistically accurate analysis of the power of prayer it turns out to have little or no effect. Any effect it does have is not proof of God anyway - it could just be a form of placebo effect.

The fourth is "religious experiences" - people who claim to have seen or touched God, or to have had very powerful feelings of being close to a magnificent, benevolent power. I used to find this argument extremely compelling (and was quite jealous that I hadn't experienced it myself) but I have since discovered that similar effects can be induced in the brain with magnetic fields or drugs. Like the power of prayer, this is something else that is "entirely within the mind". Chemical imbalance in the brain seems to be a much more likely explanation for these experiences than God.

These seem to be the main arguments. There are a number of minor ones as well but they mostly seem to have logical flaws like taking their conclusion as an initial assumption.

There are some very compelling arguments against God as well. The main one is Occam's razor - positing the existence of God doesn't actually explain anything (not even the creation of the universe, as God Himself then has the same origin problem). So we can get a theory of the universe that is simpler (and therefore more likely to be correct) by not including God.

Another thing that I found very convincing is the geographic distribution of different religions. People tend to believe the same things as their parents, friends and neighbours. This suggests that religion is passed on from person to person like a meme rather than having any intrinsic truth. Dawkins poses an evolutionary explanation for this strange human behavior - there is an evolutionary advantage to believing what your parents tell you. This behavior started out as a way for advantage-giving wisdom like "don't eat these particular berries" to spread to one's offspring but because historically we had no way of verifying these memes, incorrect but (mostly) harmless memes like "pray to the great invisible being for healthy crops" also sprang up and took advantage of the same mechanism.

A third argument against religion is how contradictory it is. Surely if there was a God and He wanted us all to behave in a particular way, he would have made the bible very coherent and hard to misinterpret. It is none of these things, as we see from the number of people who misinterpret it to forward their own agendas constantly. In fact, religious dogma seems to be particularly effective as a tool for powerful ruling classes to exert control over the general population, which suggests that it evolved to be that way for exactly that purpose.

Posted in atheism | No Comments »

Atheism vs agnosticism

Saturday, August 23rd, 2008

I used to describe myself as an agnostic, but now I describe myself as an atheist. What changed was not my faith (or lack of it) but what I understood those words to mean.

I used to think that the meanings were as follows:

Atheism: I believe there is no god.
Agnosticism: I neither believe nor disbelieve in God.

But I know think that the following definitions are more accurate:

Atheism: I do not believe that there is a god.
Agnosticism: I have no opinion about the existence or nonexistence of God.

Specifically, I don't think that there is a god but would rather avoid describing myself as having any sort of "belief" one way or the other, because that word carries some implication of "belief without (or despite) evidence". While it's impossible to ever prove with certainty that there is no god (or indeed to prove with certainty anything other than "I think, therefore I am") I think that there is a great deal of evidence that there is no God. I'll take a look at some of this evidence tomorrow.

Posted in atheism | 3 Comments »

Apostasy

Friday, August 22nd, 2008

There have been several moments during my life that particularly influenced me towards atheism.

One of these was when I first started learning about science. Scientific explanations seemed to me to be much more satisfying and believable than those of the bible. For a while I thought that this was because the people who originally wrote down the bible were not sophisticated enough to understand the science so it was written down in terms they might be able to understand on some level - that the bible was a simplified version of the truth that we would eventually figure out for ourselves. I had precedents for this concept - I had computer manuals which give strict instructions like "don't remove the floppy disk from the drive while the light is on" but I later discovered that you can remove disks during the time between when the save operation completes and the light goes out (the instruction in the manual was less efficient and less accurate but easier to understand and more difficult to screw up).

The second of these moments was probably when I was told the story of "doubting Thomas". Nobody ever seemed to be able to explain to me exactly why being skeptical was a bad thing (other than the usual "God works in mysterious ways" rubbish that I always found totally unconvincing).

The third was probably when I tried to read the Old Testament. This must have been during secondary school as well. I got as far as the story of the Tower of Babel. In the past when I heard this story it had been presented as a kind of "just so story" about the origins of the different languages. But when I read it for myself I realized that this God was a real dick! Rather than celebrating the great achievements of his creation, he scrambles their language out of fear and jealousy! ("...now nothing will be restrained from them, which they have imagined to do. Go to, let us go down, and there confound their language..."). At that point I was so disgusted I gave up.

The fourth was at university when (while debating a Christian friend) I came across a site called "Who Gives a Fish" (which now longer seems to exist). This linked to some extremely compelling arguments that all of Christianity is bunk. After reading that (and failing to find the refutations to it that I would expect to find if it were false) I no longer had any desire to be infected with this particular meme.

That I ended up an atheist despite my religious upbringing seems to me to be quite damning evidence against God - surely if there were something to it at least the people who started off religious would stay religious.

Posted in philosophy | No Comments »

« Older Entries