FLW_FTW

Challenge: Roots

22 posts in this topic

There are several ways to calculate the square root of a number. Some of them can be found here: [url="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots"]Wikipedia[/url]

Calculate the square root of a number n without using any predefined libraries. EG: Don't just submit sqrt( n );

Extra credit: Calculate the root of a number n using only bitwise/logical operations. Edited by FLW_FTW

Share this post


Link to post
Share on other sites
[spoiler]

There are a lot of boring ways to do this. I thought about, and then I remembered my favorite method:
http://en.wikipedia.org/wiki/Fast_inverse_square_root

[code]#include <stdio.h>
int main(int argc, char *argv[]) {
float num, ans;
printf("number: ");
scanf("%g", &num);
float half = 0.5f*num;
int i = *(int*)&num;
i = 0x5f3759df - (i>>1);
num = *(float*)&i;
ans = num*(1.5-half*num*num);
printf("%g\n", 1/ans);
return 0;
}[/code]

This isn't incredibly accurate (gives the square root of 49 as 7.00465 for example) but it's main purpose is for fast computer graphics - I believe it was first seen in the Quake source code - where incredible precision doesn't matter that much.

As a challenge to all of you now, figure out how it actually works. ^_^

[/spoiler]
1 person likes this

Share this post


Link to post
Share on other sites
I have gotten so much mileage out of this diagram over the years...

The attached image is a Turing machine for finding square roots of integers (the initial tape should contain the argument in unary format):

Share this post


Link to post
Share on other sites
[quote name='rainwater_stillicide' date='08 October 2009 - 03:43 PM' timestamp='1255034631' post='346064']
I have gotten so much mileage out of this diagram over the years...

The attached image is a Turing machine for finding square roots of integers (the initial tape should contain the argument in unary format):
[/quote]

Nice, umm.. could you explain that in terms I might understand? I ain't following what it's supposed to represent.

And I will try this challenge when I'm rested.. Been working long hours lately and can't think too straight.

Share this post


Link to post
Share on other sites
In math, they use logarithms to solve roots of any number.
Do you count logarithms as pre-defined libraries?

Share this post


Link to post
Share on other sites
Here is my method of finding the square root: :rolleyes:
[attachment=4199:sqrRoot.py.txt]

Sample output:
= denotes python's sqrt answer
=~ denotes my approximate answer
[code]
sqrt(-787) =~ 28.0535714286i
sqrt(289) = 17.0 =~ 17
sqrt(494) = 22.2261107709 =~ 22.2272727273
sqrt(914) = 30.2324329157 =~ 30.2333333333
sqrt(105) = 10.246950766 =~ 10.25
sqrt(796) = 28.2134719593 =~ 28.2142857143
sqrt(998) = 31.5911379979 =~ 31.59375
sqrt(701) = 26.4764045897 =~ 26.4807692308
sqrt(704) = 26.5329983228 =~ 26.537037037
sqrt(108) = 10.3923048454 =~ 10.4
sqrt(336) = 18.3303027798 =~ 18.3333333333
sqrt(167) = 12.9228479833 =~ 12.9230769231
sqrt(906) = 30.0998338866 =~ 30.1
sqrt(133) = 11.5325625947 =~ 11.5416666667
sqrt(304) = 17.4355957742 =~ 17.4411764706
sqrt(535) = 23.1300670124 =~ 23.1304347826
sqrt(947) = 30.7733651069 =~ 30.7741935484
sqrt(262) = 16.1864140562 =~ 16.1875
sqrt(950) = 30.8220700148 =~ 30.8225806452
sqrt(323) = 17.9722007556 =~ 17.9722222222
sqrt(454) = 21.3072757527 =~ 21.3095238095
[/code] Edited by SwartMumba
1 person likes this

Share this post


Link to post
Share on other sites
I am disappointed no one looked at what I did. :sad:
1 person likes this

Share this post


Link to post
Share on other sites
[quote name='SwartMumba' date='03 November 2009 - 01:46 AM' timestamp='1257230776' post='346931']
I am disappointed no one looked at what I did. :sad:
[/quote]

It's very interesting if I could understand it.


edit::: oh, and by the way. I checked with my TI-84. It seems python's native square root is much more accurate.

edit::: And whats "f'(B)(x-B)"?? inverse function?



