Implementation of ceil() and floor()

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.