22

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.


20

It all depends what you want to do. For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly. In fact, many languages such as Haskell and Scheme have built in support for rational numbers, storing them in the form $\frac{a}{b}$ where $a,b$ are integers. The main reason ...


20

In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number. Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results ...


15

It's because 0.1 = 1 / 10 = 1 / (2 × 5) cannot be represented exactly in binary floating point. This happens in C too: printf("%.20f", fmod(4.0,0.1)); prints 0.09999999999999978351. Specifically, the only numbers that binary floating point can represent exactly are dyadic fractions of the form a / 2b, where a and b are integers. Even more ...


14

The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i. $$ That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them. Another approach, which is not so common, is to normalize the product manually. Instead of keeping just ...


8

Ilmari Karonen gets it right in the other answer. But it gets even worse than that: arithmetic operations involving floating-point numbers don't necessarily behave the same as operators we're used to from mathematics. For instance, we're used to addition being associative, so that $a + (b + c) = (a + b) + c$. This doesn't generally hold using floating-point ...


8

Assuming round-to-nearest and that $N > 0$, then $N * R < N$ always. (Be careful not to convert an integer that's too large.) Let $c 2^{-q} = N$, where $c \in [1, 2)$ is the significand and $q$ is the integer exponent. Let $1 - 2^{-s} = R$ and derive the bound $$N R = c 2^{-q}(1 - 2^{-s}) \le c 2^{-q} - 2^{-q - s},$$ with equality if and only if $c =...


8

There actually is some research on improving the numerical stability of floating point expressions, the Herbie project. Herbie is a tool to automatically improve the accuracy of floating point expressions. It's not quite comprehensive, but it will find a lot of accuracy improving transformations automatically. Cheers, Alex Sanchez-Stern


7

Two's complement makes sense when the two entities in question have the same "units" and the same "width". By width I mean that, say, if you're adding an N bit number and an M bit number, where N and M are different, then you better not use two's complement. For floating point numbers, we have the problem of units: if the exponents are different, then we are ...


7

Your idea does not work because a number represented in base $b$ with mantissa $m$ and exponent $e$ is the rational number $b \cdot m^{-e}$, thus your representation works precisely for rational numbers and no others. You cannot represent $\sqrt{2}$ for instance. There is a whole branch of computable mathematics which deals with exact real arithmetic. Many ...


7

There are many effective Rational Number implementations but one that has been proposed many times and can even handle some irrationals quite well is Continued Fractions. Quote from Continued Fractions by Darren C. Collins: Theorem 5-1. - The continued fraction expression of a real number is finite if and only if the real number is rational. Quote ...


7

You cannot meaningfully test floating point values for equality. A floating point value does not represent a real number, it represents a range of real numbers, but it fails to store the width of this interval. All you can do with floating point values is to test them for approximate equality, and it's up to you to define the approximation you're willing to ...


6

This is best explained in the base 10 equivalent: scientific notation In scientific notation you have a mantissa and a exponent such that the value is $\mathrm{mantissa} \cdot 10^{\mathrm{exponent}}$. In a computer floating point the mantissa is always the same size of significant digits (a double precision has around 16 digits) and the exponent is bounded....


6

As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot execute the same machine code on both Intel and ARM, so this answer is only hypothetic. Even on different Intel processors you have to take special care that exactly ...


6

No, that's not how binary fractions work. A decimal such as $0.13$ represents $$0.13_{\mathrm{dec}} = 1\times 10^{-1} + 3\times10^{-2} = \frac{13}{100}\,.$$ Similarly, a binary fraction such as $0.1101$ represents $$0.1101_{\mathrm{bin}} = 1\times 2^{-1} + 1\times 2^{-2} + 0\times 2^{-3} + 1\times2^{-4} = \frac{13}{16}\,.$$ $1101_{\mathrm{bin}} = 13_{\...


6

There's nothing fundamentally hard about computing $\sin(10^{99})$. You simply compute $x = 10^{99} \bmod 2\pi$, then compute $\sin(x)$. (Why is this valid? It's because $\sin(x)=\sin(y)$ if $x\equiv y \pmod{2\pi}$.) It's not too hard to compute $x$ if you use a numerical representation that has enough digits of precision, and then to compute $\sin(x)$ ...


6

Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ... There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to ...


6

Firstly, you need to decide if the floating point numbers you are working with are "normalized" or not. Think about how binary numbers are represented in scientific notation. Consider the number 100101.010101 The expression given above is not given in scientific notation, but what if we change that? To re-write 100101.010101 in scientific notation, we move ...


5

If you drop the leading zeroes then $3,5,9,17$ and so on will all have the same representation. Don't forget that the number being represented need not be an integer.


5

IEEE floating point format has a sign bit, an 11 bit exponent (ranging from -1022 to 1023) and a 52-bit mantissa with an implicit "1" in the 53rd bit. Thus, the largest integer that can be represented without rounding is the binary number with 53 "1"s, $2^{53}-1$ = 9,007,199,254,740,991 ~ 9e15 < 1e16. After that you start having to round off low order ...


5

There are a number of "exact real" suggestions in the comments (e.g. continued fractions, linear fractional transformations, etc). The typical catch is that while you can compute answers to a formula, equality is often undecidable. However, if you're just interested in algebraic numbers, then you're in luck: The theory of real closed fields is complete, o-...


5

Yes, the difference is constant. It is not really constant, but approximately, yes. With exceptions. With binary floating point numbers, the expression $(f(r)−r)/r$ is constant within a factor of $2$. It is between $1 \over 2^m$ and $1 \over 2^{m-1}$ where m is the number of bits in the mantissa. For rounding error calculations, you can assume it is ...


5

The == operator invoke a float point compare instruction, this considers two numbers equal if neither is NaN, and they are exactly the same, or if they are positive and negative zero. Notably Infinity == Infinity, despite the mathematical dubiety of considering infinities equal, and Infinity - Infinity returning NaN. So if the numbers are not exactly equal, ...


5

Generally speaking, normalized means "put in scientific notation." That just means, the mantissa should never start with 0, and should be less than the base. In binary that means the mantissa must be "1". Since the mantissa of a normalized binary floating point number is always 1, we don't need to store the 1. The first mantissa bit is hidden in the ...


5

Java uses IEEE 754 binary floating point representation, which dedicates 23 binary digits to the mantissa, that is normalized to begin with the first significant digit (omitted, to save space). $0.00004_{10} = 0.00000000000000101001111100010110101100010001110001101101000111..._{2} = [1.]\color{red}{01001111100010110101100}010001110001101101000111..._{2} \...


5

The binary floating point format supported by computers is essentially similar to decimal scientific notation used by humans. A floating-point number consists of a sign, mantissa (fixed width), and exponent (fixed width), like this: +/- 1.0101010101 × 2^12345 sign ^mantissa^ ^exp^ Regular scientific notation has a similar format: +/- 1.23456 × 10^...


5

It may be that sqr (sqrt (7)) is displayed as 7, but it isn't actually exactly equal to 7. That's something you need to check. What you see is not always what you get. It may be that sqr (sqrt (7)) is exactly 7, by "coincidence" (not really coincidence, more like "unpredictable with my limited knowledge"). Take any floating point number x, 1 ≤ x < 4. ...


5

Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.


4

But why is a sign bit necessary for floating point numbers False assumption. It isn't necessary. I'm pretty sure I've met floating point formats which used 2's complement for the mantissa, but I'd have to dig out for names. I'm far from being a specialist in numerical analysis, but I get that having signed zero is important for them. It's probably easier ...


4

From Wikipedia: The two's-complement system has the advantage that the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers... Two's-complement is a representation of negative numbers that just so happens to be very convenient. That's the whole reason to use it at all. A ...


Only top voted, non community-wiki answers of a minimum length are eligible