Sunday, August 30, 2009

Padé Approximants

I spent a little time looking into Padé approximants, including how well they work for root-finding.  These are ratios of polynomials which are used as approximations to other functions.  For instance, for both polynomials of order 2, the form is a + bx + cx21 + dx + ex2 .  Note the 1 in the denominator is chosen to avoid the ambiguity of being able to multiply through by a constant.

Just as with the derivation of a Taylor series, one can determine the coefficients of the Padé approximate by equating the derivatives of the desired function to the derivatives of the approximate.  For instance, a is always equal to F(0).

If the order of the denominator is 0 (i.e., the denominator is 1), then the Padé approximants are just the Taylor series for the function.  I looked at the approximate of order (0,1) as well (a1 + dx, which is F2F - F′·x), but found that it converged worse that the Taylor series of order 1.

The useful one seems to be the approximant of order (1,1).  Since it has three free coefficients, it is equivalent to using a Taylor series up to order 2 (the x2 term).  In my experiments the Padé gave closer approximations than the Taylor series.  It is also easier to work with (especially if using rational numbers) than the Taylor series since there is no squared term.  For the same reason, it is easier to solve for x and use the approximation to solve for a root.

Newton's method for root-finding equates to writing the Taylor expansion for a function out to order 1, then inverting it to obtain an expression for x.  Obviously using another term in the Taylor expansion would give more accuracy, but since that produces a quadratic equation, the solution for x has a square root and is very messy (and in many cases, it is the square root function itself we are trying to solve in the first place).  Since the Padé approximate of order (1,1) only has linear terms of x, it can still be easily solved, and provides quicker convergence to the root than Newton's method.

Once I had written out the equation for the correction term using this method (which is (F′α + F″2F′)-1, where α is the needed correction to the function value), I saw that it was the same as that given by Halley's method.  What I find interesting is, if you read the Wikipedia article, you'll see the derivation of Halley's method is completely different than the process I went through.  The convergence of the expression from two different approaches increases my confidence that it is a good method for root-finding.  As an added bonus, when computing with rational terms, the size of the terms grows more slowly than from Newton's method.

The State of the Blog

I'm sure anyone who isn't fascinated by math has noticed I haven't posted about parenting or green living lately.  Does that mean I haven't been thinking about those things?  Or does it mean things have been going well so I haven't had a reason to reflect on them?  Well, we did replace the air conditioning, so we did think about green living, but I don't think there was anything new there.  Overall, I think it just reflects that I've been busy.

Sunday, August 16, 2009


I recently came across the computer science concept of memoization.  What's cool is that I had made some suggestions on designs at work that amount to the same thing.

In general, memoization refers to having a computer function remember the problems it's already solved, and just return the answer again if it recognizes the problem, rather than compute it again, as most software does.  The common example is the factorial function.  Since the factorial is the product of all the numbers up to the argument, on the way to, say 6!, you will compute all the factorials less than 6.  Usually the function would loop over all the numbers and multiply them together.  Instead, a memoized version would have stored all the results up to the highest argument it had previously seen, and then only compute those beyond that (storing the new results) if necessary.

One type of object-oriented class that I had proposed is a smart Angle class.  Since angles can be represented in many different ways, I wanted to be able to get any version the calling software wanted, without knowing what version it had been stored in.  In addition to radians and degrees, an angle can be (and often is in our work) stored as the combination of sine and cosine values.  Besides being able to use an angle without knowing what format it was in originally, I suggested that the other representations should be left uncomputed, but once they were asked for, the result should be stored to avoid unnecessary further computations.  Clearly this can been seen as memoization of the conversion.

In the general case, the "hit rate" of a memoized function may not be that high, depending on the number and valid range of the inputs.  However, for an object whose data never changes once it is created, essentially one of the inputs has been fixed, raising the chance that the same result will be requested repeatedly.  (In my design, each Angle object would be for a particular angle.  If the value of the variable changed, a new Angle object would be created to store it.)

By the way, I'm fascinated with the idea of "smart numbers" in computer programs - numbers as objects (or other collections of data, if not object-oriented) which store more than just their value, or that store exact representations in alternate formats.  The Angle example given, quadratic irrationals, storing numbers as rationals or continued fractions instead of decimal, and numbers that store their own error bounds, are all concepts that I've thought about over the years.  If anyone knows where one of these concepts has been used in a real program, I'd be interested to hear about it.

Thursday, August 13, 2009

A Tale of Two Sequences

Last week I came home happy one day because of a simple little math expression.  The Fibonacci sequence has the cool property that for each term, if a prior term's index is a divisor of the current index, then that term is also a divisor of the current term.  So, for example, F15 is divisible by F3 and F5 (and an additional factor).  More formally, a divides b implies Fa divides Fb.  There are other sequences with this property, including 10n − 1 (or any bn − 1).  But the Fibonacci sequence is a linear recurrence relation (each term is the sum of the two previous terms) and the sequence of one less than powers of ten is exponential.  I figured there must be some way to characterize what types of sequences can have this property.

Well, I still don't know if there are other types of sequences with this property, but I do now know why these two types share it.  I came across this relationship in a paper I found online, and as soon as I saw it I realized it could be generalized.  They are actually the same type, and can each be expressed as the other.  For instance, 10n − 1 can also be obtained using Fn = 11·Fn-1 − 10·Fn-2, and each linear recurrence sequence can also be made into a difference-of-powers sequence, though the base "b" may not be rational.

As with many techniques in math and physics, once you know there is an equivalence, it is trivial to set up a set of equations in that form and figure out the coefficients.  So, one the one hand I feel that I should have tried it sooner, but on the other I feel that if it were widely known then I would have run across mention of it sooner.  Regardless, I am happy to know a little bit more about a set of sequences which I find fascinating (more properties will get their own post one day).

Sunday, July 26, 2009

What is the Nature of Waste?

First, don't take my ruminations in this post to mean that I am going to become a profligate consumer of things because I no longer believe in scarcity.  I've got a natural inclination to be frugal, and that includes use of resources on general principles.

I was looking at a friend's recirculating waterfall.  It is very pretty, but I asked myself if it was a waste of electricity just to entertain us.  The conventional answer would be yes.  But then I realized that Nature does the same thing, using solar energy on the ocean and lakes to lift water up and then drop it to run down the streams, rivers, and waterfalls to the ocean.  Thus I arrived at the central question of this post: Why do we consider certain things to be wasteful when done by man, but not when occurring in nature?

Another example is a mountain spring.  Where I was last week there was a natural spring with good water.  Of course it trickles out of the mountain continuously, and except for the small amount caught when a person is there, it runs down and into a river and down the mountain.  Now if I were to run my pump to bring water out of the aquifer, and left my hose to run continuously into the nearest stream, most people would say I was wasting a tremendous amount of a precious resource.  Again, one example is naturally occurring while the other is performed by man, but what is the difference in the net effect?

We can ask the question not only in cases where man uses a resource, but where he fails to capture it as well.  Since Nature is using energy to lift water which is then running downhill, are we negligent in not capturing every bit of that energy which is being "wasted" in friction with the rocks?  Should every waterfall be diverted and generate hydroelectric energy?  What about all the solar energy which falls all over the earth?  Are we negligent in not harvesting it?  For that matter, we can even ask about all the solar energy which misses the earth in all the other directions.  Is it going to "waste"?

My answer to this question is that it must not be the nature of the event itself which characterizes it as wasteful, but its impact on what are considered limited resources.  Since Nature has plenty of solar energy available, using it inefficiently to keep the water cycle going is not wasteful.  Since we have limited energy available, using it to no net effect is wasteful.  This leads to the conclusion that if we figured out how to harness copious energy, and weren't short of the materials to do so, and figured out how to use it without side effects like CO2 or excess heat, that then there would be nothing inherently bad about using as much as we wanted.

