Page 1 of 2 12 LastLast
Results 1 to 15 of 16
  1. #1
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Problems with geometric progressions (XL2000)

    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? <img src=/S/scratch.gif border=0 alt=scratch width=25 height=29>
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  2. #2
    Platinum Lounger
    Join Date
    Nov 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    5,016
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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. <img src=/S/2cents.gif border=0 alt=2cents width=15 height=15>

    Alan

  3. #3
    Plutonium Lounger
    Join Date
    Mar 2002
    Posts
    84,353
    Thanks
    0
    Thanked 29 Times in 29 Posts

    Re: Problems with geometric progressions (XL2000)

    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.

  4. #4
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Sydney, Australia, New South Wales, Australia
    Posts
    251
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Re: Problems with geometric progressions (XL2000)

    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 <code>double</code>
    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([img]/forums/images/smilies/cool.gif[/img])

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

    Peter

  5. #5
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    Hello Alan,
    <hr>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".<hr>
    You're right. But I haven't told the whole story behind "playing with geometric progressions" <img src=/S/grin.gif border=0 alt=grin width=15 height=15>. 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 <img src=/S/smile.gif border=0 alt=smile width=15 height=15>
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  6. #6
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    Hi Hans,

    I'm realizing RAR files are not as popular as I thought <img src=/S/doh.gif border=0 alt=doh width=15 height=15>. Just in case, they are compressed files and can be uncompressed with any compatible file manager/archiver, for example, WinRAR. There are many 100% <img src=/S/free.gif border=0 alt=free width=30 height=15> 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.
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  7. #7
    Bronze Lounger
    Join Date
    Nov 2001
    Location
    Arlington, Virginia, USA
    Posts
    1,394
    Thanks
    0
    Thanked 3 Times in 3 Posts

    Re: Problems with geometric progressions (XL2000)

    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.

  8. #8
    Super Moderator
    Join Date
    May 2002
    Location
    Canberra, Australian Capital Territory, Australia
    Posts
    5,054
    Thanks
    2
    Thanked 417 Times in 346 Posts

    Re: Problems with geometric progressions (XL2000)

    Hi diegol,

    Perhaps you'd like to play with XNUMBERS - A Multi Precision Floating Point Computing for EXCEL http://digilander.libero.it/foxes/

    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 <img src=/S/dizzy.gif border=0 alt=dizzy width=15 height=15>
    That should pretty well fix your precision problems <img src=/S/meltdown.gif border=0 alt=meltdown width=15 height=15>

    Cheers
    Cheers,

    Paul Edstein
    [MS MVP - Word]

  9. #9
    Uranium Lounger
    Join Date
    Jan 2001
    Location
    South Carolina, USA
    Posts
    7,295
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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.
    Legare Coleman

  10. #10
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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.
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  11. #11
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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!!! <img src=/S/thumbup.gif border=0 alt=thumbup width=15 height=15>
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  12. #12
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  13. #13
    Uranium Lounger
    Join Date
    Jan 2001
    Location
    South Carolina, USA
    Posts
    7,295
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

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

  14. #14
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    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!
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

  15. #15
    5 Star Lounger
    Join Date
    Mar 2002
    Location
    Buenos Aires, Argentina
    Posts
    877
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Problems with geometric progressions (XL2000)

    Macropod, one word:

    <big>UNBELIEVABLE</big> <img src=/S/exclamation.gif border=0 alt=exclamation width=15 height=15>

    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 <img src=/S/grin.gif border=0 alt=grin width=15 height=15>. 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
    <img src=/w3timages/blue3line.gif width=33% height=2>
    <img src=/S/flags/Argentina.gif border=0 alt=Argentina width=30 height=18> <big><font color=4682b4><font face="Comic Sans MS">Diegol</font face=comic></font color=4682b4> </big>

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •