Jump to content

Talk:Floating-point arithmetic/Archive 2

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 1Archive 2Archive 3Archive 4Archive 5

binary rounding

I'm having a tiny problem with the pi example, the sentence "Hence the floating-point representation would start with ..." irritates me a little. Instead of merely cutting away behind the last digit I'd prefer rounding instead:

11.001001000011111
is the number with an extra digit. Simply cutting away the last digit gives
11.00100100001111
That's about 3.14154053, which is about -5.2E-5 away from pi.
Rounding up the last digit instead gives
11.00100100010000
That's about 3.14160156, which is about 8.9E-6 away from pi.

Is there something I've missed? --Nikai 22:24, 14 Apr 2004 (UTC)

You're quite right, especially as there are non-zero bits 'out there to the right' of the original 17. The smallest fix would be to add 'in a representation which did not allow any rounding...' or something like that. mfc 15:25, 16 Apr 2004 (UTC)

base2 to base10

howto find the exponent

In order to convert -18,75 into 32 bits:
18d = 10010b
0,75d = 2**-1 + 2**-2 = 1/2 + 1/4 = 0,11b
---> 18,75d = 10010,11b =  1,001011 * 2**4
Sign: Négatif      = 1
Exposant: 4        = 4d + 7Fh = 83h = 100 000 11 b     Why add 7Fh (0111 1111b) ?
Mantisse: 001011   = 001 0110 0000 0000 0000 0000
Hence, -18,75 is 1 10000011 001011 000 000 000 000 000 00(binary) or  C196000(hexa)
bit number      =1 23456789 012345 678 901 234 567 890 12 = 32bits              

Why add 7Fh (0111 1111b) ? [[1]]

This is the "exponent offset" of 127 referred to in the "computer representation" section. The bit pattern stored in the exponent field of the number in the computer is not the same as the exponent that we mean when we say things like "18.75d = 1.001011 * 2**4". It is always higher by 127 (in single precision.) William Ackerman 23:55, 17 August 2006 (UTC)
I don't understand how to calculate the decimal value of 110010010000111111011011 :
1 10010010 000111111011011 left to right : a31=1, a30=1, 29=0, a28=0 etc... a31=1 so float is positive a30-a23 = 10010010 --> ? a22-a0 = mantisse = 000111111011011

So how can you say that 11.00100100010000 is nearly pi ?

Like this: You must be careful to distinguish between numbers represented in whatever base from numbers represented in the format of a particular computer's representation of normalised floating-point numbers in binary, a bit sequence that is possibly very different from the bit sequence of that number in binary due to the additional details of possible implicit leading bit, and the locations of the sign bit and exponent, and any offset for the exponent.

To convert from one base to another the hand process is simple though tedious. First, split the number into the integral part and the fractional part. Thus for pi, the parts are 3, and .14159etc. Convert the integral part by repeated division by the desired base and note the remainders (working in whatever base you wish): 3/2 gives 1, remainder 1. Second step: 1/2 gives 0, remainder 1. No further steps. The integer part of the binary representation is thus 11., being the remainders in reverse order. (For 6, the remainders would be 0, 1, 1 and the representatiion would thus be 110.) For the fractional part, repeatedly multiply by the chosen base, recording and remioving the whole part that appears. So .1415*2 = 0.2830 so 0, .2830*2 = 0.5660 so 0 again, .5660*2 = 1.1200 so 1, .1200*2 = 0.2400 so 0, etc. so the first few binary bits of the fractional part are .0010 and thus the binary representation of pi is 11.00100100001... this being a proper digit string in binary of a number.

This is however not a normalised binary floating-point number, so an exponent has to be introduced. To pack the number into the computer's representation bit string (32 bits, 64 bits, 80 bits...) the mantissa's bit string must be truncated or rounded at 24 bits, or whatever is the field size allocated for it with or without implicit leading one, then all the components (sign, mantissa, exponent) be packed according to the agreed format. Going the other way, you first unpack the floating-point format into a proper number (if you know that the bit string is not already a proper binary number bit string), especially locating the binary point and then perform the base conversion. It is quite easy to write a computer programme which does this. Although it will do its internal calculations in binary, the value of "base" can be 2 or 10, or 16, or 60 (Babylonian) and all will be well.