An interesting and relevant corollary of this is that you can't place blame on previous generations for waste of resources they didn't yet know were limited.  The fact is, almost everything we do is wasteful, but just like the cycles in nature, we find them necessary to life.  Every time I go hiking or cycling and return to the starting point, I've wasted energy which must be replenished with food, which has an impact on resources to grow and ship.  Any trip taken just for entertainment is a complete waste outside of our own mental health.  And yet, we find all these things necessary to make life worth living - just as Nature must use Her resources to support life in general.

So, my conclusion?  Do try to be smart in your use of resources, so we don't run out.  But don't feel guilty about using a reasonable amount to make your life worth living.  After all, if there is any point to our existence at all, it is to enjoy the world around us.

Sunday, July 12, 2009

Observing Instead of Judging

This morning I was thinking about something my daughter had done the night before - leaving some food uneaten.  I was reflecting this morning and thought "I don't like food wasted, but at least she knows to stop eating when she's no longer hungry, which is a good habit".  But then I realized, why do I need to decide whether her actions are good or bad at all?  Does every thing in the world that I see or hear about need to be judged by me as to whether it is good or not?  In most cases, my opinion is either irrelevant, or is not needed.

So, whereas the standard advice would be to "try and find the good in everything", from now on I will try and remember to avoid the thoughts "this is good" or "this is bad" - some things just are.  I know this will be a hard habit to break.  As parents we expect to have to evaluate every situation to determine what actions we will take to help "form" our kids.  Since we have stopped trying to form our kids to let them learn on their own, it seems that making the judgment when I am not going to act on it only serves to build my frustration, and negatively affect my internal image of my kids.

Note, for you who aren't radical unschoolers, this does not mean that I am not parenting, and it does not mean that I can't have an opinion on things.  It just mean that if I say something to my kids about something they are doing, I will state the effect it is having on me (It bothers me when...), but I will not tell them that it is "bad", and I will not try and coerce them to change.  I will just hope that they will take that information on the effects of their actions into account later, along with all the other factors that may influence their decision.

Wednesday, July 1, 2009

Rational Approximation to Roots Continued...

This morning I was able to complete the symbolic expression for the limit of the series.  For large x, the expression (1 + a(bx-c))x can be expanded using the binomial theorem to 1 + x ⋅ a(bx-c) + 12 x (x-1) (a(bx-c))2 + 16 x (x-1) (x-2) (a(bx-c))3 + … ; only keeping the highest power of x in both the numerator and the denominator, they cancel and it becomes ∑ 1n! (ab)n

This is where I was last night, but this morning I realized that it could be a MacLaurin series.  A little browsing in the CRC book and sure enough, it is the series for ey, with y=ab.  So, the actual limit is eab, or solving for ab, we want ab = ln N; indeed, ln 2 is around .693, and 9/13 is a good approximation for it.  Now that I know exactly what irrational number I am trying to have for the ratio ab to converge to any given N, I can use continued fractions to choose good a and b to approximate that ratio.

By the way, to get an exact result at x=1, c should be set to b - aN-1.

However, using Excel to plot the actual values as a function of x, it becomes clear that the convergence becomes slow for even N around 10.  (7, 10, 3) gives values within .015 of 2, but the first few terms when converging to 10 are as low as 8!  One can mitigate this somewhat by raising c such that the values for x=1 and x=2 are poor (do we really need an approximation to the 1st root?), bringing the errors for the next terms down, but this only reduces the error by about half.

So, if you happen to need very high roots, like the 200th root of 10, then this is still an interesting technique.  On the other end, for roots of numbers less than 3, all the approximations are very good.  Since this is not limited to integers, should you need to generate roots of, say, 1.2, this technique will give extremely close approximations.

I did realize that the convergence can be greatly improved by raising the order of x in both the numerator and denominator, effectively creating additional terms which only have an effect for small x.  But, since I started this exploration with the observation that there was a sequence which was easy to remember and compute in my head, I decided to stay with that theme and stop here, rather than create much more complicated expressions.  (At this point, were any of the non-math-interested folks still reading, they would go "What, you mean the previous equations weren't complicated?!" :-)

