Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    26
    Rep Power
    0

    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;
  2. #2
  3. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    #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...

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    26
    Rep Power
    0
    ye,but i know there are some good ways to do it manually without using functions.
  6. #4
  7. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    And the reason for doing so is what?

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    26
    Rep Power
    0
    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.
  10. #6
  11. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    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!

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    26
    Rep Power
    0
    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?
  14. #8
  15. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Square root algorithm.

    Comments on this post

    • nebelung agrees : :-)
    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.
    DaWei on Pointers Politically Incorrect.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    26
    Rep Power
    0
    Square root algorithm.
    i always try that first ,then i ask questions (:
    If i ask questions that means what i found there wasn't satisfying.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2009
    Posts
    337
    Rep Power
    46
    Newton method can be used.
  20. #11
  21. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    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 in-line 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 i-1 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 fixed-point 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 07:46 PM.
  22. #12
  23. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    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.
    DaWei on Pointers Politically Incorrect.
  24. #13
  25. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.).
  26. #14
  27. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    This article also with code, describes a method for square root optimisation faster (or at least more deterministic) than Newton-Raphson (see the last page of the article, since it deals with other fixed-point 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!
  28. #15
  29. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2010
    Posts
    2
    Rep Power
    0

    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
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo