Prev: What book is this?
Next: Hey Adamk and Bacle, I found your mom's C-HOLE! (I be here all ze week...!)
From: Link on 17 Apr 2010 18:37
On Apr 15, 11:58 am, Chip Eastham <hardm...(a)gmail.com> wrote:
> On Apr 15, 12:14 pm, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
> > 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.
>
> If the distribution of inputs contains a significant
> fraction of non-squares, your average time benefits
> from doing some "probabilistic" tests (giving a chance
> to quickly obtain the negative result) before resorting
> to the actual square root computation.
>
> - A nonzero square in binary representation will have
>   least significant bits "...001" followed by an even
>   number of zero bits (possibly none), because odd
>   squares are congruent to 1 mod 8.  [Depending on the
>   machine architecture it may be practical to strip
>   off the trailing zero bit pairs (factor out powers
>   of 4) so we know we are dealing with an odd number,
>   but unless the distribution of inputs contains a
>   high frequency of such powers, it may not be a
>   usefulreduction.]
>
> - 2^32 - 1 = 3*5*17*257*65537 has 5 distinct prime
>   factors, so if I understood the "100 million digits"
>   aright, your input may consist of 10 million or so
>   32-bit words.  Summing these into a 64-bit accumulator
>   in one pass, and then summing those two 32-bit words
>   into a single 32-bit word, would allow you to test
>   the input for quadratic residues mod those five
>   prime values.  This will knock out about 95% of the
>   non-squares, assuming the input distribution isn't
>   malicious.
>
> regards, chip

(C hole. (v [...] C e[ ...]) (C p e). (n p C) [...] (reduction-
relation. js0. (--> (P (v_first v_other [...] v_last) H S). (P
(v_last) H S) [...]

BOOM!
 | 
Pages: 1
Prev: What book is this?
Next: Hey Adamk and Bacle, I found your mom's C-HOLE! (I be here all ze week...!)