Tuesday, June 30, 2009

Rational Approximation to Roots

I've been playing with a new math observation. It started when I noticed the following sequence for the nth roots of 2: (1 + 717)2 ≈ 2;
(1 + 727)3 ≈ 2; (1 + 737)4 ≈ 2; (1 + 747)5 ≈ 2. This can be generalized to (1 + 7(10x-3))x = ((10x + 4)(10x-3))x ≈ 2.

So, is this an isolated fluke, or are there expressions like this for all roots? It turns out there are multiple expressions (1 + a(bx-c))x which converge to any N for large x. For 2, the combinations (2, 3, 1), (5, 7, 2), (7, 10, 3) and (9, 13, 4) give increasingly closer convergence to 2. The ratio ab seems to be about .694, but I haven't yet mastered the limit expressions to get a symbolic expression for the number. I've found through trial and error combinations for roots of 3, 4, 5, and 10 - however, the convergence seems slower for larger N, meaning that the approximations are very poor for the lower roots (those you're more likely to use).

So, I haven't yet determined if this discovery is significant or trivial, but if you should happen to be at the sort of party where people are impressed by mental math (I haven't yet found one), you can rattle off that the 7th root of 2 is roughly 1 + 987. Or, more likely, you'll just have a handy small-number ratio for a root if you're doing math by hand.

Wednesday, June 24, 2009

Desire vs. Obligation

We've just returned from the SHINE unschooling conference in Niagara Falls, Ontario.  I had a relevation, but it didn't come at the conference.  It came as we arrived home.

For ten days, we had been touring, seeing museums and natural wonders, and attending the conference, all very enjoyable.  As we neared home, though, my thoughts started to turn to what things would be piled up and need to be done to catch up from being away.  And that's when I realized that part of the reason I'd enjoyed myself so much was that I'd been doing things I wanted to do, whereas in my normal life I almost exclusively do things I feel I ought to do.  I have reached a point where I run my life almost exclusively based on perceived obligations.

I constantly choose to do tasks based on the idea that I will feel better when things have been completed.  I've found in particular I often feel unhappy if I didn't accomplish anything after work, no matter what other enjoyable activities I've done.  In reality there is a never-ending list of other tasks to be done, so the pleasure is short-lived.  The alternative, of course, is to not delay happiness, but do things which are enjoyable right now.  I'm not sure how I developed such a strong sense of accomplishment as reward, but it seems consistent with Puritan values, so I'm guessing it's not that rare in American society.

As they say, realizing you have a problem is half the battle.  So, what am I doing with my revelation?  Well, I'm trying to simply choose at every opportunity the action which will actually bring my pleasure in the doing, not in the finishing.  There are still things which will have to be done, but I intend to do them at the time that I look at them and think, "I would really be happier to have this done right now", not with the anticipation that I will be happier in the future if I don't have to do it then.

One other component of this change in outlook is to reduce the number of things which are perceived as obligations.  Keep up with email, especially mailing lists?  Don't have to.  Blogs I'm subscribed to?  No obligation to read anyone.  All the filing, cleaning, and reading around the house?  I've been not doing it and feeling guilty for a long time, so if I continue to not do it but lose the guilt, I'm ahead, right?  In return I hope I'll find the time to hike, ride bikes, play with the kids, and go to events where before, I might have felt I needed to stay home and get work done.

Sunday, June 7, 2009

Bullet Trains are Sexy, Basic Math is Not

I've been thinking about the statements by Amtrak's CEO Joseph Boardman and Chairman Tom Carper that the way to go faster by train is to improve the slow sections and delays, and the negative reactions accusing them of having no vision (on Infrastructurist, and Chicago news), and I just can't let it go. The thing is, the Amtrak guys are right. Unfortunately, the best solution is not always the one that will sell politically.

Consider a train journey between two cities 180 miles apart. 160 miles of track are wide open, no congestion, etc. Near the two cities and other congestion points, there are 20 miles of track requiring slow speeds and waiting. The train goes 80 mph when it can, but only averages 10 mph through the congested sections. The trip will take 4 hours.

