Computing the limit of the sequence

[waterlookid822]

Given a real number a, we want to compute the limit of the sequence:

x1 = x - (x^3 - a) / (3x^2)

where the initial value of x is a. Start by setting x=a and computing the right-hand side. The result will be the next value of x.

Create the app that uses 0.001 as tolerance, reads a, and outputs the limit. The app stops iterating when the absolute value of the difference between the old and new values of x becomes less than the tolerance.


anyone can help me with this?

[djr33]

We don't do homework for you here. If you have a specific question we may answer it, but you can't just post your assignment here and expect that we'll do it for you.

Also, that's not just programming but somewhat advanced math.

I have no idea how your instructor expects you to approach the problem, but here's one hint: start at a and go through a loop... stop when it hits the tolerance limit.

[djr33]

In a context where that much precision is needed, that would be a problem. But the assignment just needed precision to .0001, which you have. I'm not entirely sure what type of series this is using, since I haven't worked with them for a while, and I think your interpretation may be correct, but at the theoretical level (such as how floats work) it should be about the same regardless.

But note that this is something for Java, not PHP. I don't know how Java handles non-integers or if there is a similar problem. Or were your results using Java? I just saw that you linked to the php page about floats, and I'm only familiar with PHP's number system.

[traq]

(sorry Daniel, I was trying to rewrite some bits and ended up deleting the whole thing)

yes, that was in php. it was a simple for() loop:
1) start with a = x
2) evaluate the expression
3) assign the answer to x
and start over.

as for the tolerance, I know I got answers below that, but the problem with floating point precision is that it compounds on itself (especially in loops, as you might imagine). for example, my curve looked (generally) like this, but the "correct" curve might actually be anywhere in the red (not actual results):
http://custom-anything.com/sand/curve.png
...and it may be far worse than that, I don't know.
but it's obviously enough to invalidate the results.

I don't think this problem is specific to php.
rational numbers that are exactly representable as floating point numbers in base 10, like 0.1 or 0.7, do not have an exact representation as floating point numbers in base 2, which is used internally, no matter the size of the mantissa. Hence, they cannot be converted into their internal binary counterparts without a small loss of precision. This can lead to confusing results: for example, floor((0.1+0.7)*10) will usually return 7 instead of the expected 8, since the internal representation will be something like 7.9999999999999991118....

...I especially like the "usually" part.

this would make the problem applicable to any computer programming language. I don't know what functions Java has to deal with it, but I would assume that it has precision math functions of some sort.

[djr33]

The compounding problem is a difficult one. And I'm still not sure about how other languages handle this, but it would be interesting to know more about solutions that are out there for doing accurate calculations. I once heard about a supercomputer that was calculating the value of pi to several billion digits or something, and I've always casually wondered how precise calculations like that are done since it seems that the number is not really a single item but in that situation a collection of many bits of data (no pun directly intended).

[traq]

I'm still not sure where I want to go next. Java is widely used (and Android apps would provide a comfortable transition from the web stuff I'm familiar with), but python just seems so cool. and on the other hand, why not start with C (or # or ++ (probably ++))?

anyway

possible resources

--apfloat (http://www.apfloat.org/apfloat_java/)
--LargeInteger (http://jscience.org/api/org/jscience/mathematics/numbers/LargeInteger.html)