andrel <a_l### [at] hotmailcom> wrote:
> sqrt has at worst N/2 iteration, with N the number of significant bits.
> That is a naive implementation. I thought there are even faster
> algorithms. Cheap calculators often have a button for sqrt, implying
> probably that they have a (naive) hardware implementation. I don't know
> if it is available also on more complex processors.

From the "Intel(R) 64 and IA-32 Architectures Software Developer's Manual,
Volume 1: Basic Architecture":

------------------------
8.3.5 Basic Arithmetic Instructions

The following floating-point instructions perform basic arithmetic operations on
floating-point numbers. Where applicable, these instructions match IEEE Standard
754:

FADD/FADDP Add floating point
FIADD Add integer to floating point
FSUB/FSUBP Subtract floating point
FISUB Subtract integer from floating point
FSUBR/FSUBRP Reverse subtract floating point
FISUBR Reverse subtract floating point from integer
FMUL/FMULP Multiply floating point
FIMUL Multiply integer by floating point
FDIV/FDIVP Divide floating point
FIDIV Divide floating point by integer
FDIVR/FDIVRP Reverse divide
FIDIVR Reverse divide integer by floating point
FABS Absolute value
FCHS Change sign
FSQRT Square root                          <--
FPREM Partial remainder
FPREM1 IEEE partial remainder
FRNDINT Round to integral value
FXTRACT Extract exponent and significand

[...]

8.3.7 Trigonometric Instructions

The following instructions perform four common trigonometric functions:

FSIN Sine
FCOS Cosine
FSINCOS Sine and cosine
FPTAN Tangent
FPATAN Arctangent

[...]

8.3.9 Logarithmic, Exponential, and Scale

The following instructions provide two different logarithmic functions, an
exponential function and a scale function:

FYL2X Logarithm
FYL2XP1 Logarithm epsilon
F2XM1 Exponential
FSCALE Scale

[...]

------------------------

Don't expect all these to be "naive hardware implementation" in the same sense
as, say, an integer addition, shift, bit-wise AND/OR/XOR or whatever. Even a
floating-point addition is a non-trivial thing. Rather consider the FPU
(Floating Point Unit) a computer in the computer: You feed some data into it,
give it an instruction what to do with that data, and then basically wait for
the (fast and highly optimized) hard-wired FPU "programlets" to complete. Or do
some other usefull stuff in the meantime.

To my knowledge, a lot of work is saved by using Look-up-tables (like people
used in old times before pocket calculators had a "sin", "log" or "sqrt"
button) to optimize away a few iterations of the algorithms.

BTW, your typical pocket calculator will do just about the same. AFAIK there is
no non-iterative algorithm for computing the square root of an arbitrary
floating point number.

Post a reply to this message