Sqrt and divison with recursion
Hello guys! i want to make a calculator of addition/substitution/multiplication/division/power/square root only with recursion. I have made for +,-,* and ^ but i did not figure out how to do the functions for division and square root. If you can help it'd be great. Thanks in advance!
Last edited on
If to consider only unsigned int then it is not hard to write recursive function for division
|
|
Last edited on
(1) what is the diferrence between signed and unsigned
(2) what const means?
(3) can you do anything for the square root?
If you can't heplp me with theese thanks anyway for the help provided!
(2) what const means?
(3) can you do anything for the square root?
If you can't heplp me with theese thanks anyway for the help provided!
const is a typo.:)
As for signed and unsigned then for example -6 / 3 = -2 while - 6 / - 3 = 2.
As for signed and unsigned then for example -6 / 3 = -2 while - 6 / - 3 = 2.
Signed is negative values and positive values within a set range.
Unsigned is only positive in a set range so therefore unsigned can store more positive numbers than signed.
Also your square root would be really hard with recursion...what would you get as an ouput if you did sqrt( 15 )?
Or I guess you could increment by decimal values instead of integer values but that might be a very slow process.
*edit
By the way const means constant as in the value is not modified/read-only.
Unsigned is only positive in a set range so therefore unsigned can store more positive numbers than signed.
Also your square root would be really hard with recursion...what would you get as an ouput if you did sqrt( 15 )?
Or I guess you could increment by decimal values instead of integer values but that might be a very slow process.
*edit
By the way const means constant as in the value is not modified/read-only.
Last edited on
I just found an easy way you could do sqrt that I didn't even know about tbh.
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
*edit it looks weird when I paste it..lol
Basically you do something like
sqrt of 15 to 6 signifigant values ( can be anything the more you have the more accurate ) would be
s = 15
x0 = 6 * 100 = 600
x1 = 1/2( x0 + s/x0 )= 1/2( 600 + 15/600 ) = 300.0125
x2 = 1/2( x1 + s/x1 ) = 1/2( 300.0125 + 15/300.0125 ) = 150.0312
x3 = 1/2( x2 + s/x2 ) = 1/2( 150.0312 + 15/150.0312 ) = 75.0656
x4 = 1/2( x3 + s/x3 ) = 1/2( 75.0656 + 15/75.0656 ) = 37.6327
x5 = 1/2( x4 + s/x4 ) = 1/2( 37.6327 + 15/37.6327 ) = 19.0156
x6 = 1/2( x5 + s/x5 ) = 1/2( 19.0156 + 15/19.0156 ) = 9.9022
As you can see that isn't the correct value you want to go till xn is almost the same if not the same as xn - 1 so I'll keep going The reason you need more for 15 vs that large number is because its such a small value.
x7 = 1/2( x6 + s/x6 ) = 1/2( 9.9022 + 15/9.9022 ) = 5.7085
x8 = 1/2( x7 + s/x7 ) = 1/2( 5.7085 + 15/5.7085 ) = 4.1679
x9 = 1/2( x8 + s/x8 ) = 1/2( 4.1679 + 15/4.1679 ) = 3.8834
x10 = 1/2( x9 + s/x9 ) = 1/2( 3.8834 + 15/3.8834 ) = 3.8730
x11 = 1/2( x10 + s/x10 ) = 1/2( 3.8730 + 15/3.8730 ) = 3.8730
sqrt( 15 ) is approx 3.8730
let me check the calculator that my computer comes with...
3.8730
| wiki wrote: |
|---|
| To calculate \sqrt{S}, where S = 125348, to 6 significant figures, use the rough estimation method above to get x_0 = 6 \cdot 10^2 = 600.000. \, x_1 = \frac{1}{2} \left(x_0 + \frac{S}{x_0}\right) = \frac{1}{2} \left(600.000 + \frac{125348}{600.000}\right) = 404.457. x_2 = \frac{1}{2} \left(x_1 + \frac{S}{x_1}\right) = \frac{1}{2} \left(404.457 + \frac{125348}{404.457}\right) = 357.187. x_3 = \frac{1}{2} \left(x_2 + \frac{S}{x_2}\right) = \frac{1}{2} \left(357.187 + \frac{125348}{357.187}\right) = 354.059. x_4 = \frac{1}{2} \left(x_3 + \frac{S}{x_3}\right) = \frac{1}{2} \left(354.059 + \frac{125348}{354.059}\right) = 354.045. x_5 = \frac{1}{2} \left(x_4 + \frac{S}{x_4}\right) = \frac{1}{2} \left(354.045 + \frac{125348}{354.045}\right) = 354.045. Therefore, \sqrt{125348} \approx 354.045 \,. |
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
*edit it looks weird when I paste it..lol
Basically you do something like
sqrt of 15 to 6 signifigant values ( can be anything the more you have the more accurate ) would be
s = 15
x0 = 6 * 100 = 600
x1 = 1/2( x0 + s/x0 )= 1/2( 600 + 15/600 ) = 300.0125
x2 = 1/2( x1 + s/x1 ) = 1/2( 300.0125 + 15/300.0125 ) = 150.0312
x3 = 1/2( x2 + s/x2 ) = 1/2( 150.0312 + 15/150.0312 ) = 75.0656
x4 = 1/2( x3 + s/x3 ) = 1/2( 75.0656 + 15/75.0656 ) = 37.6327
x5 = 1/2( x4 + s/x4 ) = 1/2( 37.6327 + 15/37.6327 ) = 19.0156
x6 = 1/2( x5 + s/x5 ) = 1/2( 19.0156 + 15/19.0156 ) = 9.9022
As you can see that isn't the correct value you want to go till xn is almost the same if not the same as xn - 1 so I'll keep going The reason you need more for 15 vs that large number is because its such a small value.
x7 = 1/2( x6 + s/x6 ) = 1/2( 9.9022 + 15/9.9022 ) = 5.7085
x8 = 1/2( x7 + s/x7 ) = 1/2( 5.7085 + 15/5.7085 ) = 4.1679
x9 = 1/2( x8 + s/x8 ) = 1/2( 4.1679 + 15/4.1679 ) = 3.8834
x10 = 1/2( x9 + s/x9 ) = 1/2( 3.8834 + 15/3.8834 ) = 3.8730
x11 = 1/2( x10 + s/x10 ) = 1/2( 3.8730 + 15/3.8730 ) = 3.8730
sqrt( 15 ) is approx 3.8730
let me check the calculator that my computer comes with...
3.8730
Last edited on
Thanks for searching this answer giblit, but i am a begginer programer and my calculator project was my idea so i am not obiged on it. This method seems too advanced for my mathematical knowings and i think that for the moment i will keep sqrt() function provided by math.h.I thought it could be a more easier method :d. But again i thank you for your work.
Last edited on
It's not that advanced of a method its basic algebra
S = x (value being sqrt'd ) so sqrt of 15 means s = 15
x0 = Signifigant digits * 10^2
Then you do x1 -> answer
xn = 1/2( ( xn - 1 ) + ( 15 / xn - 1 ) )
Begin with an arbitrary positive starting value x0 (the closer to the actual square root of S, the better).
Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
Repeat step 2 until the desired accuracy is achieved.
It can also be represented as:
x_0 \approx \sqrt{S}.
x_{n+1} = \frac{1}{2} \left(x_n + \frac{S}{x_n}\right),
\sqrt S = \lim_{n \to \infty} x_n.
As you can see when I did 600 for sqrt( 15 ) it took a while vs as if I did like 10 which would look like
x0 = 1 * 10^2 = 100
x1 = 1/2( 100 + 15/100 ) = 50.075
x2 = 1/2( 50.075 + 15/50.075 ) = 25.1872
x3 = 1/2( 25.1872 + 15/25.1872 ) = 12.8914
x4 = 1/2( 12.8914 + 15/12.8914 ) = 7.0275
x5 = 1/2( 7.0275 + 15/7.0275 ) = 4.5810
x6 = 1/2( 4.581 + 15/4.581 ) = 3.9277
x7 = 1/2( 3.9277 + 15/3.9277 ) = 3.8734
x8 = 1/2( 3.8734 + 15/3.8734 ) = 3.8730
x9 = 1/2( 3.8730 + 15/3.8730 ) = 3.8730
same answer but took less loops to get it.
S = x (value being sqrt'd ) so sqrt of 15 means s = 15
x0 = Signifigant digits * 10^2
Then you do x1 -> answer
xn = 1/2( ( xn - 1 ) + ( 15 / xn - 1 ) )
Begin with an arbitrary positive starting value x0 (the closer to the actual square root of S, the better).
Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
Repeat step 2 until the desired accuracy is achieved.
It can also be represented as:
x_0 \approx \sqrt{S}.
x_{n+1} = \frac{1}{2} \left(x_n + \frac{S}{x_n}\right),
\sqrt S = \lim_{n \to \infty} x_n.
As you can see when I did 600 for sqrt( 15 ) it took a while vs as if I did like 10 which would look like
x0 = 1 * 10^2 = 100
x1 = 1/2( 100 + 15/100 ) = 50.075
x2 = 1/2( 50.075 + 15/50.075 ) = 25.1872
x3 = 1/2( 25.1872 + 15/25.1872 ) = 12.8914
x4 = 1/2( 12.8914 + 15/12.8914 ) = 7.0275
x5 = 1/2( 7.0275 + 15/7.0275 ) = 4.5810
x6 = 1/2( 4.581 + 15/4.581 ) = 3.9277
x7 = 1/2( 3.9277 + 15/3.9277 ) = 3.8734
x8 = 1/2( 3.8734 + 15/3.8734 ) = 3.8730
x9 = 1/2( 3.8730 + 15/3.8730 ) = 3.8730
same answer but took less loops to get it.
Last edited on
I think i understand a little if i am right plese announce me but i think the general algorithm would be( from your explain):
n->programmer choosed number(integer positive)
num->user choosed number( waiting to be sqrt'd)
x0=1*n^2
x1=1/2(x0 + num/x0)
.................................
x(n-1)=1/2(x(n-2)+num/x(n-2))=sqrt(num)
And if i am not wrong, as well as n is bigger the answer is more aproximate.
I took some randome cases and that's my conclusion i hope it's right. Thank you again for your work anyway.
n->programmer choosed number(integer positive)
num->user choosed number( waiting to be sqrt'd)
x0=1*n^2
x1=1/2(x0 + num/x0)
.................................
x(n-1)=1/2(x(n-2)+num/x(n-2))=sqrt(num)
And if i am not wrong, as well as n is bigger the answer is more aproximate.
I took some randome cases and that's my conclusion i hope it's right. Thank you again for your work anyway.
yeah but n should be 10 though I didn't try other numbers so oculd be very well any number.
Last edited on
Even if it's 10 the algorithm is very useful. Thank you very much for the help , it would have been a lot heavier for me to find this myself.
An interesting feature of this algorithm is that it converges very rapidly towards the solution, once it is close. It gives roughly double the number of correct significant digits with each iteration.
Example:
n = 4
x0 = 4 (or any reasonable estimate).
x1 = 2.5
x2 = 2.05
x3 = 2.00060975609756097560975609756
x4 = 2.00000009292229466031325963976
x5 = 2.00000000000000215863811094172
x6 = 2.00000000000000000000000000000
Notice the number of zeros after the decimal point, indicating correct digits in each iteration.
Example:
n = 4
x0 = 4 (or any reasonable estimate).
x1 = 2.5
x2 = 2.05
x3 = 2.00060975609756097560975609756
x4 = 2.00000009292229466031325963976
x5 = 2.00000000000000215863811094172
x6 = 2.00000000000000000000000000000
Notice the number of zeros after the decimal point, indicating correct digits in each iteration.
Topic archived. No new replies allowed.