So 11.00100100001... is indeed the start of the binary representation of pi as a proper digit string in binary, just as 3.1415 is a proper digit string in decimal of an approximate value for pi, which on the IBM1620 (a base ten computer) might appear in storage as 3141501 where the bold type indicate tags associated with the digit: the IBM1620, a discrete transistor design (pre-integrated circuits, that is) offered indefinite precision floating-point arithmetic via hardware (not software); a number was located by the start digit of its address and if that digit was tagged, it was a negative number. The digits of the number continued until the next tagged digit marking the end thus the tag on 5, and for floating-point numbers was followed by a two-digit power with the tag marking the end of the power. Because it normalised to the 0.xxxx style (rather than the x.xxx style), 3.1415 is represented as .31415x10 thus the exponent field of 01, and if I felt like typing them, I could have added many more than five digits. Reading memory dumps of numbers on the IBM1620 was so easy... No "little-endian" madness. NickyMcLean 21:41, 17 August 2006 (UTC)

Humm, on review, I think I recall now that the IBM1620 addressed numbers by their rightmost digit (whose tag indicated the sign), and the high-order digit in memory (indefinitely off to the left, at lower addresses) would have a "field mark" tag on it. For floating-point, the address point thus led directly to the exponent field. No matter, the fundamental point is that numbers could be hundreds of digits long, and though represented in decimal, not all digits had the same interpretation as a part of the number because some were exponent digits. NickyMcLean 21:51, 17 August 2006 (UTC)

0.6/0.2

I was reading this article a while ago and I saw something (I think in the "problems" section) about what happens when a computer tries to find int (0.6/0.2), where int(x) is the largest integer not larger than x. It said something like "since neither 0.6 nor 0.2 can be exactly represented in binary, the computer evaluates 0.6/0.2 to 2.999999998, which the computer will happily convert to 2". I can't find it in the page archive, so could someone put something like that on the page, because I think it's a good example of a problem with floating-point arithmetic. (P.S. I've tried calculating int (0.6/0.2) on a computer, and it does sometimes come out to 2.)

hyphen or not?

The article is inconsistent about "floating point" versus "floating-point". I think we should decide on one form and use it. Does anyone have a preference for one variant or the other? Neilc 04:15, 12 September 2005 (UTC)

When it is used as a compound adjective (as in "floating-point arithmetic"), then it should be hyphenated according to good English punctuation style. When it is used as a noun (as in the article title), it should not be hyphenated. —Steven G. Johnson 16:02, September 12, 2005 (UTC)

Literal 0.1 unrepresentable?

In the section "Problems with floating point" it says that the literal 0.1 is unrepresentable, I'm not quite understanding this, can someone please explain? - Xgkkp 18:36, 5 October 2005 (UTC)

It cannot be represented exactly by a binary (base 2) fraction, as it requires powers of 5 to be exact. For examples, see: ['problems with binary floating-point'] mfc

Shouldn't we mention how operations on floating-point numbers are (usually) carried out?

Most implementations of floating-point numbers do not only specify how such numbers are represented but also specify what results operations on them must produce. More precisely, one usually requires a op_f b:= rnd(a op b) for any two floating-point numbers a,b, and any (here binary) operation op (like +, -, /, *, sqrt, etc.). Here, rnd is the function that rounds its argument to the closest floating-point number, and op_f is the operation op for floating-point numbers.

I wonder whether the article should not at least mention this "fundamental property" because it is this very property that allows us to analyze what a calculation actually does! For instance, the requirement "a op_f b:= rnd(a op b)" implies that (for normalized numbers) a op_f b = (a op b) (1+eps) where |eps| is bounded. Using this, you can perform an analysis of what a formula like ((a +_f b) -_f c) *_f d), for instance, actually computes.

