20090928, 20:51  #1 
"Ben"
Feb 2007
5·727 Posts 
integer nth root code
I'm going back to look at my integer nth root code per this, and I'm running into a problem.
I'm trying variations like so: nroot(3^180,150) The actual integer root is 3, and my code's first guess is 4. So far so good. I then compute the next term in the recurrence: and since 4^149 > 3^180, the fraction in the bracket is zero and the next term in the sequence is 3. Great! But we can't stop there because this new term is not the same as the old one (hasn't converged). So now with , we get a huge term for the fraction in the bracket, the next term in the sequence is now something like 4 trillion, and the sequence never converges. What do I do in situations like this, when even a correct guess of the integer nth root produces a wildly inaccurate next guess in the recurrence? 
20090929, 04:46  #2 
"William"
May 2003
New Haven
2^{2}·593 Posts 
This isn't modular arithemetic  you are looking for the rounded off (or perhaps down) value of the real root  right?
Section 9 of Numerical Recipes says you should always bracket a root and never let your iteration method get outside of the best known bounds at any stage. I've had very good experience with the Van WijngaardenDekkerBrent method of Section 9.3 in a wide variety of numerical root finding problems. If I understand the problem correctly, from a bracket of (3,4) you should move into an endgame of picking 3 or 4, not iterating further. William Last fiddled with by wblipp on 20090929 at 04:47 
20090929, 05:06  #3  
Jun 2008
Wollongong, .au
3×61 Posts 
Quote:
Sorry, my programming skills are minimal, so I can't actually assist with the mechanics of the computation. 

20090929, 12:46  #4  
"Ben"
Feb 2007
5×727 Posts 
Quote:
Quote:
Last fiddled with by bsquared on 20090929 at 12:46 Reason: value to range... 

20090929, 13:52  #5 
Tribal Bullet
Oct 2004
DD9_{16} Posts 
In the specific case of needing the closest integer to the root, Crandall and Pomerance show that you can stop the iteration when the sequence of root estimates stops decreasing. That leads to a skewed loop where the convergence check is in the middle, after A/x_k^(n1) has been computed, and x_(k+1) only gets computed if the convergence test fails.

20090929, 19:39  #6 
Mar 2009
2·19 Posts 
As Jason said, you can stop the iteration if the sequence stops decreasing. But you have to choose a starting value greater than the real root. Normalyy you start with x0 = 2^ceil(bitsize(A)/n).
If n is large and the guesses are not very close to the root, convergence is only linear not quadratic. You should check the first few x_i for progress, otherwise it is better to use bisection steps until the iterates come close to the final result. Wolfgang 
20090929, 19:54  #7  
"Ben"
Feb 2007
5×727 Posts 
Quote:
The Van WijngaardenDekkerBrent method that wblipp suggested includes allowances for that, I think. Implementing that method in YAFU is an exercise for another day. Stuff like this is very interesting and a fun diversion but I don't believe many people use YAFU for everyday bigint calculations for which they need the fastest and most bulletproof methods. I'm still concentrating on factoring improvements for now. That said, by all means continue to find and report these things as they come up, it's very much appreciated! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
Square root of 3  Damian  Math  3  20100101 01:56 
Reference code for allinteger convolutions  jasonp  Software  17  20090129 02:25 
Cube root  mfgoode  Homework Help  10  20071005 04:12 
invalid root  junky  NFSNET Discussion  0  20040326 02:14 