21 replies to this topic

[FLW_FTW]

There are several ways to calculate the square root of a number. Some of them can be found here: Wikipedia

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, 04 October 2009 - 12:30 AM.

[intimidat0r]

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

#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;
}

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.

[rainwater_stillicide]

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):

Attached Files

•  int_sqrt.jpg   229.65K   70 downloads

[PurpleJesus]

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):

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.

[bcrscahh198987]

In math, they use logarithms to solve roots of any number.
Do you count logarithms as pre-defined libraries?

[intimidat0r]

It's trivial to write your own logarithm function anyway.

[SwartMumba]

Here is my method of finding the square root:
 sqrRoot.py.txt   1.95K   27 downloads

Sample output:
= denotes python's sqrt answer
=~ denotes my approximate answer

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

Edited by SwartMumba, 31 October 2009 - 07:58 PM.

[SwartMumba]

I am disappointed no one looked at what I did.

[bcrscahh198987]

I am disappointed no one looked at what I did. :sad:

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'((x-"?? inverse function?



I added comments to your code, check the comments.

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(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' /> + f'(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />(x-<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />  # By the way smartmumba, f' is inverse function?
	in my code, a = sqrt(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />'''

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, 13 November 2009 - 05:21 AM.

[intimidat0r]

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

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

[bcrscahh198987]

I got a simple but inefficient method of doing it.

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.

http://mathforum.org...rt.by.hand.html

http://mathforum.org...rt.by.hand.html

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, 27 November 2009 - 03:10 PM.

[bcrscahh198987]

Anyway, here's my method in ruby

Spoiler

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+<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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

here's my sample output

494 ~= 22.61107708929
914 ~= 30.2324329156619

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, 27 November 2009 - 03:35 PM.

[bcrscahh198987]

So there's 3 methods so far.



Fast inverse square,

Linearization

Averaging.





Any other approach?

[bcrscahh198987]

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

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

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, 27 November 2009 - 03:38 PM.

[zandi]

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.

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

[SwartMumba]

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.

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

There is an imaginary number!
Look at the end.
sqrt(-787) =~ 28.0535714286i <-- see i

[zandi]

ah, didn't notice that. i suppose it's alright then.

[zandi]

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 this 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:

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;
}

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

[SwartMumba]

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, 25 December 2009 - 11:24 PM.

[zandi]

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

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.