How sqrt() of GCC works after compiled? Which method of root is used? Newton-Raphson?

by

yeah, I know fsqrt. But how the CPU does it? I can’t debug hardware

Typical div/sqrt hardware in modern CPUs uses a power of 2 radix to calculate multiple result bits at once. e.g. http://www.imm.dtu.dk/~alna/pubs/ARITH20.pdf presents details of a design for a Radix-16 div/sqrt ALU, and compares it against the design in Penryn. (They claim lower latency and less power.) I looked at the pictures; looks like the general idea is to do something and feed a result back through a multiplier and adder iteratively, basically like long division. And I think similar to how you’d do bit-at-a-time division in software.

Intel Broadwell introduced a Radix-1024 div/sqrt unit. This discussion on RWT asks about changes between Penryn (Radix-16) and Broadwell. e.g. widening the SIMD vector dividers so 256-bit division was less slow vs. 128-bit, as well as increasing radix.

Maybe also see

But however the hardware works, IEEE requires sqrt (and mul/div/add/sub) to give a correctly rounded result, i.e. error <= 0.5 ulp, so you don’t need to know how it works, just the performance. These operations are special, other functions like log and sin do not have this requirement, and real library implementations usually aren’t that accurate. (And x87 fsin is definitely not that accurate for inputs near Pi/2 where catastrophic cancellation in range-reduction leads to potentially huge relative errors.)

See https://agner.org/optimize/ for x86 instruction tables including throughput and latency for scalar and SIMD sqrtsd / sqrtss and their wider versions. I collected up the results in Floating point division vs floating point multiplication

For non-x86 hardware sqrt, you’d have to look at data published by other vendors, or results from people who have tested it.

Unlike most instructions, sqrt performance is typically data-dependent. (Usually more significant bits or larger magnitude of the result takes longer).

More Related Contents:

  1. What is the reason function names are prefixed with an underscore by the compiler?
  2. how can i increase the speed of my C++ calculation [closed]
  3. Procedure to include own functions to ANSI C Standard library
  4. Sum of the all the numbers between a and b [closed]
  5. Can I use Intel syntax of x86 assembly with GCC?
  6. Alternative (K&R) C syntax for function declaration versus prototypes
  7. print a __m128i variable
  8. Why does GCC allocate more space than necessary on the stack, beyond what’s needed for alignment?
  9. Rounding integer division (instead of truncating)
  10. Stack allocation, padding, and alignment
  11. How does GCC implement variable-length arrays?
  12. Syscall implementation of exit()
  13. Power by squaring for negative exponents
  14. Why does GCC pad functions with NOPs?
  15. “undefined reference to `pow'” even with math.h and the library link -lm [duplicate]
  16. Compiler using local variables without adjusting RSP
  17. Changing array inside function in C
  18. undefined reference when calling inline function
  19. Strange warning in a C function const multidimensional-array argument
  20. Gaussian elimination without result for acceleration
  21. Fastest way to calculate a 128-bit integer modulo a 64-bit integer
  22. Do I get a performance penalty when mixing SSE integer/float SIMD instructions
  23. Why does gcc use movl instead of push to pass function args?
  24. Calling C functions from x86 assembly language
  25. sin, cos, tan and rounding error
  26. Why is gcc allowed to speculatively load from a struct?
  27. How come INC instruction of x86 is not atomic? [duplicate]
  28. Finding square root without using sqrt function?
  29. Efficient 4×4 matrix multiplication (C vs assembly)
  30. C pointer notation compared to array notation: When passing to function

Leave a Comment