Archive for May, 2007

Continued Fractions

Saturday, May 19th, 2007 Nigel Jones

Once in a while something happens that makes me realize that techniques that I routinely use are simply not widely known in the embedded world. I had such an epiphany recently concerning continued fractions. If you don’t know what these are, then check out this link.

As entertaining as the link is, let me cut to the chase as to why you need to know this technique. In a nutshell , in the embedded world we often need to perform fixed point arithmetic for cost / performance reasons. Although this is not a problem in many cases, what happens when you need to multiply something by say 1.2764? The naive way to do this might be:

uint16_t scale(uint8_t x)
 uint16_t y;
 y = (x * 12764) / 10000;
 return y;

As written, this will fail because of numeric overflow in the expression (x * 12764). Thus it’s necessary to throw in some very expensive casts. E.g.

uint16_t scale(uint8_t x)
 uint16_t y;
 y = ((uint32_t)x * 12764) / 10000;
 return y;

Our speedy integer arithmetic isn’t looking so good now is it?

What we really want to do is to use a fraction (a/b) that is a close approximation to 1.2764 – but (in this case) has a numerator that doesn’t exceed 255 (so that we can do the calculation in 16 bit arithmetic).

Enter continued fractions. One of the many uses for this technique is finding fractions (a/b) that are approximations to real numbers. In this case using the calculator here, we get the following results:

1: 1/1 = 1
3: 4/3 = 1.3333333333333333
1: 5/4 = 1.25
1: 9/7 = 1.2857142857142858
1: 14/11 = 1.2727272727272727
1: 23/18 = 1.2777777777777777
1: 37/29 = 1.2758620689655173
1: 60/47 = 1.2765957446808511
1: 97/76 = 1.2763157894736843
1: 157/123 = 1.2764227642276422
2: 411/322 = 1.2763975155279503
1: 1801/1411 = 1.2763997165131113
1: 3191/2500 = 1.2764

We get higher accuracy as we go down the list. In this case, I chose the approximation (157 / 123) because it’s the highest accuracy fraction that has a numerator less than 255. Thus my code now becomes:

uint16_t scale(uint8_t x)
 uint16_t y;
 y = ((uint16_t)x * 157) / 123;
 return y;

The error is less than 0.002% – but the calculation speed is dramatically improved because I don’t need to resort to 32 bit arithmetic. [On an ATmega88 processor, calling scale() for every value from 0-255 took 148,677 cycles for the naive approach and 53,300 cycles for the continued fraction approach.]

Incidentally, you might be wondering if there are other fractions that give better results than the ones generated by this technique. The mathematicians tell us no.

So there you have it. A nifty technique that once you know about it will make you wonder how you got along without it for all these years.


H1-b visas and Economics 101

Tuesday, May 1st, 2007 Nigel Jones

USA Today has a story today about how 123,000 applications were received within 48 hours of this years H1-b visa lottery being opened on April 1. Given that there are 65,000 visas granted a year, there seems to be a large mismatch between supply and demand. Although the USA Today story talks about some of the sexy positions (Supermodels! Complete with alluring photograph!), the reality is that most of these applications are for the fields of electronics and computing, including embedded systems.

This topic interests me, in part because I came to the USA on a similar visa program (actually an E2 – but that’s another story).

Anyway, whenever this topic comes up, there’s normally some quote from a high tech industry executive explaining that they simply can’t get enough talented folks – and hence the need for the program. Whenever, I see this argument advanced, I’m always struck by the failure of the journalist to ask a basic question – namely “What would you do if the program was eliminated?” I suspect that the honest executive would answer:

  1. Lobby like mad to get it reinstated
  2. Pay what I had to to get the talent I needed
  3. Look to put the work where the talent is (i.e. ship it overseas).

Whereas I could probably discourse for a long time on answer 1, it’s the other two that intrigue me.

The reality today is that enrollment in engineering is dropping. If one was to look at non first / second generation immigrant enrollment, I’d hazard a guess that it has all but collapsed. This is despite the fact that engineering in general (and electrical engineering in particular) is always one of the highest paying jobs upon graduation, with recent graduates earning about $65K, versus the $30K earned by your typical liberal arts major. So, what would happen if these salaries doubled? Would this be enough to attract more home grown talent in to the industry? Economics 101 would suggest that if you raise the salaries high enough then supply will rise to meet the demand. The question is, by how much would salaries have to rise?

Economics 101 also suggests that as the price of a good / service rises, it is highly likely that the consumer will look for a substitute. At present this works by bringing folks in on the H1-b program. If the program was eliminated, then I assume that this would be done by shipping more work overseas.

I guess this leads me to the point of my post. The USA prides itself on its capitalist approach – and the belief that the free market is inherently the best way to solve all (OK, most) problems. As a result, Americans normally abhor government interference in the market place. But isn’t that exactly what is being done here?

If we genuinely believe in the free market, then the H1-b visa program should be abolished. Salaries would rise for engineers, more students would study engineering – and more work would go overseas. I have no idea whether the end result would be beneficial to engineers or not. It would however be ideologically consistent.

The economic purists might argue that the H1-b visa should be scrapped in the sense that anyone who wished to work here should be allowed to do so. I agree that this is also ideologically consistent. However, the reality is that the USA limits immigration in all fields. Thus to be truly consistent this would require the USA to do the same for all jobs – which is tantamount to saying there are no limits on immigration – something which isn’t going to happen.