18

Just curious how are these implemented. I can't see where I would start. Do they work directly on the float's/double's bits?

Also where can I find the source code of functions from math.h? All I find are either headers with prototypes or files with functions that call other functions from somewhere else.

EDIT: Part of the message was lost after editing the title. What I meant in particular were the ceil() and floor() functions.

Tony
  • 5,972
  • 2
  • 39
  • 58
Vlad Vivdovitch
  • 9,295
  • 8
  • 22
  • 21
  • Depending on what you really want to know, this question may belong on math.stackexchange.com. Implementing (an approximation to) any given non-simple-arithmetic function like `sqrt`, `sin`, `exp`, etc. usually involves knowing numerical analysis and applying an approximation method, possibly with argument reduction and other tricks too. – R.. GitHub STOP HELPING ICE Jun 01 '11 at 22:54

6 Answers6

21

If you're interested in seeing source code for algorithms for this kind of thing, then fdlibm - the "Freely Distributable libm", originally from Sun, and the reference implementation for Java's math libraries - might be a good place to start. (For casual browsing, it's certainly a better place to start than GNU libc, where the pieces are scattered around various subdirectories - math/, sysdeps/ieee754/, etc.)

fdlibm assumes that it's working with an IEEE 754 format double, and if you look at the implementations - for example, the core of the implementation of log() - you'll see that they use all sorts of clever tricks, often using a mixture of both standard double arithmetic, and knowledge of the bit representation of a double.

(And if you're interested in algorithms for supporting basic IEEE 754 floating point arithmetic, such as might be used for processors without hardware floating point support, take a look at John R. Hauser's SoftFloat.)

As for your edit: in general, ceil() and floor() might well be implemented in hardware; for example, on x86, GCC (with optimisations enabled) generates code using the frndint instruction with appropriate fiddling of the FPU control word to set the rounding mode. But fdlibm's pure software implementations (s_ceil.c, s_floor.c) do work using the bit representation directly.

Matthew Slattery
  • 45,290
  • 8
  • 103
  • 119
6

math.h is part of the Standard C Library.

If you are interested in source code, the GNU C Library (glibc) is available to inspect.

EDIT TO ADD:

As others have said, math functions are typically implemented at the hardware level.

Alan
  • 45,915
  • 17
  • 113
  • 134
2

Math functions like addition and division are almost always implemented by machine instructions. The exceptions are mostly small processors, like the 8048 family, which use a library to implement the functions for which there are not a simple machine instruction sequence to compute.

Math functions like sin(), sqrt(), log(), etc. are almost always implemented in the runtime library. A few rare CPUs, like the Cray, have a square root instruction.

Tell us which particular implementation (gcc, MSVC, etc./Mac, Linux, etc.) you are using and someone will direct you precisely where to look.

wallyk
  • 56,922
  • 16
  • 83
  • 148
  • 1
    All three of your example functions are available as hardware instructions on any modern x86-compatible platform... – Oliver Charlesworth Jun 01 '11 at 22:37
  • 2
    and almost never used in implementations... At least none of the open source implementation of the math library that I am familiar with uses the hardware instruction for transcendantal functions (sin, cos, etc...). – David Cournapeau Jun 01 '11 at 22:49
  • @David: Interesting. Any idea why not? – Oliver Charlesworth Jun 01 '11 at 22:55
  • 3
    The hardware instructions are largely unusable. For example the hardware `sin` and `cos` only work for very small arguments, and even then they might be off by more than you would like... – R.. GitHub STOP HELPING ICE Jun 01 '11 at 22:56
  • @R.,@David: Well, I learnt something today! Have redacted my answer accordingly... Although I would still contend @wallyk's remark in his answer that implies that it's only rare CPUs have these functions available at the hardware level. – Oliver Charlesworth Jun 01 '11 at 22:58
  • 1
    @Oli: I haven't looked for five years or so, but the x86 FPU instructions are named *partial sin*, *partial sqrt*, etc. Those instructions must be wrapped with argument checking, reduction, units conversion, and usually quite a bit more housekeeping. The instructions *may* make sense in a runtime library, but are not something a compiler would routinely generate. – wallyk Jun 01 '11 at 23:34
  • By the way, argument reduction modulo a transcendental number is not an easy task. Actually I have no idea how to do it... – R.. GitHub STOP HELPING ICE Jun 01 '11 at 23:41
  • @wallyk: `sqrt` is implemented in hardware on most platforms; as others noted `sin` and `log` are available on the x87, but generally not used in high-quality libraries. – Stephen Canon Jun 02 '11 at 02:42
  • 3
    @R..: it needs to be done carefully, but it's not rocket science; read http://www.derekroconnor.net/Software/Ng--ArgReduction.pdf or find a copy of Jean-Michel Muller's books. Writing good tests is significantly harder than writing the reduction itself. – Stephen Canon Jun 02 '11 at 02:43
1

On many platforms (such as any modern x86-compatible), many of the maths functions are implemented directly in the floating-point hardware (see for example http://en.wikipedia.org/wiki/X86_instruction_listings#x87_floating-point_instructions). Not all of them are used, though (as I learnt through comments to other answers here). But, for instance, the sqrt library function is often implemented directly in terms of the SSE hardware instruction.

For some ideas on how the underlying algorithms work, you might try reading Numerical Recipes, which is available as PDFs somewhere.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • Anyone here old enough to own an x86 computer that didn't have hardware support for floating point math? (I am...so old) – Alan Jun 01 '11 at 22:41
  • @Alan: I never owned one of those, though I used them at work. Our 1980s product was based the 8086 and 8087. – wallyk Jun 01 '11 at 23:03
  • @Alan My first computer was a 286 with no floating point, $200 in 1989 (included monochrome (gold) monitor). – luser droog Jul 03 '13 at 07:29
1

A lot of it is done on processors these days. The chip I cut my teeth on didn't even have a multiply instruction (z80)

We had to approximate stuff using the concept of the Taylor Series.

About 1/2 the way down this page, you can see how sin and cos are approximated.

EvilTeach
  • 28,120
  • 21
  • 85
  • 141
  • If you used Taylor series to approximate functions over an interval, you were doing it wrong: http://lolengine.net/blog/2011/12/21/better-function-approximations – Pascal Cuoq Jul 03 '13 at 08:09
0

While modern CPU do have hardware implementation of common transcendantal functions like sin, cos, etc..., it is rarely used as is. It may be for portability reason, speed, accuracy, etc... Instead, approximation algorithms are used.

David Cournapeau
  • 78,318
  • 8
  • 63
  • 70
  • After some reading and some looking at object code, I'm very much inclined to agree with you. Though it seems that at least some (non-transcendental) maths functions are implemented in terms of the FPU instructions, such as `sqrt` (in both GCC and ICC). – Oliver Charlesworth Jun 01 '11 at 23:13