| Author |
Message |
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
 Posted: 06 May 2005 04:49:29 pm Post subject: |
|
|
When working with iterations to calculate the square roots of numbers, I found that as the numbers became large, the number of iterations required to take "x" down to "√x" at a precision of ten digits (rounded) increased substantially. The problem was this: Looping the equation a finite number of times would result in a greater lack of accuracy for larger inputs. However, I didn't want to run the iteration endlessly, either. So, I set out to find an equation that would determine the number of iterations necessary to calculate the square root of any given whole number to at least ten digits.
Before I could devise such an equation, I needed to gather a sample space.
What I found was startling:
# of Iterations (x)[font="courier new"]____Mininum whole number yielding "x" iterations
1[font="courier new"]___________________1
4[font="courier new"]___________________2
5[font="courier new"]___________________3
6[font="courier new"]___________________5
7[font="courier new"]___________________29
8[font="courier new"]___________________136
9[font="courier new"]___________________490
10[font="courier new"]__________________1590
11[font="courier new"]__________________6795
12[font="courier new"]__________________32671
13[font="courier new"]__________________116880
14[font="courier new"]__________________449984
15[font="courier new"]__________________2000000
16[font="courier new"]__________________5000000
17[font="courier new"]__________________10000001
18[font="courier new"]__________________14000002
19[font="courier new"]__________________490000002
20[font="courier new"]__________________2000000000
21[font="courier new"]__________________7000000000
22[font="courier new"]__________________32198999996
23[font="courier new"]__________________128868884986
24[font="courier new"]__________________449989999978
25[font="courier new"]__________________1999999999962
Unfortunately, after running multiple regressions with different ranges within these samples, I can't achieve any coherent equation without creating a tremendous amount of residual from every element. I tried rounding the obvious integers to their obvious amounts, but nothing seems to work. Is anyone else willing to help me continue this venture?
Square Root Calculator:
[font="courier new"]Input A:A
For(B,0,?
.5(Ans+A/Ans
End:Ans
Iteration Counter:
[font="courier new"]Input A
DelVarBA→C
Repeat C=√A
B+1→B
.5(C+A/C→C
End:B
I'll continue to work on this.
Last edited by Guest on 06 May 2005 04:51:40 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 06 May 2005 05:41:44 pm Post subject: |
|
|
That thing grows faster than any exponential, could be some sort of x^x or x! thing?
Edit: it grows slower than either of those, at least in the range of that table.
However, calculating the number of iterations, even if it were simple, would be slower than calculating the square root (of course, the iteration method is also slower than calculating the square root).
Last edited by Guest on 06 May 2005 07:53:53 pm; edited 1 time in total |
|
| Back to top |
|
|
DigiTan
Unregistered HyperCam 2
Super Elite (Last Title)
Joined: 10 Nov 2003
Posts: 4468
|
| Posted: 07 May 2005 12:14:53 am Post subject: |
|
|
| I started using the same method in the Sonic physics code and got the same results. Maybe you can use a Fourier transform in matlab and get an exponential property out of it. I don't know how helpful that would be since this isn't periodic. This method doesn't have a name does it? |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 07 May 2005 01:49:53 am Post subject: |
|
|
Newton-Raphson, huh?  Let me tell you, it's not the only way to calculate square roots iteratively.  Look into Halley's or something similar.
This may help. Also this.
thornahawk
P.S. DigiTan, I seriously doubt the data Supergoose generated would lend itself to Fourier analysis. It's really wonderful, but it has its limits...
Last edited by Guest on 07 May 2005 02:13:00 am; edited 1 time in total |
|
| Back to top |
|
|
DigiTan
Unregistered HyperCam 2
Super Elite (Last Title)
Joined: 10 Nov 2003
Posts: 4468
|
| Posted: 08 May 2005 01:12:12 am Post subject: |
|
|
| I was afraid of that. Isn't there some kind of fancy windowing method they use to work with these non-repetitive functions? I think those business types use it for profit projections and such. |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 08 May 2005 01:34:47 pm Post subject: |
|
|
Thats scary how fast that grows. I wonder what kind of function that is. anybody tred graphing it?  |
|
| Back to top |
|
|
leofox
INF student
Super Elite (Last Title)
Joined: 11 Apr 2004
Posts: 3562
|
| Posted: 08 May 2005 02:11:11 pm Post subject: |
|
|
| i graphed it with the plot functions. it looks a bit like the fibonacci numbers, but different.. |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 08 May 2005 02:55:16 pm Post subject: |
|
|
hmmm....
Edit:
whoa I never noticed the "?" in the for loop. everything I've ever read says that " " and "?" aren't used for anything. how do you use the "?" in a loop
Last edited by Guest on 08 May 2005 02:58:07 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 08 May 2005 03:08:32 pm Post subject: |
|
|
The "?" is to be replaced with the number of iterations you want in your loop. It also acts as a placeholder for the specific equation I want.
My next post will show the minimum number (decimals included) for which "x" iterations are found.
Last edited by Guest on 23 Jun 2005 08:09:05 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 08 May 2005 04:52:22 pm Post subject: |
|
|
| What if you find out that the equation involves a square root itself? |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 08 May 2005 06:52:04 pm Post subject: |
|
|
Supergoose wrote: The "?" is to replaced with the number of iterations you want in your loop. It also acts as a placeholder for the specific equation I want.
My next post will show the minimum number (decimals included) for which "x" iterations are found.
[post="50089"]<{POST_SNAPBACK}>[/post]
oh, I get it now. Also anybody else notice that numbers 2,3,4, and 5 of the sequence are all prime? I'm not sure about the all of the others, although dsoem obviously aren't, since I have't checked but even that is interesting |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 09 May 2005 05:00:04 pm Post subject: |
|
|
| As someone I don't know once said "That's nothing special. 80% of the first five natural numbers are Fibonacci numbers." |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 09 May 2005 06:23:02 pm Post subject: |
|
|
| I like that quote |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 10 May 2005 01:23:59 am Post subject: |
|
|
*sigh*... apparently, the links were not noted. Let me spell it out then.
The first point of it was the relation between your starting value and the nth iterate x(n):
|(√b-x(n))/√b| ≤ 2((√b-x(0))/(2√)^(2^n)
where x(0) is your starting value for the iteration.
Since you'd want that expression to the left of that inequality be ~ 10^-12, plug that in there, and treat the above as an equality to solve for n.
In short, the answer to Sir Robin's question is in the affirmative. And yes, elfprince13, that really is a rapid type of growth. The proper term for this is "double-exponential growth"
The second point was that you are using very poor seed values for Newton's iteration (i.e. the number itself). Your time spent in cycling through Newton's method for an inordinate amount of iterations would be better spent using a good seed value (e.g. a rational approximant, or (gasp!) Taylor polynomial), and then polishing the result with the iteration. That, or see the second link I gave. Read it well.
DigiTan, windowing would be akin to tapering off the astounding growth characteristic of this set. Not very appropriate for this circumstance.
And I have given up trying to convince those "business types" that something that is inherently chaotic will not subject itself well to something that analyzes periodicity. And they wonder why their forecasts tend to suck... :(
thornahawk
Last edited by Guest on 10 May 2005 01:26:44 am; edited 1 time in total |
|
| Back to top |
|
|
DigiTan
Unregistered HyperCam 2
Super Elite (Last Title)
Joined: 10 Nov 2003
Posts: 4468
|
| Posted: 10 May 2005 02:07:48 pm Post subject: |
|
|
Is that basicly the same as this method?...
I put it in a Sonic routine and so far it seems to behave the Supergoose described.
Last edited by Guest on 10 May 2005 02:08:06 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 10 May 2005 03:32:56 pm Post subject: |
|
|
That's exactly the same.
I think a better way to calculate square roots would be something like
Code:
{1,1
While e10>2Ans(2)^2
Ans(1)+{N,1}Ans(2
End
Ans(1)/Ans(2
Although I'm not sure if it's faster, I just like continued fractions. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 11 May 2005 02:36:08 am Post subject: |
|
|
That algorithm you gave, Sir Robin, was in the first link I posted. It is called the Bhaskara-Brouckner algorithm.
I really like Halley's method more:
(in the style of Supergoose's first routine):
Code:
Input A:A
For(B,0,?
Ans(3A+Ans²)/(A+3Ans²)
End:Ans
Coupling that with a starting approximation that is good to ~3 digits, the number of iterations will be ~3. :)
thornahawk |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 11 May 2005 06:50:39 am Post subject: |
|
|
| But my method has a well-defined boundary for when it should stop |
|
| Back to top |
|
|
|
Math and Science => Technology & Calculator Open Topic
