perfect square macro

Hmmm, kind of a BIG request for a macro.  preprocessor macros don't have looping, variables, or arithmetic if's, so all that's left is text-fudging and recursion.

But let's see if we can do it anyway:

First let's see if we can generate powers of a number.  If we can do that much, then we just need to call this power macro until we get a match.  A bit slow but you didnt specify what speed you wanted!

We have to use recursion, so it's going to be something like:

#define Power(x,y)  ( Power( x, (y - 1) ) * (x) )

... but we need it to stop expanding at y = 0, so we need some text_fudging for that special case:

#define Power_0   1

#define Power_1(x,y)   Power_##y(x,y)  // define about 100 of these up til Power_100

Don't have a c compiler handy right here so you'll have to trust me on this one.

... then to do an equality test,  that's even harder as cpp doesnt have any Arithmetic IFs, but you can fake it with multiplication and subtraction and recursion:



#define  FindIfPerfectSquare(y,x)  ( y * ((y) - FindIfPerfectSquare( y, x - 1 ))))

Done just right this will expand to a long expression:  (yournumber - power(99, 2 ) * ( yournumber - Power( 98,2 )

...  IT STILL NEEDS SOME WORK, but I *think* the general idea is in there...

> i want to use the binary format and bit patterns,not any other approach,infact i want a one or two liner.

...and I would like a car that flies, gets 1000 miles to the gallon, is extremely cheap, never has to be serviced, and is perfectly safe.

The only way I can think to test for perfect square in entirely contained in a macro context is this:

#define IS_SQUARE(x) (sqrt(x) == floor(sqrt(x)))

This isn't that great because it uses redundant sqrt()s, and floating point.

Another way to do it is to rely on some tables to eliminate most non-squares:

#define MIGHT_BE_SQUARE(x) (1&(0x2010213>>((x)%32))&(0x2492693>>((x)%27))&(0x294A53>>((x)%25)))

This works as a perfect test for x < 241.  Otherwise, it gets rid of about 96% of non-squares.  You can use this to reduce the number of times you do a slow square check:

if (MIGHT_BE_SQUARE(x) && slow_reliable_check_square(x)) {
   .. do x-is-square stuff ...
} else {
    .. do x-is-not-square stuff
}

>... then to do an equality test,  that's even harder as cpp doesnt have any Arithmetic IFs,
> but you can fake it with multiplication and subtraction and recursion:
>
>#define  FindIfPerfectSquare(y,x)  ( y * ((y) - FindIfPerfectSquare( y, x - 1 ))))

Let's assume for a minute that C allowed recursive macros... then
FindIfPerfectSquare   would expand to an infinitely long expression, and
the C compiler could never get through it all...

The question you should really ask himself/herself is why do you even want it
to be a macro?  
Size should be the main consideration (whether it's worth it)
and an inline function should be just as good.

A positive integer v is a perfect square  means  

there are two positive integers a and b
s.t.  a*b = v  <=> a = b

Without actually proving it...    a < v, right?   then just try every a...
What numbers can you rule out?  Any number v isn't divisible by, right?
Perhaps if they're relatively prime?

Ok... when k is a positive integer less than a
       a <= v/k

I don't know, you'll need to check/proof that it is safe to do that, and you
would probably do well to see about finding a lower bound

start for a = 2; a < v && a < v/(a-1) {
    increment a
    if (a*a == v) { found = 1; }
  }
  return found;

Of course  if  v is really big, then you're probably best off just  using the
sqrt() function, or getting a better guess for a before starting, eh?

You can stop recursion by concatenating up a macro symbol one character at a time.  When you hit the required length, have a macro symbol that returns zero.

Something like:

#define A_
#define A_A_
#define A_A_A_  // and so on...

#define A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A    0   // 100 A_'s

#define Recur50   A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_   // 50 A_'s

#define Recur( p1, p2, ..., Stopper )     Recur( p1, p2, ..., Stopper##A_ )

hey guys,
               i got an approach in some math forums,it goes like this.start from 1,add 2 to to it and add it by itseelf it gives 4,add another 2 to the original number,it gives 5,add it to the new number,
somewhat like

1
1+3=4
1+3+5=9
1+3+5+7=16
1+3+5+7+9=25
...........................and so forth

one approach said start subtracting from 1 and move on to 3 and keep going until i get a 0..but iam not able to find a bit pattern like some left shift or right shift operations,the reason iam stressing on it is,i do not want to initialize too many varibales on stack,basically if the operation is performed in the internal registers,it is better,memory is constarint.

no math library functions,no recursion,not more than one or maximum two variables.thanx

Those restrictions are rather unusual, please explain why you want
a maximum of two variables.

Perhaps C is the wrong language to be using, and you might look at using
assembly if your space restrictions are so tight.

In any case, if you can approximate an upper and lower limit for the square root,
you can get a range of possible 'exact integer square roots'   to check.
If you find one, then it's a perfect square, if you verify there's no choice in the
range that works, then it can't be a perfect square.

You don't need to use the math library to approximate a square root,
your favorite approach should do (whatever that is)

You can possibly approximate by choosing extreme values, looking at their squares,
until you have a number whose square is less than the target and a number whose square
is greater, and then take a number somewhere from the middle,  reducing the search space
by half, possibly more, depending on how you analyze it..

*why you want a maximum of two variables*

costly for bus cycles to access data from memory.time overhead,RAM space etc.....

>costly for bus cycles to access data from memory.time overhead,RAM space etc.....

It's also very costly to go through a conditional loop re-implementing an integer version of a function that is already implemented in _hardware_.

This will probably be faster than any loop anyone can come up with:

int is_square(int radicand) {
    int root = sqrt(radicand);
    return root*root == radicand;
}

if you want to go by bit patterns, perfect squares are 0,1,4 or 9 mod 16. i.e. num%16 = 0 or 1 or 4 or 9. if the num%16 != one_of_these_values then it is not square. this a partial answer only. let me do some more work on this.

here is a piece of code. it may or may not not fit your needs but looks pretty fast to me. if you want you could do a binary search for most significant non-zero bit. but that would involve comparsions and subtractions. doesn't matter on intel machines because AND and SUB take same amount of time. don't know about other processors.
for ( k=31; ; k-- )
  if( 1<<k & number ) break;
k >>= 1; /*div by 2*/
if ( (number >> k)*(number >> k) == number )
  it's a perfect square.
else
  it's not.

there might be errors. i don't have a compiler right now so i can't test it. other experts plz correct me if anything is wrong.

note that the code does not call anything from the math library because to me it seems that it would defeat the the aim of fast code. if you are willing to sacrifice time for the sake of readbility then fine. you can figure out k using log function. or you could write a macro that will determine k for you instead of having a loop.

>> This will probably be faster than any loop anyone can come up with:
>> int is_square(int radicand) {
>>     int root = sqrt(radicand);
>>     return root*root == radicand;
>> }
WRONG!!! sqrt is one of the most expensive functions. plus stack usage must be limited. my code above tries to find floor(sqrt) using bit shifts. simply shift by half the number of bits.

yes i thought about it for a while and found that my routine is a piece of ****.

I did not say that the whole code you posted was bad. just disagreed with your statement that is_square() is fastest. overall, MIGHT_BE_SQUARE is simply amazing as it has excellent on avg performance (as you state it). I was wondering if you could explain how did you come up with those numbers?

i take that back. did you consider how expensive % is? its same as division. which takes ~29 clock cycles on intel 188xl. since this is an embedded processor case here, I do not expect the performance to be much better (may be 15, tops). unless it's a DSP processor. in that case it is better to write it in assembly. and one more thing that we all forgot is that the order of evaluation is not guaranteed or required by the C standard spec. so sqrt could be evaluated before your macro. it's best to ask the writer of the compiler to resolve the issue but it is not feasible. so what do we do? simply use the sqrt given to us. aren't we dumb to think that we can come up with better solution than those experts out there?

The first perfect square is...
1*1=1

the next is...
2*2=4     = 1   + 3    = 1*1 + 1 + 2*1

then
3*3=9     = 4   + 5
4*4=16   = 9   + 7
5*5=25   = 16 + 9
6*6=36   = 25 + 11
...
12345*12345 = 12344*12344 + 1 + 2*12344 = 152399025

Perhaps this could be useful in checking if a number is of the proper
form?    (still thinking)

Only sometimes is the '%' expensive.  gcc can often take '/' by a small compile-time constant and transform that into a multiply and a shift.  It takes a/b and uses a 32x32->64 bit multiply to turn it into an equivalent (a*c)>>d expression.  Approximately, 1/b == c/(2^d) with enough accuracy that it will give the same answer for all ints < 2^31

> and one more thing that we all forgot is that the order of evaluation is not guaranteed or required by the C standard spec. so sqrt could be evaluated before your macro

That's true in general for arithmetic operators, but the C standard defines the logical operator '&&' (and similarly, '||')  so that a "Sequence Point" happens in between the evaluation of the left argument and the right argument.  In other words, the order of evaluation for '&&' and '||' is explicitly guaranteed, and the right side is explicitly guaranteed to not be evaluated if the left side rules it out.

a() && b() && c()

Neither b() nor c() will be called if a() returns false.

> I was wondering if you could explain how did you come up with those numbers?
The hex numbers or the 96% number?
0x2030213:  The bits # 0,1,4,9,16,17,25 are the only ones set, and these numbers are the only values squares can hold modulo 32.  I just wrote up a dumb little program to generate these constants for arbitrary moduli.

The 96% comes from the fraction of values that are eliminated by each of the 3 quadratic residue tests.  The mod32 test only accepts 7/32 values.  The mod27 test only accepts 11/27 values.  The mod25 test only accepts 11/25 values.  Since all of these moduli are relatively prime, these probabilites are independant, so we can just mulitply them together.  7/32 * 11/27 * 11/25 is about 3.8%,  so that means the tests eliminate over 96% of nonsquares.  

>> gcc can often take '/' by a small compile-time constant and transform that into a multiply and a shift.
that's great. but is the asker using gcc?

>>the C standard defines the logical operator '&&' (and similarly, '||')  so that a "Sequence Point" happens in between the evaluation of the left argument and the right argument.
really? because i read in some other thread that it is not guaranteed. and it was from one of more famous people around here. i don't remember the name and i don't remember if it was c or c++. now you have managed to confuse me. where can i find C standard spec. not to argue with you but for future reference.

ans thanks for the explanation about those numbers.

Here's a draft, almost as good as the real thing.  In order to get the real thing, you need to buy it from ANSI (or your national IEC standards organization if you're not in the U.S.)
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n869/n869.pdf.gz

The unguaranteed-order thing is true about all operators in C except for '&&' and '||'.

See section 6.5.13 for the && operator.

Actually, the '? :' operator will only evaluate one of its second and third arguments, and its order is guaranteed too.

hey guys,
              i dont know,about the size and speed of this macro but any ideas as to simplifying it further.the below macro works.but experts judge my take on this one.

#define SQUARE(num)  {int n=1,k=1;while(num != n && n<=num) {n=n+(k+=2);} if(num==n)cout<<"OK";else cout<<"NOT A SQUARE";}  

It will take freaking forever.  That's an O(sqrt(n)) algorithm you have there.  The mere fact that it's in a macro doesn't make it fast.

Nova is right... about the only way you could do slower would be to write
for(n = 0; n < num; n++) {if (n*n==num) break;}  if (num==n) {cout<<"OK\n";} ...

The following is pretty bad and requires about 29 steps for big numbers, but at least it's
fairly fast...

int main() {
 int num = 196000000;

#define AVGN (l+(u-l)/2)
 int lower=1,upper=num;
       if (num<0) {lower=1; upper=-1;}
       for(lower = 1;lower < upper;) {
            if ((AVGN * AVGN) == num) { lower = AVGN; break; }
            if (AVGN * AVGN > num || AVGN*AVGN < 0) { upper = AVGN-1; }
            else                   { lower = AVGN+1; }
       }
     if(lower*lower==num)cout<<"OK";else cout<<"NOT A SQUARE";}
#undef AVGN
}

Man, this would have been a fun thread to have followed live.  :)

Look at the basic premise again:

1 = 1^2
1+3= 4 = 2^2
1+3+5= 9 = 3^2
1+3+5+7= 16 = 4^2
1+3+5+7+9= 25 = 5^2

The square root is the number of operands.  (sqrt (25) = 5.  1+3+5+7+9=25.   1+3+5+7+9 has 5 operands)

When the number of operands is odd, the square root is the middle operand.
When the number of operands is even, the square root is the average of the middle two operands.
The square root is always the average of all operands.

It would seem that these facts could be useful.


Fun With Mathematics -- coming soon to a theatre near you!  ;)
Kent

(a+1)^2 - a^2 = 2a + 1
so
S_(n+1) = S_(n) + (2a + 1)

Well, wow... indeed it is the number of operands

hmm..
(a+100)^2 - a^2 = 2*100*a + 10000
(a+10000)^2 - a^2 = 2*10000*a + 100000000

(a+b)^2 - a^2 = 2*b*a + b^2

This suggests finding a smaller perfect square's root than the target number
and iterate by increasing by  2ba+b^2  units, but I guess it isn't very practical...

--
Perhaps examine how GMP handles this is worth looking at, however:
http://www.swox.com/gmp/manual/Perfect-Square-Algorithm.html
http://www.inria.fr/rrrt/rr-3805.html

"mpz_perfect_square_p is able to quickly exclude most non-squares by checking whether the input is a quadratic residue modulo some small integers."

I'm not very familiar with number theory or quadratic residue (mod p) tests, but being able to exclude
non-squares early and being finding the square root in  O(1.5*M(N/2)) via something like that Karatsuba Square
Root algorithm would seem fairly fast in terms of runtime, if it's something you can implement...

I looked at a version of gmp after I put my macro up.  It's algorithm was:
1.  Check quadratic residue modulo 256, return false if it fails this test.  This uses a 256-byte table.
2.  Perform 1-limb mod operation on the big number, with a special modulus being the product of a bunch of small primes.
3.  Using the result from step 2, do quadratic residue checks for each of the prime moduli that make up that 1-limb  modulus, and return false if it fails any of these residue tests.  Each of these tests is identical in form to the 3 tests in my macro.
4.  Perform a sqrt-equivalent operation on the full number, just keeping track of the remainder.  
5.  If the remainder from step 4 is zero, return true.  else return false.

It looks like it always comes down to performing an integer sqrt algorithm to do the final check.  

For what it's worth, here is a Newton's-method algorithm used in some different places to find floating point sqrt(n):

1.   Approximate sqrt(n) using a limited-precision table, accurate to 10-12 bits or so.  
2.  x = 0.5 * (x + n/x).  Repeat 2 or three times

It does sqrt with a table lookup, a few divides and adds.

To find the square root of an integer, you need to do this efficiently enough that you beat your CPU's floating-point sqrt operation, else it's just not worth it.