I know that not all implementations of floating-point numbers require a op_f b:= rnd(a op b) (I think GNU MP does not, but there are "patches" that make it do so). Nonetheless, IEEE 754 does respect it (at least for normalized numbers, if I am not mistaken). Adding a section on this "fundamental property" (anyone has a better name?!) would, I think, help a lot to understand that we CAN work and calculate with floating-point numbers (and do not have to HOPE that it is going to work well).

(I am willing to write something, of course, with your help, but would like to first ask what you think of the idea.) hbf 02:14, 25 November 2005 (UTC)

It seems like a good idea to include how floating point mathematical instructions are calculated and how to calculate the error in the resulting number. (This is what you're talking about right?) You mention 'eps' - it seems that eps would vary with the function i.e. |eps (+)| = |eps (-)| <> |eps (sqrt)| . (hope my syntax makes sense without explanation)
I assume that eps is pretty much the same accuracy as the mantissa in simple functions like add.
Unfortunately my knowledge of actual fp implementation is not good. I probably wouldn't be able to help much except check your maths.
I think the correct term includes words like 'precision of floating point operations' - is precision the word you were looking for?
I'm not sure if you description 'how operations on floating-point numbers are (usually) carried out' includes computer hardware e.g. structure of logic gates to create for example a floating point 'adder' (if so maybe I can help) or were you thinking in purely mathematical terms.

On a vaguely similar subject I was thinking there should be an explanation of what floating point numbers are actually good for, with comparison with fixed point arithmetic. (in terms of say a physical simulation of real world physics e.g. floating point good for light intesity at distance due to the non linear nature of the variation. but fixed point good for 'euclidian space' vectors - (given sensible programming) since these are linear quantities. I'm currently looking for the correct page to include it in as my topic spans two pages. HappyVR 16:29, 11 March 2006 (UTC)

Scientific notation

I added a link to the closely related Scientific notation. I noticed it is already linked in the text but I thought there should be a specific link seeing as the two are so closely related.HappyVR 16:40, 11 March 2006 (UTC)

Implementation

I removed the following comment left by an editor without account at the article:

This is all very interesting, but how are they stored? Many people wish to know this!

I do hope somebody will write about the "fundamental property", mentioned above, and perhaps give more details about the implementation. -- Jitse Niesen (talk) 03:25, 20 March 2006 (UTC)

?

I removed this :
"A floating point number can be seen as a large integer, were the most significant bit is stored, then the number of the following identical bits, and then the remaining bits. Additionally, a constant denominator is defined to allow for fractions, and a constant bias to have a zero."
Not saying it's wrong - just questioning whether it helps explain anything? Seems (to me) to be describing a different method of storing numbers - it's definately not clear to me.HappyVR 19:57, 23 March 2006 (UTC)

problems - cancelation

"Cancellation - subtraction between nearly equivalent operands"

subtraction of equivalent operands does what? Does it yeild 0? That should be explicit. Fresheneesz 19:43, 25 May 2006 (UTC)

example - not IEEE standard

Why is the example not in IEEE standard? Is it in any standard? Why would we do it that way on this page when a better standard exists? Fresheneesz 19:44, 25 May 2006 (UTC)

mantissa - not informal

"which is called the significand or, informally, mantissa"

At Talk:Significand, I assert that mantissa is not the same thing as a significand, nor is it informal. Please discuss there. Fresheneesz 20:01, 25 May 2006 (UTC)

Base 2 vs base b

I think there should be a clear distinction on this page between base 2 and base b. Floating point numbers are, by far and away, mostly used in binary number representation. We should have a general definition using an arbitrary base, but in computers, the base is 2, and that should be the focus. Fresheneesz 20:05, 25 May 2006 (UTC)

My recent (and ongoing) edit.

I'm attempting to improve this article. I hope to add material on actual computer representation, and overflow/underflow/subnormal results. I hope that this will address many of the questions raised on this talk page.

By the way, the "fundamental property" noted above (that floating point arithmetic is done by effectively carrying out the operation to infinite precision and then rounding), is true. The IEEE standard mandates that compliant computers get this result. For square root, which is within the domain of the IEEE standard, this is very hard, but is nevertheless mandated. More complicated things like sin/cos/exp/log are (fortunately for library authors) not within the IEEE standard, and are only "almost always" correct.

William Ackerman 02:00, 5 June 2006 (UTC)

Looks very good; thanks for your efforts. However, you seem to use different definitions of the significand s. The article says:
  • the revolution period of Io is simply e=5 ; s=1528535047
  • the value of the significand obeys 1 ≤ s < b
  • the mathematical value of a floating-point number is .sssssssss...sss × be
These statements seem to contradict each other. Additionally, I thought that the IEEE standard does not mandate banker's rounding, but allows different kinds of rounding (or perhaps, it requires that various kinds of rounding be implemented?). In that case, the phrase "the technique of Banker's rounding is used" is too rigid. -- Jitse Niesen (talk) 04:33, 5 June 2006 (UTC)
You caught the page between my first version and a cleanup edit :-) It happens that my first handwritten draft used a different definition of point location, at the extreme left end, that I happen to prefer. (POV!!!) When I saw that I would be contradicting both common IEEE conventions and explicit IEEE terminology and definitions, I retreated, and changed things to s.sssss. William Ackerman 18:20, 5 June 2006 (UTC)

I have done more cleanup, and have taken the liberty of removing the "cleanup" flag from this page. William Ackerman 02:09, 8 June 2006 (UTC)

I have softened the assertion that "mantissa" is wrong, taking into account the sensibilities expressed earlier on this page that its usage is so widspread that calling it wrong is too harsh.

Also, I have put in material describing the "fundamental property" (as it has been called on this talk page, though not the article itself) that the result is always (mandated by IEEE) the nearest representable value. This property is crucial! It is the most important achievement of IEEE 754. The way I have expressed it doesn't do it justice. Can anyone rearrange this to describe this property in the way it deserves?

Also, I have separated the aspects of the rounding mode from the aspects of overflow and infinity creation. While the rounding mode can affect whether an infinity is created, it's a two-stage process -- first get the ideal exponent, and then see whether it fits. William Ackerman 01:17, 19 June 2006 (UTC)

Exponent overflow/underflow

I think that the conditions of exponent overflow (and underflow) should be distinct from the more pure notions of +-infinity which should be reserved for the cases where no exponent would be big enough. In implementations of floating-point arithmetic, the existing protocol requires messing with odd compiler options and strange routines that set and test various processor states which are dependent on the specific processor. Not being a standard part of a language (even in number-crunching fortran) means that such programmes are non-portable, and I haven't attempted to use these facilities. I'd prefer the collection of values to include +-inf, +-overflow, +-underflow, plus undefined (for non-initialised floating-point numbers, though I of course Always Initialise variables Before Reference) as well as the infamous NaN (resulting from computation). It is particularly annoying that different events cause different bit patterns for a resulting NaN, so that testing if x = NaN fails. Fortran offers IsNaN(x), but this is of course non-standard, since of course not all computer hardware designs recognise such a bit pattern. NickyMcLean 21:01, 16 August 2006 (UTC)

By "cases where no exponent would be big enough" do you mean numbers that could not be represented no matter how large the exponent field is? If so, that number is truly infinite. Common usage and terminology uses a weaker definition of floating-point infinity -- any number that can't be represented by the existing exponent field. That's about 10^308. You also mention unsatisfactory and non-portable results of tests of the form "x==NaN". Tests for NaN and INF should not be done that way, since the hardware (for complex but good reasons) often considers NaN to be not equal to anything, not even another NaN. You should always use things like IsNaN(x) or ieee_is_nan(x) in Fortran, or _isnan(x) in C. These should not have portability problems -- in each case, the compiler/library is supposed to understand whatever bit representation the current hardware uses, and act accordingly. That is, if a program produces a NaN, _isnan(x) should return true on any hardware, no matter how that hardware encodes those bits. William Ackerman 00:22, 18 August 2006 (UTC)
No, overflow is not infinity. For any given fp scheme, there is some maximum value for the exponent (positive, and negative) - whatever it is, if x is a number with over half that value for its exponent, then x*x will overflow (or underflow, for negative exponents) but this should not be regarded as being infinity at all.
True, but the hardware has no choice. In floating-point hardware, INF doesn't mean "the thing you learned about in school as a way of thinking about divergent integrals". It means "Help! I overflowed!" William Ackerman 00:40, 31 August 2006 (UTC)
Well, which is to be the master? I agree that the hardware behaves as you say (because it does), but, I want the hardware to (be designed to) follow what I want, not for me to adjust my thoughts to conform to what the hardware does (even though on a particular computer, I do have to, with resentment), and I'm arguing that it should do otherwise to suit me (and of course, I hope others will be suited also) thus I do wish to distinguish proper infinities (cast up by the mathematics, and recognised as such by my algorithm which of couse does brilliant things in conformance with the mathematics, which is hopefully in good conformance with the physical situation, but that's something else), from overflows caused by mere arithmetical limitations, which limits are annoyingly different in different number formats on different machines. Thus I desire +-oflo as well as +-inf and agree that more combinations arise but that's no problem to me as it suits me.... NickyMcLean 21:46, 31 August 2006 (UTC)
This applies for any finite exponent limit, whatever it is. Infinity is a lot further out. Overflow might be the result of a small change: if x is close to the largest fp number that can be represented, 2x will overflow, likewise if x is close to the smallest (non-zero) number, x/2 will underflow. (I'm not persuaded of the utility of "denormalised" numbers close to zero: their existence just exacerbates the difficulty of preparing a comprehensive algorithm that must now deal with two types of numbers rather than one) Physicists delight in formulae such as e**3/h**2 *m (charge of electron planck's constant, mass of electron) all of which are very small, so one hopes that during an expression's evaluation there are extra bits for the exponent not available in the storage form. Otherwise, overflow results even though the result is within fp range.
A proper infinity would for example be generated by a/b where b is zero, though full propiety in general requires that this be the result of an analysis involving (limit, b to zero, of a/b) rather than some blunder in the method producing a divide by zero. Similarly, tangent(pi/2) should spit back infinity (ah, which sign?), though to pick nits, the limited precision fp representation of pi/2 would not be pi/2 exactly so tangent(approx(pi/2)) might merely be a very large number (but not infinity) for which overflow ought to be the result. Likewise, one might argue that arctan(0,0) should return ? (or NaN) because a vector of zero length points in no direction.
You say you'd like different kinds of NaN for atan2(0,0), 0/0, overflow/overflow, etc. As far as I know, the IEEE commettee didn't provide for that. If such distinctions existed, the rules for how all the various types of overflows, infinities, and NaNs propagate through all the various operations would become way too complicated. In practice, these things turn into NaN pretty quickly. The main reason for providing INF is to let programmers catch things early, if they so choose. William Ackerman 00:40, 31 August 2006 (UTC)
I'll see if I can provoke different "values" for NaN in some tests. Amusingly enough, I have wallowed in this slough before (half-hourly measurements of electrical load at hundreds of substations) where data is not available with certainity. A value might be x, and associated with it in my scheme was a character code. Blank for "good", otherwise one of "fubrom" for various failure states (Failure of the meter, Unavailable number, Broken tape, Reset count error, Overflow in count (yay!), Movement failure (the paper tape didn't advance)) Well, obviously in summations there could be combinations. Blank+Blank stayed Blank(yay), Blank+fubrom became fubrom, one fubrom with a different fubrom became ?. All good fun, but it had to be done via associated tests, though careful organisation and phasing meant that only if within a day's data there were non-blank codes did the jiggling start. It was not at all satisfactory to ignore these details, despite the cost in extra processing. (Alas, staff using this system resorted to editing the source data files (!) to remove the fubrom codes so that their summations would appear without the warning codes and there would be no need to fix the errors, for there were no errors...) Now, if I could be certain of a multi-value NaN state (where any NaN value would not be admitted to a summation, nor would a count of good values include them, so something like SUM(a)/CountValid(a) would work) I'd be happier becaue the one datum would encase both the value and failing that, the codes. Thus, my proposal would be for a miscegnatory NaN (my usage of ? from mismatched fubroms), NaN codes as a consequence of various established misbehaviours, and an allowance for "user-defined" NaN codes. Currently I am dealing with "missing datum" via an explicit floating-point value that is not expected to appear (exactly) via calculations on normal data. I had wanted -666.666E666 but it is out of the available fp range, so I have chosen -666.666E33 with careful usage. The data are stored as real*4 in a random-access disc file, but all calculations are via real*8 so the BAD value is real*8 but is assigned -666.666e33's real*4 binary value. And it is really tedious to be forever having to check for BAD values, at a cost in crunch speed, when the hardware would do better. But because IsNaN is not standard (and the prog. is to run on a variety of systems in principle) I have resolved for the moment to stick with it.NickyMcLean 21:46, 31 August 2006 (UTC)
Thus one introduces further shadings. infinity/infinity generates one sort of NaN, but overflow/overflow (and other combinations) should generate another sort. In the first case, the number cannot be other than infinity due to the limit argument so no finite dynamic range for the fp scheme would suffice, but in the overflow case, it might well be that the same calculation and data performed with a greater dynamic range fp. scheme would result in a valid result with no overflows anywhere along the line. Having messed with an IBM1130 where the dynamic range was small enough to be met often (about 10**36 or so I think) one often had to recast formulae. Thus, (e/h)**2*e*m worked.
This trick for programming around the exponent range limitations of machines like the 1130 is similar to the tricks that people use (the Archimedes pi example!) to work around accuracy limitations. In each case it's unfortunate that such things are necessary, but floating-point is a big set of compromises. William Ackerman 00:40, 31 August 2006 (UTC)
With regard to the IsNaN function, the compaq "visual" fortran manual v6.6 refers to it as a non-standard function, which it is; as with other ad-hoc extensions to a compiler, there is no guarantee that other compilers will have the same extension, still less that the next standardisation will include it. Further, if there are multiple representations that count as a NaN value, I too would like to be able to set and use such code values for the benefit of my processing. (One might be "missing datum", another might be "failed to converge", etc etc) Without a clear usage of equality, surely a very basic concept, this is not helpful. NickyMcLean 05:28, 19 August 2006 (UTC)
All I can say here is that the industry has not yet standardised things like IsNaN, or ways to instantiate a NaN value. William Ackerman 00:40, 31 August 2006 (UTC)
Some tests later, I got around to RTFM (associated via "help" with the compiler), which as usual is not specific which is why tests have to be concocted because the accursed manual writers rarely present full details, merely namechecking some issues. Here is an extract from the Compaq "visual" furrytran compiler concerning NaN
Not a Number
Not a Number (NaN) results from an operation involving one or more invalid operands. For instance 0/0 and SQRT(-1) result in NaN. In general, an operation involving a NaN produces another NaN. Because the fraction of a NaN is unspecified, there are many possible NaNs. Visual Fortran treats all NaNs identically, but provide two different types:
Signaling NAN, which has an initial fraction bit of 0 (zero).
Quiet NaN, which has an initial fraction bit of 1.
The output value of NaN is NaN.
My tests could not cause Sqrt(neg) to generate a NaN despite the remark in the damn manual; there might be some option somewhere or other arrangement to enable it to produce a NaN rather than an error message, but I couldn't find it and did not want to embark on the supposed option of writing my own error-handling routines. However, the key phrase is "there are many possible NaNs" even though this compiler system restricts itself to two, itself a number not equal to one. Agreed, the IEEE specification fails to specify multiple values for NaN, merely allows them without inference (grr), so I'd be in favour of a scheme such as I described. In usage, the fp hardware (well, firmware) is ordinarily about to do something complex with two fp numbers; if one or both has a special value, the complexity of dealing with that ought to be less. So, a NaN code for "mangled", then codes for 0/0, etc, then "user-defined" codes should not cause much trouble. Basically, (NaN op x) gives that NaN, (NaNa op NaNb) gives the general NaN code unless perhaps a = b. Seems simple enough. The values could be revealed as NaN0, NaN1, etc. NickyMcLean 22:06, 4 September 2006 (UTC)