Problems with geometric progressions (XL2000)

Topic

New Reply

Here’s a tricky one:

Sorry for the extension and the mathematical terminology; I tried to shorten the post as much as possible and to make my point clear. Used WinRar to compress and then zipped, because a ZIP compression would exceed the 100K limit and RAR is not among the allowed formats for upload.

I was playing with geometric progressions in Excel. Just in case, a geometric progression a(t) is a sequence such that a(t) = a(t-1)r, where r is the so-called common ratio (a constant), and a(1) needs to be defined as an initial condition.

The problem I found is that since Excel works with 15 significant digits, errors occur for large t: from a certain t=T on, Excel runs out of numbers to make calculations and starts rounding and cutting figures.

In my first go at it, I filled a column with values for t, and to its right I made a column for a(t), where the cells were formulated as mentioned above: a(t) = a(t-1)r. I verified there was an error indeed, which grew bigger as t grew larger.

So I thought what would happen if I used a theoretically equivalent formula for a(t): a(t) = a(1)r^(t-1). Knowing very, very little about how Excel works, I had two hypotheses for how it handles r^(t-1):

1) Excel successively multiplies r r r r…r (t-1) times. There exists a certain t=T that causes a rounded a(T); so the following term, a(T+1), will contain the error of the previous term plus an error caused by another rounding. This approach is somehow implied in my first formulation a(t) = a(t-1)r, because Excel is forced to multiply one by one each number.

2) Maybe Excel could calculate by some method r^(t-1) in a more accurate way; once it has the result, it makes the number “fit” in the 15-digit scheme. I didn’t think this made much sense, but I decided to give it a try anyway. This would imply using the second formulation: a(t) = a(1)r^(t-1).

What I found was that Excel really does make calculations in a different way, or at least the results differ significantly for t large enough. So I decided to fill one column, A, with values for t; make a second column, B, with formulation 1: a(t)_1; a third column, C, with formulation 2: a(t)_2, and a fourth column, D, with the difference of the two: z(t) = a(t)_1 – a(t)_2. I made Excel show enough decimal places, and started checking where the first non-zero difference occurred. See the attached book.

For the values of Common Ratio = 1.015 and Scale Factor a(1) = 10, the first difference occurs at t=29. I coloured the row red for easier identification. So, D33 = 0,000000000000015987211554602300. If we go forward to the last value of t I filled in column A, t=2210, we see that the difference has increased a lot: D2214 = 181,25000000000000000000. Again, this difference is supposedly attributable simply to the use of a different (but equivalent) formulation. But there’s more.

Go back to D33. Yes, the difference is small. But do check the numbers Excel displays in B33 and in D33. THEY ARE EQUAL!!!.

So I’m now completely clueless on two points: 1) how does Excel make calculations?; and 2) how can it be that to Excel two numbers are equal but their difference is NOT zero? Is this related to the binary base in which Excel stores numbers?

Finally, another detail: if you set the value of a(1) to 1, the difference in D33 IS zero; but it isn’t zero in D38, when it should be (since B38=C38). For different combinations of a(1) and r you get similar crazy results.

Any clues?

Reply | Quote

Replies

I can’t really surmise on what Excel (or anything else) does at the level of the 15th significant figure. The only thing I’d point out is that the difference you mention at D2214 represents only 10^(-11)% of the 1920822916919810 value you’re speaking of. I don’t think it really means anything to try to compare error values (or anything else) at this level of “granularity”. If you repeat the same calculations, it’s quite feasible that different error values will appear. It’s more in the category of very low level background noise, if I can use such an analogy.

Alan

Reply | Quote

Hello Alan,[indent]

---

The only thing I’d point out is that the difference you mention at D2214 represents only 10^(-11)% of the 1920822916919810 value you’re speaking of. I don’t think it really means anything to try to compare error values (or anything else) at this level of “granularity”.

---

[/indent]You’re right. But I haven’t told the whole story behind “playing with geometric progressions” . I said that in my previous post to cut things a little shorter and to avoid technicisms.

Let’s say you take out a loan, and agree to repay it in periodic installment payments which vary in geometric progression. It’s an application commonly found in financial mathematics books.

What I was trying to do is an amortization schedule for this kind of loan. What I found is that for n large, the final loan balance at t=n (n being the last moment) was not zero, as supposed to be. The accumulated amortizations at t=n didn’t amount to the original loan balance at t=0 either. Some very strange things happened: for example, for n=2000, you take out a loan of $1000 at t=0, at a periodic effective rate of 0.02. The common ratio for the payments is 1.001.
At t=2000, when you should be done, you find out you still “owe” some $944195.866.

What happens here is that again, from a certain t=T on, Excel begins to calculate erroneous values for the varying payments. Then when the periodic amount of interest is deducted from the corresponding payment to calculate the periodic amortization, the error is carried to the latter. Finally, we get an error in the balance for that period, when the innacurate amortization is deducted from the previous balance. So the beast builds up, grows bigger and stronger. It all ends up in nonsense. Of course I checked that for n small, say, up to n=700 or so, everything works just fine.

If we think in terms of time, and think of a very small period as one week, then n=2000 would imply about 500 months, i.e. roughly 42 years. It may not seem realistic that this kind of loan will appear so frequently, but independently of this particular example, I became a little paranoid about the (big!) errors one can incur in with Excel. Next I tried to track down the source of error, which seemed to be the lack of more than 15 significant digits ONLY. But then I found there was something else, and wondered if anyone around here knew what that something else was and how hard it could bite. If I knew how Excel works, I’d know how not to formulate spreadsheets so as to keep error under control. Like being a step ahead of the problem… I just wish it could be possible.

Thank you

Reply | Quote

When dealing with money, the normal solution to this problem is to round all of the intermediate calculations to two digits after the decimal. Since you have not posted a worksheet that shows what you are doing, I can not tell if this would solve your problem or if you would need some other solution.

Reply | Quote

Hi Legare,

I’m sorry for not posting the worksheet, I’m really short of time these days and I’d have to check and translate the relevant parts of it. I’d also have to delete as many cells as necesary to make it fit in the zipped 100k quota. But I think I’ll upload the translated version “as is” to a server, along with the first worksheet for everyone to download, as soon as I can get hands to it.

The solution you suggest would imply checking “Precision as displayed” in the Tools | Options | Calculation tab, right? If not, Excel would make all the calculations with all the precision anyway (if I don’t get things wrong).

Thanks for your response

Reply | Quote

ONE way would be to check Precision as Displayed. However, you can also use the ROUND function on all of the intermediate calculations.

Reply | Quote

Hello Legare,

Rounding to 2 decimal places did not work– what it did is magnify error enormously. I think I know what you mean about using 2 decimal places for money, but this is a different case. One should have Excel work with all the precision, and when everything works fine, you round the periodic installment payments and balances to 2 decimal places. I’m eager to upload the worksheet so you can see how it works. I’ll try it to be next Monday night when I do so.

Thank you!

Reply | Quote

Legare and all,

I could finally upload the files to a server. Here is a very basic web page with the files. File 1 is 383 KB; File 2 is 441 KB; and File 3 is 1269 KB. I didn’t zip them because the hosting provider doesn’t allow uploads in the ZIP format.

If there’s something you don’t understand please let me know.

I’m sorry for the delay, but I couldn’t have it sooner.

Thanks again

Reply | Quote

Since I can’t open .rar files, I cannot look at the Excel file, but Alan is correct. Since Excel computes numbers with only finite precision, each calculation may introduce a very small rounding error; if you perform repeated calculations, these errors will accumulate. If you do a search in this forum for rounding error (as a phrase), you will find several threads dealing with this.

Note: Excel doesn’t calculate a^b as a*a*….*a, it uses a faster algorithm. What the exact method is, I don’t know.

Reply | Quote

I haven’t seen the Excel internals, but being a C programmer I can offer this information:

1. Most programs on PCs store their numbers as double
s, also known as double precision floating pointer numbers. The number is stored as a mantissa and exponent. On 32 bit machines a double has a range of 15 significant digits, up to around 10^308
If you want further precision (at the expense of processing speed), some architecture supports ‘long doubles’. But they only get to you to 18 sig digits (and 10^4096) (Maybe Excel uses these?). Or both the Perl and Java languages support ‘Big Floats’ or numbers of any precision. Expect performance to plummet.
You could also explore the MathCad program (of which I have only a cursory knowledge). I believe it allows further precision.

2. Note that the last digit of a float (single precision floating point number), double or long double shoudn’t be relied on. The random number generators from many compilers use that last digit as part of the algorithm for the random number.

3. I would expect that Excel would call the C function pow for a^b. The actual algorithm that function uses is up to the compiler writer (probably Visual C++ for Excel). Again, I haven’t seen the algorithm, but would expect it to be answer = pow(e, ln(a)+ln()

PS: I couldn’t open the RAR file either. What’s it from?

Peter

Reply | Quote

Hi Hans,

I’m realizing RAR files are not as popular as I thought . Just in case, they are compressed files and can be uncompressed with any compatible file manager/archiver, for example, WinRAR. There are many 100% others out there, but I haven’t tried any.

Thanks for the tip on the algorithm. That leads me to think the second formulation of the geometric progression is better than the first one, but I can’t tell for sure yet.

Reply | Quote

FYI, I tried to unzip file using CuteZIP, which can unzip .RAR files, but get error msg (see att’d pic) whenever try to extract.

Reply | Quote

I don’t know why I suspected something like that could happen with file managers that handle both RAR and ZIP formats. I used WinRAR first to create the RAR file, then WinZip to create the final Zip file. I’ll see if I can upload the files to a server as soon as I can take care of it.

Reply | Quote

Hi diegol,

Perhaps you’d like to play with XNUMBERS – A Multi Precision Floating Point Computing for EXCEL http://digilander.libero.it/foxes/%5B/url%5D

Xnumbers is an Excel addin (xla) that performs multi-precision floating point arithmetic and extends the standard Excel precision from 15 up to 200 significant digits
That should pretty well fix your precision problems

Cheers

Cheers,
Paul Edstein
[Fmr MS MVP - Word]

Reply | Quote

Hello macropod,

Thanks for the link!!! This website is most interesting!!!! I downloaded and loaded Xnumbers, but couldn’t work things out yet. It seems I’ll have to take a careful look at the tutorial, which looks great!!

I’ll post back with news, as soon as I have any.

The other add-ins also look very tempting… Thank you!!!

Reply | Quote

Macropod, one word:

UNBELIEVABLE

With only 35 significant digits, for the same example, the final loan balance at t=2000 is -1,84718E-13, which I think can be safely considered zero . I also couldn’t resist trying the 200-digit power, and the result is overwhelmingly happy.
When I do the upload, I’ll include the RAR file in my first post (in simple XLS format), the former 15-digit Excel precision amortization schedule, and the new book with the add-in-dependent formulae that yield awesome results.

I recommend that everyone give this one a try, it’s truly amazing. Calculations may take twenty seconds or so, depending on the number of cells to calculate, but it’s nothing compared to what you get. The documentation is very easy to read.

I want to thank all the people that put up with me and helped me solve the problem

Reply | Quote