Perfect square or not?

[jnml]

Bob has a huge, zillion digits number and needs to know if it is a perfect square or not. Unfortunately, the number is so big no usual computer methods are able to give the answer in any reasonable time. The number has no apparent special form.

Bob consults Alice. Alice asks Bob what is the value of bit X in the binary representation of the number. Bob says it is Y. Alice tells Bob that his number is not a perfect square.

The above is enough to now know what are the values of X and Y.

(Addmited, this one is so easy it may even not belong here, but I still find surprisingly many people not being able to solve it. Can you? ;-)

[LaurV]

Bob has a huge.. Wow, for a moment I saw you are talking about our Bob.. (RDS)

- all odd squares are 1 mod 8 (the end of their binary form is ...x001)
- all even squares are 0 mod 4 (the end of bla bla is ..x00).
So, if the former but last bit is 1, the number is not perfect square.

Now the real interesting question would be if Alice says she doesn't know, and she keeps asking Bob, till eventually he tells her the most part (or all) the number. Can she answer efficiently? That would be interesting to solve, as a puzzle.

[jnml]

Originally Posted by LaurV

Bob has a huge.. Wow, for a moment I saw you are talking about our Bob.. (RDS)

LOL

- all odd squares are 1 mod 8 (the end of their binary form is ...x001)
- all even squares are 0 mod 4 (the end of bla bla is ..x00).
So, if the former but last bit is 1, the number is not perfect square.

On a nit picking side note, mod 8 is an overkill ;-)

Now the real interesting question would be if Alice says she doesn't know, and she keeps asking Bob, till eventually he tells her the most part (or all) the number. Can she answer efficiently? That would be interesting to solve, as a puzzle.

Hmm. Now, I'm puzzled ;-) Just guessing: No. (?)

[alpertron]

If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.

If the "1" is found in the even bit position, the next two more significant bits bits must be zero (the 001 string) otherwise the number is not square.

Otherwise you will need more than half of the bit representation of the number in order to know whether it is a perfect square or not (in the worst situation you will need the entire number). If the number is so large that cannot be sent from Bob to Alice, she will not be able to answer the question.

[jnml]

Originally Posted by alpertron

If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.

Did you mean "least significant bit set" instead of "not set"?

Otherwise it doesn't seem to work:

 pos 3210
bits 1001 // 9

Least significant bit not set is at position 1, which is an odd number - but 9 == 3².

[Batalov]

He counts from 0 being the LSB bit, as in ...n₂ * 2² + n₁ * 2¹ + n₀ * 2⁰

[jnml]

Originally Posted by Batalov

He counts from 0 being the LSB bit, as in ...n₂ * 2² + n₁ * 2¹ + n₀ * 2⁰

Me too AFAICS.

[LaurV]

Originally Posted by jnml

Me too AFAICS.

He wants to say "the number of zeroes at the end must be even and after the first 1 (counting from the right, i.e. from the end) there must be another two (at least) zeros (i.e. in front of it, to the left)" to (have a chance to) be a square. Which is right. That is, the last "1" in the normal order from left to right, as you read the number, that is the rightmost "1", must be preceded by at least 2 zeroes and followed by an even number of zeroes. Otherwise there is no way to be a square. There is always a confusion when you say "set bit", "clear bit", "reset bit", bla bla. Not everybody understand that the bit is in 1 or in 0.

edit: like this ......xxxxxxx001*, where the * can be replaced with nothing, or with an even number of zeroes.
edit2: xxxx from above it is always a triangular number, so if you can test this fast... :P

[jnml]

Originally Posted by LaurV

He want to say "the number of zeroes at the end must be even and after the first 1 (counting from the right, i.e. from the end) there must be another two (at least) zeros (i.e. in front of it, to the left)" to be a square. There is always a confusion when you say "set bit", "clear bit", "reset bit", bla bla. Not everybody understand that the bit is in 1 or in 0.

I believe I understand that and I agree (odd number of right trailing zeroes means the factorization will include an odd power of 2 which a perfect square cannot have).

I still think that both the above from me and quoted from you means the same which is "the index of the right most set bit must be even (not odd)", while alpertron wrote "not set". I think it's just that he made a simple typo, nothing more. (I produce them hundred times a day in code ;-)

[science_man_88]

for(x=1,100,print(binary(x^2)))

[alpertron]

Originally Posted by alpertron

If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.

Sorry, it is not "not set", it is "set".