New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect results from 'nthRoot' #397

Closed
FSMaxB opened this Issue Jun 17, 2015 · 10 comments

Comments

Projects
None yet
2 participants
@FSMaxB
Collaborator

FSMaxB commented Jun 17, 2015

There are numerical instabilities in the nthRoot function, see the following example:

$ ./repl.js 
> math.eval('sqrt(2^1000)/2^500');
1
> math.eval('nthRoot(2^1000,2)/2^500');
2.5822498780869086e+120
> 

I haven't looked at the code of nthRoot or at possible algorithms yet.

Are there any algorithms that handle those instabilities better?

@josdejong

This comment has been minimized.

Owner

josdejong commented Jun 17, 2015

Thanks! Turns out there is an infinite loop protection with a too low maximum count (here in the code). iMax is 100, but in your example there are 506 iterations needed. We can at least increase iMax to say 1000 or 10000. I'm not sure whether it would be safe to just remove the loop protection.

@josdejong josdejong added the bug label Jun 17, 2015

@FSMaxB

This comment has been minimized.

Collaborator

FSMaxB commented Jun 17, 2015

Under what conditions would this be an infinite loop? If I understand it correctly, this comes down to the question if there are parameters for which the algorithm doesn't converge (not mathematically but numerically ).

If it's not sure if this converges, iMax should be set to something that doesn't take too long on slow hardware (let's say 10-20 seconds).

Another suggestion: Throw an error when iMax is reached and provide an optional third parameter for the maximum number of iterations.

I think an error should be thrown because otherwise the result is incorrect and you have no way of knowing that it is.

@FSMaxB FSMaxB changed the title from Numerical instabilities in `nthRoot` to Incorrect results from 'nthRoot' Jun 17, 2015

josdejong added a commit that referenced this issue Jun 17, 2015

@josdejong

This comment has been minimized.

Owner

josdejong commented Jun 17, 2015

I've just pushed a fix

@FSMaxB

This comment has been minimized.

Collaborator

FSMaxB commented Jun 17, 2015

Thanks.

Should this issue be closed now or after the release of v2?

@josdejong

This comment has been minimized.

Owner

josdejong commented Jun 17, 2015

I've changed the max iterations to 10000 (it's typically between 5 and 20, and for very small or large values it can be in the order of 500).

The function now throws an error when the maximum iterations is reached. However, so far I couldn't come up with a case where this happens. I think adding an optional third parameter will be a bit overkill, the method should just work.

I also saw that the function didn't work at all for small values ( < 1e-16 ) due to the epsilon. I've fixed that too by comparing x against xPrev in the loop.

The issue can stay open until the issue is applied in the first next release (will automatically be closed by github then). We could also do a bugfix for the v1 branch.

@FSMaxB

This comment has been minimized.

Collaborator

FSMaxB commented Jun 17, 2015

Is throwing an error API-Breaking?

@josdejong

This comment has been minimized.

Owner

josdejong commented Jun 17, 2015

I would say not, it's fixing a bug.

@FSMaxB

This comment has been minimized.

Collaborator

FSMaxB commented Jul 8, 2015

I've ported this fix to v1_develop.

@josdejong

This comment has been minimized.

Owner

josdejong commented Jul 9, 2015

Thanks Max, I will do a bugfix release this weekend (just back from vacation - it's time to get this v2 finally finished).

@josdejong josdejong closed this in da86ca0 Jul 12, 2015

@josdejong

This comment has been minimized.

Owner

josdejong commented Jul 12, 2015

I've released v1.7.1 including this bug fix.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment