Re: Square root algorithms and complexity

"gpapak" <gpapak@xxxxxxxxxxx> wrote in
news:dm70gf$79a$1@xxxxxxxxxxxxxxxxxxxx:

> Dear Lynn,
>
>
> I developed an algorithm which includes multiplications,addistions,
> and the computation of a square root .
> I want to extract the complexity of my algorithm, in terms of the
> number of multiplications that the algorithm performs, in order to
> compare it with other
> similar algorithms (time consumption).
>
>
> best regards
> George
>
> "gpapak" <gpapak@xxxxxxxxxxx> wrote in message
> news:dm6tsc$6lc$1@xxxxxxxxxxxxxxxxxxxxxxx
>> Hello,
>>
>>
>> Does anyone know popular algorithms for computing the square root of
> integer
>> numbers?
>> Additionly, which is the number of multiplications that is needed for
>> computing the square root using a specified algorithm ?
>>
>> Thanks in advance
>> George
>>
>>
>>
>
>

Well, the last timing information I have is for the Intel 80486, with a
1991 copyright date. A FSQRT took around 85 cycles; a FMUL around 16. So,
a square root would have taken about 5-6 times a long as a multiply.
Newer chips have much improved FPU times (at least for a multiply). The
85:16 ratio is near the 5.5 ratio mentioned by Herman Rubin for high-
precision arithmetic. Could well just be a coincidence! Probably is! If
you can't find anything better (e.g., measure the times in your actual
program on your actual chip), just use that ratio. Unless you have a
tremendously high number of SQRT() per second, any error is probably
what I know as "fine tuning the noise".

I'll repeat, that the actual square root algorithm almost surely does not
use any multiplies or divides at the chip level, but rather some variant
of non-restoring square root algorithm. Only if you are going beyond the
native accuracy of the machine itself, will actual multiplications be
needed (e.g., Newton's reciprocal square root) at a software level.

I can't really tell where you are headed. Hope some of this helps!

Lynn Killingbeck
.

Relevant Pages

  • Checking square root algorithm for portability/correctness
    ... I posted a thread on comp.programming awhile back asking about an algorithm ... I implemented on square root. ... prime number as a convenient way to get a pseudorandom number generator. ... iterations could be arbitrary. ...
    (comp.lang.c)
  • Re: Applying Poisson methods
    ... It is certainly not your algorithm. ... use of an inverse CDF and mine. ... CDF as you show, so long as it does not break. ... Take the square root of 75, to save as a constant M. ...
    (sci.stat.math)
  • Re: Square root algorithms and complexity
    ... >I developed an algorithm which includes multiplications,addistions, and the ... is using "machine precision", additions and multiplications ... may be such that part or all of the time for a square root ... >> computing the square root using a specified algorithm? ...
    (sci.math)
  • Re: Checking square root algorithm for portability/correctness
    ... > an algorithm I implemented on square root. ... > number of iterations to make. ... mask the highest eventh bit and shift the mask as you go. ... Assuming you have M value bits, your algorithm performs ...
    (comp.lang.c)
  • Re: (!?) need fast algorithm for computing factorials
    ... > I am looking for the fastest algorithm for computing factorials (ex: ... > The program to be used is Labview and it needs to compute up to 10000!. ... from 1 through N is not the best algorithm for computing N!. ... This uses Omultiplications, Oadditions/subtractions, and ...
    (comp.programming)