perfect square prob... math?

This is a discussion on perfect square prob... math? within the C Programming forums, part of the General Programming Boards category; I need a function to check an inputed number if can be perfectly squared. Just checking the last two digits ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37

    perfect square prob... math?

    I need a function to check an inputed number if can be perfectly squared. Just checking the last two digits makes this possible.

    00
    01
    04
    09
    16
    21
    24
    25
    29
    36
    41
    44
    49
    56
    61
    64
    69
    76
    81
    84
    89
    96

    i have found references to such functions (issquare), but no source. if someone could help me out that would be great.

    i have thought about parsing the last two digits and checking them against an array of the above possibilities. i am just not sure of the best solution. please help me construct something.

    thanks,
    skeptik

    (i hope this makes sense.)

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    > Just checking the last two digits makes this possible.
    Depends which way you want to go

    You can convert the input number ("1234") to an integer (1234), then do modulo 100 on it to extract the last 2 digits (x%100).

    Or you can leave it as a string, and create a pointer to the last pair of characters
    char *last2 = &string[ strlen(string)-2 ];

    The rest is a table search to compare against your list
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Unregistered
    Guest

    Re: perfect square prob... math?

    The last two digits(in base 10) of a positive number can be easily obtained as
    i-(i/100)*100
    or i%100
    no parsing required

    If a number is square , then the remainder upon division by 4 is either 0 or 1 , since any multiple of 100 is divisble by 4 , the last two digits (in base ten) of a square number must leave a remainder of 0 or 1 upon division by 4 , but unfortunately this only can be used to reject numbers which are not squares , it cannot be used to determine whether a number is square or not .
    so you can use this,
    but note the remainder of the divison of i by 4 is simply i&3

    int issquare(int i)
    {
    int j;
    if(i<0) return 0;
    j= i&3;
    if( (j != 0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
    /*check if square, ugly brute force method */
    if ( i&1 ) for(j=1;j*j<i;j+=2); /*i is odd check only odd numbers */
    else for(j=0;j*j<i;j+=2); /*check only even*/
    return (j*j==i);
    }

    another method that comes into my mind is by using the fact that the sum of first n odd numbers is n*n
    so we have
    int issquare1(int i)
    {
    int j,s=0;
    if(i<0) return 0;
    j=i&3;
    if( (j!=0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
    for(j=1;s<i;j+=2) s+=j;
    return (s==i);
    }

    the above method requires no multiplication


    since the square is a monotonic function we can also use binary search

    int issquare2( int i)
    {
    int j,lo,hi,mid;
    if(i<0) return 0;
    j=i&3;
    if( (j!=0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
    if(i<=1) return 1;
    for(lo=0,hi=i;lo+1<hi; )
    {
    mid=(lo+hi)/2;
    if( mid*mid>i) hi=mid;
    else lo=mid;
    }
    return (lo*lo==i);
    }


    Anyway last two digits do not determine wheter a number is square or not for eg. in base 10, 16 is a square , 116 is not . However sometimes they can tell if a number is not a square .
    For , eg a number having 06 as the last two digits in base 10 cannot be a square .
    Originally posted by skeptik
    I need a function to check an inputed number if can be perfectly squared. Just checking the last two digits makes this possible.

    00
    01
    04
    09
    16
    21
    24
    25
    29
    36
    41
    44
    49
    56
    61
    64
    69
    76
    81
    84
    89
    96

    i have found references to such functions (issquare), but no source. if someone could help me out that would be great.

    i have thought about parsing the last two digits and checking them against an array of the above possibilities. i am just not sure of the best solution. please help me construct something.

    thanks,
    skeptik

    (i hope this makes sense.)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Loop seg error
    By Zishaan in forum Game Programming
    Replies: 2
    Last Post: 03-28-2007, 01:27 PM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  3. Help with my draughts game
    By Zishaan in forum C++ Programming
    Replies: 9
    Last Post: 03-24-2007, 07:33 AM
  4. need help with simple math prob...
    By skeptik in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 11-19-2002, 12:37 AM
  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