April 30th, 2010, 07:24 AM

Best square root way
What is the best/fastest/shortest way to find square root?
Mine is kinda lame :
Code:
scanf("%d",&num);
for(i=1;i<num;i++)
if(i*i==num)
sroot=i;
April 30th, 2010, 07:28 AM

#include <math.h> (or <cmath> for C++)
double d = sqrt(9);
Tain't likely you are going to beat the guys who do this for a living...
April 30th, 2010, 07:30 AM

ye,but i know there are some good ways to do it manually without using functions.
April 30th, 2010, 07:34 AM

And the reason for doing so is what?
April 30th, 2010, 07:56 AM

Well,its fast and easy but i think we should use them only after we understand how they work and be able to build them by ourselves.
April 30th, 2010, 08:01 AM

That is a fine attitude, but somehow I doubt an employer is going to pay you to take endless hours to understand how all library code works before taking the time to use it. If you are still in school (or on your own time), then I applaud your interest in finding out how things work, but if you are in a work environment you need to accept that since code maitenance is often well over 50% of the cost of the code (including, in many cases, even the hardware costs!) and except in extremely unusual circumstances any percieved performance gain is impossible to even measure, let alone make a difference, a single line call to a standard library function is always going to be the "best/fastest/shortest way to find square root".
I have tinkered with doing my own binary math to do in software what the hardware is already doing for me, so I am sympathetic to 'reinventing the wheel' as a way to understand what is going on, but keep what I said above in mind in an operational environment!
April 30th, 2010, 08:18 AM

Am not in a hurry ,am first year on informatics&telecommunications so am just taking my time to understand the basic stuff as deep as i can,i will worry bout time/code efficiency later.
Since most languages are more or less same thing with differences mainly in syntax i thought that i should build up a solid logic and understanding of programming so everything else flow gently.
Besides that,has anyone other ways finding square root without using function?
April 30th, 2010, 08:20 AM

Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
April 30th, 2010, 08:28 AM

i always try that first ,then i ask questions (:
If i ask questions that means what i found there wasn't satisfying.
April 30th, 2010, 08:47 AM

Newton method can be used.
April 30th, 2010, 06:43 PM

Originally Posted by deicider
ye,but i know there are some good ways to do it manually without using functions.
Not if you want "best/fastest/shortest" method on hardware with an FPU (i.e. all modern desktop systems). x86 FPU for example has a single instruction (FSQRT) for performing square root operations, and your library will use that. Short of inline assembler to avoid the function call overhead, you will not do much better, and the chances are that you compiler will inline it in any case if you let it. Various Intel and AMD specific extensions have other hardware sqrt instructions that may provide faster performance, and if you want to get really complex (and hardware specific), you can get the GPU to perform the operation using CUDA for example (although on its own it is unlikely to be faster  you'd rather use CUDA for performing an entire algorithm than a single operation).
Now your example code will only work for integer values and will yield the wrong answer if num has no exact integer root; you should at least stop when i*i >=num, and even then i1 may or may not be closer.
Performing a square root approximation on an integer value is useful on systems with no FPU where floating point operations may be prohibitively slow and integer and fixedpoint arithmetic is necessary instead (as on many embedded systems and DSP processors). But if you do that you should use a more intelligent algorithm than that you have proposed. The link above describes the most common method.
This article describes methods specifically for embedded systems (the only time you are likely to have a practical reason for doing this), in code rather than mathematical notation. It starts off by describing your naive solution (but corrected!), and goes on to improve it; explaining the improvements as it develops the code.
Last edited by clifford; April 30th, 2010 at 06:46 PM.
April 30th, 2010, 07:50 PM

He isn't interested in germane articles. He already checked them all out. He wants to test every value from minus infinity to plus infinity to see if any of them results in the answer.
EPSILON has no meaning in such a purely scientific endeavor demanding the utmost in righteous, solidly unequivocal answers.
It doesn't matter that it isn't normally time effective. Wishing can clearly make it so. One merely has to wring the necks of enough chickens.
Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
April 30th, 2010, 09:13 PM

Originally Posted by Nyan
Newton method can be used.
I think this is generally accepted as the best solution. However, finding a version that is guaranteed to work for integer inputs isn't totally trivial. I think these guys have a version that does work: http://www.apple.com/acg/pdf/aks3.pdf (Scroll down to "Detecting proper powers." The rest of the paper isn't relevant to this problem.) However, they don't explain why it's guaranteed to work. Their pseudocode actually finds arbitrary roots (square roots, cube roots, etc.).

This article also with code, describes a method for square root optimisation faster (or at least more deterministic) than NewtonRaphson (see the last page of the article, since it deals with other fixedpoint accelerations as well).
Originally Posted by deicider
i always try that first ,then i ask questions (:
If i ask questions that means what i found there wasn't satisfying.
Then either your Google technique or your comprehension of what you find needs improving more than your programming skills.
A large part of human knowledge is out there, and certainly this subject is well covered. If you expect a better answer here, you are likely to fall short, but you'll have to at least tell us what you have found and why it does not answer your question. All you are doing is getting smarter people (at least smarter at searching, or perhaps more widely read in programming and mathematics), than you to do your Googling for you!

Best square root way
Hi,
Children first learn to find the easy square roots that are whole numbers, but quickly the question arises as to what are the square roots of all these other numbers. You can start out by noting that (dealing here only with the positive roots) since √16 = 4 and √25 = 5, then √20 should be between 4 and 5 somewhere.
Then is the time to make a guess, for example 4.5. Square that, and see if the result is over or under 20, and improve your guess based on that. Repeat the process until you have the desired accuracy (amount of decimals). It's that simple and can be a nice experiment for children.
Thanks
Devid