Option one for reducing travel time is to put in a high speed train. It now goes 160 mph on the open rail, but is subject to the same congestion near the cities. Travel time: 3 hours.

Option two to save the same hour is to improve the average speed in the congested sections from 10 to 20 mph. Which solution is more cost effective? Which one is sexier and easier to get public support for?

I haven't gone and researched the history, but I'm willing to bet that the European countries and Japan already had their trains running without significant congestion and delays before they offered their high-speed trains. When I lived in Switzerland 20 years ago, I don't recall trains having to crawl through sections of track, nor coming to a stop and waiting, aside from a few minutes just outside a station. I've ridden Amtrak and these experiences are typical.

I hope that if we do put in high-speed trains that we at least give them improved, dedicated track all the way into the stations. Otherwise it's just option one above.

I hope it doesn't sound as if I don't want high-speed rail in the US. It would be great. But I think there are some necessary precursors that we need to do first.

Wednesday, June 3, 2009

Where Do Hybrid Vehicles Make the Most Sense?

I like to keep up with the development of various types of hybrid vehicles through sites like autobloggreen. A common observation is that hybrid powertrains will give the biggest benefit to vehicles which stop and accelerate frequently. UPS/FedEx trucks, garbage trucks, and city buses are being developed as prototype heavy hybrid vehicles.

I think there is a group of vehicles where the benefits of a hybrid powertrain should be even greater, though: vehicles which run their engines to power on-board systems while they are stationary. I'm thinking of bucket trucks, various lifts, and a lot of hydraulic construction vehicles. There is an office building under construction near mine at work, and I see (and hear) a lot of equipment with the engine running while it holds a load or a person works on a platform. Autobloggreen recently reported on delivery of a hybrid propane delivery truck which can run the delivery pump from the batteries, eliminating the need to leave the truck running during the transfer.

In many of these vehicles, the accessory system doesn't even need power all the time. For instance, the operator of a bucket truck may not need to move the bucket for minutes, once it is positioned. But, currently the engine runs to keep the hydraulic pump ready. By contrast, batteries don't need to use power just to be at the ready. Note that the batteries don't need to be able to power the on-board systems for very long - the engine can still run whenever the batteries need to be recharged, but it doesn't need to run continuously.

There are many more vehicles which are used in this way. If you are alert to it, you will find work vehicles with running engines frequently. Police are another example. I understand that there are enough computers and radios in a police cruiser that the engine needs to run to power them all while the officer works with them (plus, they want the air conditioning to stay on).

I suspect that the construction and utility industries provide a noticeable portion of our fuel use, and although some equipment will have continuous high power requirements, reducing what we can would be worthwhile.

Friday, May 29, 2009


I know I'm breaking the first rule of blogging* by putting my various unrelated interests into one blog. However, since I expect my readership to be maybe three, if I made a blog for each topic, the average number of readers for each would be .5. So, feel free to use the titles and tags to skip things you aren't interested in.

So, what is the idea of this blog? From time to time I've come up with observations or insights, and I've felt that they were being lost, not benefiting anyone besides myself. I'm not keeping a lab notebook nor writing elsewhere for publication, as a traditional academic would (not that I think any of my thoughts are actually at the forefront of the field). So I'm going to use this as a forum (or at least a notebook, if no one else is reading) to record my ideas.

And what areas am I interested in? Well, I'm a cyclist, including recumbent and tandem. I've also become a bit of a bike and pedestrian advocate (I've already proposed and gotten passed a change to state law). Under my wife's influence I've become interested in organic food, green living, and alternate transportation. We also unschool. My other major interest is recreational math, usually number theory. I play a lot with primes, factoring, and recognizing squares. I prefer to work algorithms by hand, to understand them, rather than see if I can use them on a big number.

I plan to keep this blog about ideas in those various areas, and not specifically about me. So, I won't be boring you with what's happening to me, only with the ideas I have.

Next up, the first post - will it be any good?

*I have no idea what the rules of blogging actually are, or what order they would be in.