Prev: What is the shape that defines a semi-circle as the as it rollsalong a straight line?
Next: Cauchy product
From: recoder on 15 Apr 2010 10:19
Dear All,
What is the state of the art method to detect if a binary number is a
perfect square?
Thanks in advance....
From: Pubkeybreaker on 15 Apr 2010 10:36
On Apr 15, 10:19 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> Dear All,
>  What is the state of the art method to detect if a binary number is a
> perfect square?
> Thanks in advance....

Please answer the following:

(1) Why do you believe that its representation (i.e. binary) matters?
On a computer, all numbers are stored in binary.
(2) How big is the number? [this matters!]
(3) When you say "state of the art" do you mean "best known
algorithm",
or do you mean "best known code on a particular computer"??
If the latter, you need to specify the computer.
(4) Must the answer be deterministic, or will you settle for knowing
the
answer with high probability?

Your statement of the problem is too vague to have a definitive answer.
From: recoder on 15 Apr 2010 11:20
On Apr 15, 5:36 pm, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
> On Apr 15, 10:19 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > Dear All,
> >  What is the state of the art method to detect if a binary number is a
> > perfect square?
> > Thanks in advance....
>
> Please answer the following:
>
> (1) Why do you believe that its representation (i.e. binary) matters?
> On a computer, all numbers are stored in binary.
> (2) How big is the number?  [this matters!]
> (3) When you say "state of the art" do you mean "best known
> algorithm",
> or do you mean "best known code on a particular computer"??
> If the latter, you need to specify the computer.
> (4) Must the answer be deterministic, or will you settle for knowing
> the
> answer with high probability?
>
> Your statement of the problem is too vague to have a definitive answer.

the binary number is in the range of 100 k - 100 Million digits

for me state of the art means speed

Deterministic might take long time, high probabibility is speedier I
guess
From: Michael Hennebry on 15 Apr 2010 11:43
On Apr 15, 10:20 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> On Apr 15, 5:36 pm, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
> > On Apr 15, 10:19 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > > Dear All,
> > >  What is the state of the art method to detect if a binary number is a
> > > perfect square?
> > > Thanks in advance....
>
> > Please answer the following:
>
> > (1) Why do you believe that its representation (i.e. binary) matters?
> > On a computer, all numbers are stored in binary.
> > (2) How big is the number?  [this matters!]
> > (3) When you say "state of the art" do you mean "best known
> > algorithm",
> > or do you mean "best known code on a particular computer"??
> > If the latter, you need to specify the computer.
> > (4) Must the answer be deterministic, or will you settle for knowing
> > the
> > answer with high probability?
>
> > Your statement of the problem is too vague to have a definitive answer.
>
> the binary number is in the range of 100 k - 100 Million digits
>
> for me state of the art means speed
>
> Deterministic might take long time,  high probabibility is speedier I
> guess

For probabilistic, evaluate a lot of Jacobi symbols.
No means no. Yes means maybe.

For deterministic, I think you will have to bite the bullet and find
the square root.
This can be done in a time proportional to the time required for
multiplication.
From: Pubkeybreaker on 15 Apr 2010 12:14
On Apr 15, 11:43 am, Michael Hennebry <henne...(a)web.cs.ndsu.nodak.edu>
wrote:
> On Apr 15, 10:20 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
>
>
>
>
> > On Apr 15, 5:36 pm, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
> > > On Apr 15, 10:19 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > > > Dear All,
> > > >  What is the state of the art method to detect if a binary number is a
> > > > perfect square?
> > > > Thanks in advance....
>
> > > Please answer the following:
>
> > > (1) Why do you believe that its representation (i.e. binary) matters?
> > > On a computer, all numbers are stored in binary.
> > > (2) How big is the number?  [this matters!]
> > > (3) When you say "state of the art" do you mean "best known
> > > algorithm",
> > > or do you mean "best known code on a particular computer"??
> > > If the latter, you need to specify the computer.
> > > (4) Must the answer be deterministic, or will you settle for knowing
> > > the
> > > answer with high probability?
>
> > > Your statement of the problem is too vague to have a definitive answer.
>
> > the binary number is in the range of 100 k - 100 Million digits
>
> > for me state of the art means speed
>
> > Deterministic might take long time,  high probabibility is speedier I
> > guess
>
> For probabilistic, evaluate a lot of Jacobi symbols.

Yep.

> No means no.  Yes means maybe.
>
> For deterministic, I think you will have to bite the bullet and find
> the square root.
> This can be done in a time proportional to the time required for
> multiplication.- Hide quoted text -

Use Newton-Raphson along with FFT based multiplication.
 |  Next  |  Last
Pages: 1 2
Prev: What is the shape that defines a semi-circle as the as it rollsalong a straight line?
Next: Cauchy product