Archive for the ‘maths’ Category

Fractional exponent floating point numbers

Thursday, September 20th, 2012

The usual binary representation of floating point numbers is a sign/exponent/mantissa representation. To get an idea of what this means, consider a hypothetical 6-bit floating point format with 1 sign bit, 3 bits of exponent and 2 bits of mantissa. That gives us 64 possibilities, which is sufficiently few that it's practical to list all the possible values:

0 000 00 +0   1 000 00 -0
0 000 01 +0.0625   1 000 01 -0.0625
0 000 10 +0.125   1 000 10 -0.125
0 000 11 +0.1875   1 000 11 -0.1875
0 001 00 +0.25   1 001 00 -0.25
0 001 01 +0.3125   1 001 01 -0.3125
0 001 10 +0.375   1 001 10 -0.375
0 001 11 +0.4375   1 001 11 -0.4375
0 010 00 +0.5   1 010 00 -0.5
0 010 01 +0.625   1 010 01 -0.625
0 010 10 +0.75   1 010 10 -0.75
0 010 11 +0.875   1 010 11 -0.875
0 011 00 +1   1 011 00 -1
0 011 01 +1.25   1 011 01 -1.25
0 011 10 +1.5   1 011 10 -1.5
0 011 11 +1.75   1 011 11 -1.75
0 100 00 +2   1 100 00 -2
0 100 01 +2.5   1 100 01 -2.5
0 100 10 +3   1 100 10 -3
0 100 11 +3.5   1 100 11 -3.5
0 101 00 +4   1 101 00 -4
0 101 01 +5   1 101 01 -5
0 101 10 +6   1 101 10 -6
0 101 11 +7   1 101 11 -7
0 110 00 +8   1 110 00 -8
0 110 01 +10   1 110 01 -10
0 110 10 +12   1 110 10 -12
0 110 11 +14   1 110 11 -14
0 111 00 +Infinity   1 111 00 -Infinity
0 111 01 SNaN   1 111 01 SNaN
0 111 10 QNaN   1 111 10 QNaN
0 111 11 QNaN   1 111 11 QNaN

So we can represent numbers up to (but not including) 16, in steps of (at finest) 1/16.

The distribution of these numbers (on the positive side) looks like this:

As you can see it approximates an exponential curve but is piecewise linear. Despite there being 64 distinct bit patterns, only 55 real numbers are represented because of the infinities, Not-a-Numbers and the two zeroes. Near zero, the pattern is broken and the numbers between 0 and 0.25 have the same spacing as the numbers between 0.25 and 0.5 - these are called the "denormals" and cause enormous headaches for CPU manufacturers, OS developers, toolchain developers and developers of numerical software, since they often either don't work according to the standards or are much slower than the rest of the floating point numbers.

With IEEE-754 single precision floating point numbers, there are so many pieces to the piecewise linear curve (254 of them for each sign) that the piecewise linearity wouldn't be visible on a graph like this, and the proportion of the bit patterns corresponding to distinct real numbers is much higher (close to 255/256 rather than 7/8).

How different would the world be if we just used an exponential curve instead of a piecewise linear approximation of one? That is to say, what if instead of representing floating point number x as A*2B for some integers A and B, we represented it as 2A/k for some integer A and a constant integer k? In other words, we represent floating point numbers as the exponent of a fixed point fraction (hence, the name Fractional Exponent Floating Point or FEFP). Let's choose k such that the powers of two are the same as in the exponent/mantissa representation, i.e. k=4 in this case, and again list all the possibilities:

0 000 00 +0   1 000 00 -0
0 000 01 +0.1487   1 000 01 -0.1487
0 000 10 +0.1768   1 000 10 -0.1768
0 000 11 +0.2102   1 000 11 -0.2102
0 001 00 +0.25   1 001 00 -0.25
0 001 01 +0.2973   1 001 01 -0.2973
0 001 10 +0.3536   1 001 10 -0.3536
0 001 11 +0.4204   1 001 11 -0.4204
0 010 00 +0.5   1 010 00 -0.5
0 010 01 +0.5946   1 010 01 -0.5946
0 010 10 +0.7071   1 010 10 -0.7071
0 010 11 +0.8409   1 010 11 -0.8409
0 011 00 +1   1 011 00 -1
0 011 01 +1.1892   1 011 01 -1.1892
0 011 10 +1.4142   1 011 10 -1.4142
0 011 11 +1.6818   1 011 11 -1.6818
0 100 00 +2   1 100 00 -2
0 100 01 +2.3784   1 100 01 -2.3784
0 100 10 +2.8284   1 100 10 -2.8284
0 100 11 +3.3636   1 100 11 -3.3636
0 101 00 +4   1 101 00 -4
0 101 01 +4.7568   1 101 01 -4.7568
0 101 10 +5.6569   1 101 10 -5.6569
0 101 11 +6.7272   1 101 11 -6.7272
0 110 00 +8   1 110 00 -8
0 110 01 +9.5137   1 110 01 -9.5137
0 110 10 +11.3137   1 110 10 -11.3137
0 110 11 +13.4543   1 110 11 -13.4543
0 111 00 +16   1 111 00 -16
0 111 01 +SNaN   1 111 01 -SNaN
0 111 10 +QNaN   1 111 10 -QNaN
0 111 11 +Infinity   1 111 11 -Infinity

I moved the infinities to have "all 1s" representation, and just reserved 4 extra entries for NaNs (I'm not sure if anyone actually uses the facility of NaNs to store extra data, but a nice thing about this representation is that you can dedicate as few or many bit patterns to NaNs as you like).

A couple of improvements: our "minimum interval" between adjacent numbers is now about 1/36 instead of 1/16 and (because of the NaN tweak) we can represent slightly higher numbers.

In this representation, there's only one "denormal" (zero) for each sign. That can't fit the pattern however we cut it, since our "A" value never reaches minus infinity, however I suspect people would complain if they couldn't put zero in their floating point variables. This does mean that the interval between zero and the next highest number is larger than the minimum interval.

Would it be practical for CPUs to actually do computations with these numbers? Surprisingly, yes - though the trade-offs are different. Multiplication and division of FEFP numbers is just addition and subtraction (of the fixed point fractional exponent). Addition and subtraction are more complicated - you need to actually take the exponent of the representations, add or subtract them and then compute the logarithm to get the representation of the result. That sounds really hard, but using the CORDIC algorithms and some of the trickery currently used to add and subtract floating point numbers, I think additions and subtractions could be done in about the same time and using roughly the same number of transistors as multiplications and divisions of floating point numbers currently use. What's more, it might be possible to reuse some of the add/subtract logic to actually compute exponents and logarithms (which are themselves quite useful and often implemented in hardware anyway).

So I actually think that FEFP is superior to IEEE754 in several ways. The latter is sufficiently entrenched that I doubt that it could ever be replaced completely, but FEFP might find some use in special-purpose hardware applications where IEEE754 compatibility doesn't matter, such as signal processing or graphics acceleration.

Spam for buying instead of selling

Wednesday, September 19th, 2012

Most unsolicited commercial email tries to get its readers to buy something, but recently I had some spam that was the other way around - they wanted to give me money! Specifically, they wanted to buy ad space on one of my sites. Now, given that I don't have any costs involved in running the site in question (the hosting and domain name were donated), I don't feel I have the right to put ads on the site. I wouldn't want to anyway - it's a better site for not having ads, and it's not like the amount of money involved is likely to make the slightest bit of difference to the quality of my life. For the same reasons I don't have ads on this site (maybe if I could make enough money from the ads to give up my day job it would be a different story but none of my websites has anywhere near that amount of traffic!)

Even so, it took me a moment to decide whether to reply with a polite "no thank you" or to press the "report as spam" button. In the end I decided on the latter course of action - it's still unsolicited commercial email even if it's buying instead of selling. And one of the last things the internet needs is more advertising. It's kind of interesting though that advertisers (or ad brokers at least) are starting to court webmasters - it always seemed to me that the supply of advertising space on the internet vastly outstripped the demand, but maybe that's changing.

Similarly, my web host recently sent me a coupon for $100 of free Google ads - I have no use for them myself (I don't think anyone interested in what I have to say here is going to find it via an ad) but I hope I'll be able to donate them to someone who does have a use for them.

Removing outliers

Monday, October 17th, 2011

If you've got a sequence of data that you want to do some statistical analysis on, but you know that some of it is bad, how do you remove the bad data? You could just remove the top 5% and bottom 5% of values, for example, but maybe you don't have any bad data (or maybe you have lots) and that would adverse affect your measurement of the standard deviation.

Suppose that you know that your dataset is supposed to follow a normal distribution (lots do). Then you could remove outliers by measuring the skew and kurtosis (3rd and 4th moments), and just repeatedly remove the sample furthest from the mean until these measurements look correct. This algorithm is guaranteed to terminate since if you only have 2 samples the skew and kurtosis will be 0. You've still got a parameter or two to tune though (how much skew and kurtosis you'll tolerate).

Import taxes to level the playing field

Thursday, October 6th, 2011

There's a big hurdle for the US manufacturing sector in that many products are much cheaper to produce in China or Taiwan. Part of the reason for this is that those countries have much less strict standards on things like pay, employee working conditions and pollution controls. Another way of looking at it is that US companies are saving money and skirting important social and environmental rules by outsourcing their manufacturing to countries which don't have these rules - with excellent consequences in terms of increased profits and cheaper products, but disastrous consequences in terms of the environment, the welfare of those who make the products, and US manufacturing jobs.

It seems to me that the US government should use its power to tax imports to level the playing field for US manufacturers by removing the incentive to manufacture elsewhere. In other words, the import tax on something should be the difference between what it costs to make something in the US and what it actually cost to make due to laxer regulations. Then, manufacturing for things sold in the US would (over time) move to the optimal locations based on where they were being sold and the where the raw materials were mined or recycled.

Suddenly making all our electronics more expensive by (maybe) a factor of 10 would be enormously disruptive so I suggest ramping up the tax gradually over a period of (say) 10 years or so. That would lessen the blow and give the US manufacturing companies some time to bootstrap. It also gives a great incentive to China to improve working conditions and emissions since doing so essentially wouldn't cost them anything (it would be covered by the corresponding reductions in import taxes).

In the long term, I would expect that the final cost of the manufactured products in question would stay about the same or even become cheaper than what they would be without these taxes. That's because as it becomes more expensive to hire people to do a menial job, it becomes more cost-effective to automate that job. The machine costs more to begin with (you need clever people to build and program it) but once it's up and running the unit cost per produced item is much lower.

There's a lot more to it than that, of course - China still has a big advantage in the expertise it has developed in building things, China sells to other places besides the US, and there are currency, debt, and trade treaty issues which further complicate matters in ways I don't completely understand. Still, I think it's an interesting idea to consider.

Fractal waveform

Tuesday, September 27th, 2011

It would be really interesting to try to make a waveform that is fractal in nature, and actually sounds interesting and musical at whatever frequency you play it at. As you speed it up, some frequencies will go so high they become inaudible and new frequencies move into the audible range at the low end. In normal music, the pitches, effects, tempos and structures all happen at different timescales but in fractal music they would all interact with each other in interesting ways.

A weird thing in Haskell

Wednesday, September 21st, 2011

Here's something odd I noticed while playing around with the Haskell programming language. Sometimes, a==b does not imply f(a)==f(b). Look:

> 1/0
Infinity
> 1/(-0)
-Infinity
> 0==(-0)
True
> (1/0)==(1/(-0))
False

Interactive IFS

Monday, September 19th, 2011

I want to write a program that allows you to explore Iterated Function System (IFS) fractals interactively by moving points around with the mouse.

There's a few different ways to do this, depending on what set of transformations you use.

IFS fractals usually use affine transformations, which encompass translations, rotations, dilations and shears. This can be done with 3 points per transformation - if one considers the points as complex numbers we have the transformation f(x)=ax + b\overline{x} + c. However, rather than controlling a, b and c directly I think it would work better to move the images of some interesting points like 0, 1 and i (i.e. move c, a+b+c and (a-b)i+c). Then the geometric interpretation of the control points would be easy to understand - they would just be the corners of a transformed rectangle.

However, there are other possible transformations. We could reduce the number of control points to 2 and disallow non-orthogonal transformations, giving f(x)=ax + b and control points 0 and 1 mapping to a and a+b.

We could move to quadratics f(x) = ax^2 + bx + c and move c, a+b+c and c+ib-a, and with 4 points we can do cubics f(x) = ax^3 + bx^2+cx+d (in which case we would probably use control points f(0), f(1), f(i) and f(1+i)).

We can even go all the way to f(x) = ax^2 + b\overline{x}^2 + c|x|^2 + dx + e\overline{x} + g (6 control points) if we wanted to go really crazy - that might be a bit unwieldy though.

I'd also like to be able to associate a colour with each transformation so that the colour of a point in the final image depends on the sequence of transformations that led to that point. Perhaps C = \alpha C_{prev} + (1-\alpha)C_{transform} for some \alpha.

Energy saving idea

Thursday, September 8th, 2011

One of the most inefficient things we do with energy is heat up water with it only to let most of that water (and most of the energy) go right down the drain when we take showers (baths are a little better because more of the energy goes into heating the house in the winter, but they do use more water).

So I think that if we were serious about wanting to save energy one thing we could do is try to encourage shorter showers by making people aware of how much energy they use. What I imagine is a little display that shows you how much energy you've used since the start of your shower (if you like you could factor in the cost of the water and sewage as well as the energy used to heat the water). For maximum effectiveness, I think the value displayed by the meter should be in units of local currency, and correspond to the amount you'd spend taking a shower of that length every day for a year - that way it feels like you're spending money really fast (of course, you'd really only be spending it at 1/365th of that rate so it's a bit of a psychological hack/cheat).

I think many people would appreciate such a device for the money it would save them, though I suppose some people might believe that long, guilt-free showers are worth that extra money.

Issues as political proxies

Tuesday, September 6th, 2011

Suppose you own a large successful business which makes money by telling customers things they want to hear - reassuring stories, comforting platitudes and advice and guidance about how to live their lives. Suppose also that, for tax reasons, you are not allowed to use your influence over your customers to push them towards voting for one particular candidate over another, and you're also not allowed to donate any of the company's profits to political parties or candidates.

However, you'd still prefer to have one candidate elected over another because your preferred candidate might lower your taxes or give you more freedom to run your business the way you want to run it, or maybe just because he's a good customer. How could you covertly support that candidate?

One thing you could do is a pick a couple of social issues which aren't fundamentally a big deal to you one way or another but which differentiate your preferred candidate from their opposition and which the opposition is unlikely to change their minds on (perhaps because they are objectively correct in their position). Then you can use your platform to tell your audience that your preferred position on said social issues is vitally important, and deciding the wrong way on them will lead the country to ruin. You don't even need to mention the names of the political candidates or the upcoming election to your audience at all - they can figure out themselves what they need to do.

For this reason I think we need to avoid making "tax deductions for political neutrality" deals - it's too easy for the organizations in question to be covertly politically non-neutral and the tricks they use cause pressure to move candidates away from objectively correct positions in this kind of issue.

How do we get there from here?

Sunday, September 4th, 2011

So we have some ideas about how we want the world to look - the next question is "How do we get there from here?" It seems to be very difficult to get anything changed at least in US politics because there are so many entrenched interests, but here's the best idea I've had about it so far.

We use this fantastic information transfer medium of the internet to get as many people interested, involved and well informed as possible. We get these people to vote in on-line elections (that are at least to begin with unofficial, non-binding and informal but are as secure as possible and only open to registered, authenticated voters). We then try to persuade politicians to take these polls into account (as well as what they suppose the opinions of the rest of the electorate to be) when making their decisions. Participating in this system costs the politician nothing at first (since when they disagree with what the poll says they can say "oh that's just the opinion of a small minority of people, most people have the opposite opinion"), but as more and more people participate in these polls they eventually become impossible to ignore ("it's the will of the people"). When politicians vote against the will of the people, we call them out on it and hopefully get them voted out of office in the next election. Once the system has sufficient momentum, we start to field candidates who run on a platform of voting according to the results of these polls rather than their own opinions. Then eventually we can transition away from having elected politicians at all and just have a system of direct delegated democracy so that the people can vote (directly or by proxy) on every piece of proposed legislation. This is much less susceptible to corruption by corporations, because decisions are not made by wealthy minority.

In the meantime, we have to do something about the media. It's no good having a democracy if people are voting against their own interests and blindly following the instructions of corporate mouthpieces. I think this is more of a US problem than a UK one the BBC is much more impartial than private media can be. Here in the US there are massive numbers of people who get all their information from Fox News and conservative talk radio which are really just fronts for organizations like Koch Industries. This is how we get public support for absurd wars and other policies that are disastrous for almost all of the people who are voting for them. The usual method we use as a society for determining which side of an argument is true is the judicial system, so I'm wondering if we can somehow make news organizations liable for things that are not true that they present as news. Don't make the penalty too big because sometimes mistakes happen but make it large enough so that the likes of Fox can't continue their current scam. And if that puts too much power in the hands of judges, then we'll need some entirely new system of checks and balances to prevent abuse there. I guess to avoid stepping on the first amendment there would have to be some kind of voluntary labeling scheme for news organizations, and we would have to learn to take with rather more salt news from sources which don't stand by what they say by participating in this scheme.

We still need to keep the economy growing as fast as possible. Unlike the conservatives, I don't think the way of doing this is reducing taxes on the rich and reducing services on the poor. I think we need more small businesses, and that there are a lot of impediments preventing people from setting up or taking over small businesses. These impediments need to be identified and removed. More small businesses means more competition for large corporations. In the US, creating a functional public healthcare system would be a great benefit for small businesses (companies in the US are can't attract the best employees without providing health insurance plans, which is much more expensive for small companies than for big ones).