How to confirm the number is square number?

This is a discussion on How to confirm the number is square number? within the C Programming forums, part of the General Programming Boards category; is there any efficent method to do it? for example, Code: 5 false 7 false 9 true 49 true 2553604 ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    77

    How to confirm the number is square number?

    is there any efficent method to do it? for example,
    Code:
    5
    false
    7
    false
    9
    true
    49
    true
    2553604
    true
    (the input data less than 2^32)
    Last edited by Mathsniper; 12-15-2006 at 08:44 AM.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    take sqrt, convert to int and check that the res*res == orig
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    E.g.: 841
    1) Split number into sets of 2 digits 08|41
    2) Let a = sqrt so far (init: a = 0)
    2) Let b = remainder = 08
    3) Solve for c in d=c(20a + c) such that d<=b
    .: c = 2 d=4
    .: a = 2
    4) b - d = 08 - 4 = 04
    5) Restart at 2) using b= 04*100+41 = 441

    3) .:c=9 d=441
    .:a=29
    4) b-d = 441-441 = 0
    5) Done. This is a perfect square since no remainder and we haven't gone into decimals yet

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    There is an efficient way to do this, yes.

    Newton's Method (Heron's Method?) works for integers when calculating square roots. It finds the square root in what appears to be log(n) time

    Find sqrt of 64
    Starting guess: 64.
    f(n) = (n + 64/n)/2

    f(64) = (64 + 64/64)/2 = 32
    f(32) = (32 + 64/32)/2 = 17
    f(17) = (17 + 64/17)/2 = 10
    f(10) = (10 + 64/10)/2 = 8
    f(8) = (8 + 64/8)/2 = 8 STOP
    Does 8*8 = 64? Yes. 64 is a square.


    There's just one tiny infinite loop to be worried about. Try finding the square root of 99, using a guess of "10" to see the loop.
    1. Use a number you know to be greater than the correct value as the first guess for this algorithm. Notice how my first guess was "64", which is guaranteed to be greater than or equal to sqrt(64).
    2. If at any point in the algorithm, f(n) > n, then quit there.

    http://mathforum.org/library/drmath/view/52609.html
    Callou collei we'll code the way
    Of prime numbers and pings!

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by coder8137
    3) Solve for c in d=c(20a + c) such that d<=b
    I haven't the time to carefully go over this... but this is solving for c, given the square of c. Isn't this step equivalent to the original problem?
    Callou collei we'll code the way
    Of prime numbers and pings!

  6. #6
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    Isn't this step equivalent to the original problem?
    It's similar, the important point is that b should always be < 10000. (EDIT: Not true for calculating sqrt of large numbers, when further into the calculation, since a will get bigger and bigger.) Also, just in case you didn't notice, the formula is looking for the biggest integer c. Usually solved with a few guesses. It's designed for large numbers or can calculate actual square roots to with decimal places easily. Also, it's probably one of the few methods you can use in your head to find the sqrt of non-perfect squares.
    Last edited by coder8137; 12-15-2006 at 09:07 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. Random number + guessing game trouble
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-08-2007, 03:33 AM
  3. Stone Age Rumble
    By KONI in forum Contests Board
    Replies: 30
    Last Post: 04-02-2007, 09:53 PM
  4. Loop seg error
    By Zishaan in forum Game Programming
    Replies: 2
    Last Post: 03-28-2007, 01:27 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21