I added comments to your code, check the comments.
[quote][code] Let x equal the value you want to find the square root of.
Let b be a value near x, which you know the square root of.
Let f(x) = (x)^0.5
then,g(x) = f(B) + f'(B)(x-B) # By the way smartmumba, f' is inverse function?
in my code, a = sqrt(B)'''[/code][/quote]

Those damn smileys, for the first time, I finally understood why boards have disable smileys option. Except this board doesn't have it. Edited by bcrscahh198987

Share this post


Link to post
Share on other sites
[quote name='bcrscahh198987' date='13 November 2009 - 05:07 AM' timestamp='1258106834' post='347321']

edit::: And whats "f'(B)(x-B)"?? inverse function?
[/quote]

That would be the derivative of f times (x-B).

Share this post


Link to post
Share on other sites
I got a simple but inefficient method of doing it.

[quote]How do you find the square root of a number by hand?
What about cube roots?

The square root of a number is just the number which when multiplied by itself gives the first number. So 2 is the square root of 4 because 2 * 2 = 4.

Start with the number you want to find the square root of. Let's use 12. There are three steps:

Guess
Divide
Average.
... and then just keep repeating steps 2 and 3.

First, start by guessing a square root value. It helps if your guess is a good one but it will work even if it is a terrible guess. We will guess that 2 is the square root of 12.

In step two, we divide 12 by our guess of 2 and we get 6.

In step three, we average 6 and 2: (6+2)/2 = 4

Now we repeat step two with the new guess of 4. So 12/4 = 3

Now average 4 and 3: (4+3)/2 = 3.5

Repeat step two: 12/3.5 = 3.43

Average: (3.5 + 3.43)/2 = 3.465

We could keep going forever, getting a better and better approximation but let's stop here to see how we are doing.

3.465 * 3.465 = 12.006225

That is quite close to 12, so we are doing pretty well.

[url="http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html"]http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html[/url] [/quote]
[quote][url="http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html"]http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html[/url][/quote]


That's probably the simplest way to do it, the problem would probably be how many times are you going to loop or repeat the steps until you feel it's correct. The bigger the number you want to calculate for, you'll want to use more loops.

The second problem , that I can think of, is the part with guessing. How are you going to guess? If you try to find the root of 1, how is the computer going to guess properly? Edited by bcrscahh198987

Share this post


Link to post
Share on other sites
Anyway, here's my method in ruby

[spoiler][code]puts "Type in a number, not letters or symbols."
a = gets

a = a.to_f #converts the variable "a" from a string to float
b = a/2 #this is the part where I guess what the root is and declare the variable b.

15.times do
c = a/b #this part is necessary to help with the next step
b = (c+B)/2 #this step makes the variable "b" into the new guess.


end

puts b

# the method for this calculations of roots is found at
# http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html
# This code was made by bcrscahh198987 [/code][/spoiler]


here's my sample output
[code]
494 ~= 22.61107708929
914 ~= 30.2324329156619[/code]


This means I can make my answers as accurate as I want it by adjusting the amount of times of the loop.

In this case it's 15 times.


and by the way, my answers are much more accurate than SwartMumba. haha :) Edited by bcrscahh198987

Share this post


Link to post
Share on other sites
So there's 3 methods so far.



Fast inverse square,

Linearization

Averaging.





Any other approach?

Share this post


Link to post
Share on other sites
[quote name='intimidat0r' date='14 November 2009 - 03:05 PM' timestamp='1258229106' post='347378']
[quote name='bcrscahh198987' date='13 November 2009 - 05:07 AM' timestamp='1258106834' post='347321']

edit::: And whats "f'(B)(x-B)"?? inverse function?
[/quote]

That would be the derivative of f times (x-B).
[/quote]


Using derivatives huh? I'm not in calculus yet. I only understand it to be slope of a curve or tangent to the curve.

Oh yeah, How do I get rid of those smileys?? Edited by bcrscahh198987

Share this post


Link to post
Share on other sites
oooh, this should be a fun challenge. i'll finally be able to apply what i've learned in calc II in a real world situation.

i'll work on this and submit my code later, but my general strategy will be: [spoiler]start by finding the Maclaurin series of sqrt(x), and determine how far from 0 i can still consider it to be sufficiently accurate. once the difference between my square root and the actual square root becomes greater than epsilon (i'll use the resolution of a float on a 32-bit machine) i find the taylor series at that number, and repeat the process to give my function a larger domain where it's accurate than just around 0. after I do that a few times, i move from paper to laptop, code it up, then see how the actual library functions do it.[/spoiler]

also swartmumba, i'm wondering why your sqrt() function is giving a result for a negative input without using imaginary numbers, hehe.

Share this post


Link to post
Share on other sites
[quote name='zandi' date='16 December 2009 - 11:10 PM' timestamp='1261026622' post='348449']
oooh, this should be a fun challenge. i'll finally be able to apply what i've learned in calc II in a real world situation.

i'll work on this and submit my code later, but my general strategy will be: [spoiler]start by finding the Maclaurin series of sqrt(x), and determine how far from 0 i can still consider it to be sufficiently accurate. once the difference between my square root and the actual square root becomes greater than epsilon (i'll use the resolution of a float on a 32-bit machine) i find the taylor series at that number, and repeat the process to give my function a larger domain where it's accurate than just around 0. after I do that a few times, i move from paper to laptop, code it up, then see how the actual library functions do it.[/spoiler]

also swartmumba, i'm wondering why your sqrt() function is giving a result for a negative input without using imaginary numbers, hehe.
[/quote]

There is an imaginary number!
Look at the end.
sqrt(-787) =~ 28.0535714286[color="#ff0000"]i[/color] <-- see i

Share this post


Link to post
Share on other sites
alright, i think i've got it:

[spoiler]
i was going to use the taylor series of sqrt(x) to calculate it, but it only converged for a pretty small neighborhood of values, so i went looking for other methods of calculating it. then, i came across the identity sqrt(x) = e^(1/2)ln(x), which reduced calculating the square root to the problem of calculating a logarithm, which i knew had an easy to derive taylor series. so, i derive the taylor series for ln(x), but then it would only converge for an input between 0 and 2. at first i thought i was back where i started, but after noticing [url="http://en.wikipedia.org/wiki/Natural_logarithm#Numerical_value"]this[/url] on wikipedia (just before the "high precision" section) i realized i could manipulate the input so one half would be in a range i could compute for, and the other half was computable from constants in math.h. here's the ln() and sqrt() functions:

[code]
double ln(register double x)
{
register int n = 1;
register int exponent = 0;
double result = 0.0;
register double sum = 0.0;

while(!(0<x && x<2))
{
x/=10;
exponent++;
}

for(; n<=100; n++)
{
sum += (1.0/n)*pow(-1,n+1)*pow(x-1,n);
}

result = sum + exponent*M_LN10;

return result;
}



double my_sqrt(double x)
{
double result = 0.0;

result = pow(M_E, 0.5*ln(x));

return result;
}
[/code]

[/spoiler]

as far as i've checked, it's as accurate as sqrt(), though i haven't bothered to code for negative input.
1 person likes this

Share this post


Link to post
Share on other sites
Nice Zandi.

I think it was in MITs calc HW questions - or maybe Calculus Early Transcendentals - that I read some computers use this method to calculate the square root.

+1 Edited by SwartMumba

Share this post


Link to post
Share on other sites
[quote name='SwartMumba' date='25 December 2009 - 11:23 PM' timestamp='1261801401' post='348697']
Nice Zandi.

I think it was in MITs calc HW questions - or maybe Calculus Early Transcendentals - that I read some computers use this method to calculate the square root.

+1
[/quote]

thanks. the nice part about the series is that for the range it converges, you know it is exactly equal to the function. the problem is with computers you can't calculate an infinite sum, just find an approximation, so you have to hope it converges quickly enough. in this case it did, but i'm sure for other functions this approach wouldn't work so well.

Share this post


Link to post
Share on other sites
print('Enter a number:');
nbr=input();
aprox=0.0001;
dif,root=0.0001*0.0001-nbr,0.0001
print nbr,'\'s root is',nbr**0.5;

Share this post


Link to post
Share on other sites
The bitwise sqrt operation.

[spoiler]
I love this famous piece of code.
[code]
float Sqrt(float x) {
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
x = 1/x;
return x;
}
[/code]
[/spoiler]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now