> urticator.net

  About This Site
> Domains

> Numbers

  Powers and Fractions
  Notes About Squares
  Decimal Expansions
  Repeat Length Again
  Number Maze
  Intrinsic Nature of Primes
  Other Topics
> Other Topics (2)

  Machine Language
  Pascal's Triangle
  Dead Reckoning
> Exponentials
  Multiplication in Base 10
  The Multiplication Table

> Exponentials, Continued
  The Algorithm
  Error Analysis

Exponentials, Continued


So, now we know how to get the remainder into the range 00.1. That seems pretty good, but is it good enough? Let's look at the formula side of things and see.

The exponential (base e) can be written as a nice power series.

ex = sum ( xn/n! )

That series isn't the only possible starting point for a formula, but it's the only one I'm going to talk about. It's simple, and converges rapidly, and is what we want to use. We can't use all the terms, of course, so we have to truncate the series at some point. But, if we truncate after the linear term, the range turns out to be way too small; and if we truncate after the cubic term, the formula turns out to be way too complicated; and that pretty well settles it. With a conversion factor for base 10 included, here's what we have.

10x = ex ln 10 ~ e2.303x ~ 1 + 2.303x + (2.303x)2/2

Now, although I haven't said so in so many words, the goal here is to find a good inverse for the logarithm method, which provides results to five decimal places. So, since the argument x is a logarithm, we can assume it will be accurate to five places; but then, since the formula has a substantial linear term, the best we can hope for is that the result will be accurate to five places too.

What does it mean to be accurate to five places? If I tell you that log 2 is .30103, you know that's within 510-6 of the true value; so maybe if the result of the formula is within 510-6 of the true value (10x), it will be accurate to five places? Well, no. No matter how close the two numbers are, there's always some probability that they'll come out different when you round them to five places.

1.00000 49999
1.00000 50001

Still, requiring the error to be less than 510-6 is a pretty good rule of thumb; let's go with that for now and worry about the details later. Then, working through the numbers, it turns out that the formula is valid out to x = 0.018 and a bit.

So, surprise! The range 00.1 is not good enough, and we need to find a third piece. The simplest one that we haven't already used is log 3, which is .47712; but we already know how to dispose of multiples of 0.1, so we can think of it as roughly 0.077. Then, if we allow adding or removing one or two copies of that, that gives us the following table, just like the table for log 2 except that we don't need a grid to see how it works.


So, given a number in the range 00.1, we can add or remove copies of log 3 and get a remainder in the range 00.023. That's still not quite good enough, but now, fortunately, there's a trick we can do. Suppose the original number is 0.075. According to the current scheme, we should subtract 0.054 to get remainder 0.021, which is too large but we could equally well subtract 0.077 to get remainder -0.002! That works perfectly; the formula, as it happens, is valid out to x = -0.018 too. So, by choosing the nearest number from the table instead of the next smallest, we can get the remainder into a range where the formula is valid.

And there you have it! The detailed algorithm that I'll present in the next section may look different, but it's really just a rearranged and optimized version of what I've outlined here. In particular, the pieces and the formula are exactly the same.

In case you're wondering, here are a few last details about the range.

  • It doesn't matter how you choose the nearest number. If, e.g., the original number is .06560, you can think of it as 0.065 and say that it's closer to 0.054; you can round it to 0.066 and say that it's closer to 0.077; or you can use full precision and discover that it's closer to .05424 than to .07712 after all. Even in the worst case, the remainder is never larger than .01211, which is fine.
  • It doesn't matter that log 2 isn't exactly 0.3. To dispose of multiples of 0.1, we might need to use as many as five copies of log 2. Five copies of log 2 is inexact by .00515, so in the very worst case, the adjusted remainder might be as large as .01726 which is a bit of a close call, but still fine.



  See Also

  Error Analysis

@ September (2006)