Computer Systems Organization
Session 5 Main Theme Bits, Bytes, and Floats Dr. Jean-Claude Franchitti
New York University
Computer Science Department Courant Institute of Mathematical Sciences
Presentation material partially based on textbook slides Ce Se: A Pgae Peece
by Randal Bryant and David OHaa as well as fa f Mcae Oe b: Neca Computing with IEEE Floating Point Arithmetic Slides copyright © 2020
1
Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
2
What is the class about?
Course description and syllabus:
» http://www.nyu.edu/classes/jcf/CSCI-GA.3033-012/
» http://www.cs.nyu.edu/courses/fall20/CSCI-UA.0205–001/ » Accessible via NYU Classes
Textbooks:
» Comper Ssems: A Programmers Perspecie
Randal Bryant and David O’Hallaron Pearson
ISBN-10: 013409266X, ISBN-13: 978-0134092669, 3rd Edition (03/2015) » Recommended:
» The C Programmning Language, Brian W Kernighan and Dennis Ritchie
Prentice Hall; ISBN-10: 0131103628; ISBN-13: 978-01311103627, 2nd Edition (04/88)
3
Icons / Metaphors
Information
Common Realization Knowledge/Competency Pattern Governance
Alignment
Solution Approach
4
4
Bits, Bytes, and Floats: Detailed Agenda
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication
Floating point in C Summary
5
Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
6
Bits, Bytes, and Floats
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication
Floating point in C Summary
7
Fractional binary numbers
What is 1011.1012?
Turing Award 1989 to William Kahan for design of the IEEE Floating Point Standards 754 (binary) and 854 (decimal)
8
Fractional Binary Numbers
2i
2i-1
•• •
4
2
1
bi
bi-1
•••
b2
b1
b0
b-1
b-2
b-3
•••
b-j
1/2
1/4
1/8
Representation
» Bits to right of “binary point” represent fractional
powers of 2
» Represents rational number:
2-j
9
•• •
Fractional Binary Numbers: Examples
Value 5 3/4
2 7/8 1 7/16
Representation
101.112 010.1112 001.01112
Observations
Divide by 2 by shifting right (unsigned)
Multiply by 2 by shifting left
Numbers of form .…2 are just below 1.0
///…/i …➙1.0 Use notation 1.0 ε
10
Representable Numbers
Limitation #1
» Can only exactly represent numbers of the form x/2k • Other rational numbers have repeating bit representations
» Value • 1/3
• 1/5 • 1/10
Representation
0.0101010101[01]2 0.001100110011[0011]2 0.0001100110011[0011]2
Limitation #2
» Just one setting of binary point within the w bits
• Limited range of numbers (very small values? very large?)
11
Why Not Fractional Binary Number?
Not efficient
3 * 21001010000000 ….. 0
Given a finite length (e.g. 32-bits), cannot represent very large nor very small numbers (ε0)
12
Bits, Bytes, and Floats
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication
Floating point in C Summary
13
IEEE Floating Point
IEEE Standard 754
» Established in 1985 as uniform standard for floating point
arithmetic
• Before that, many idiosyncratic formats
» The IEEE standards committee consisted mostly of hardware people, plus a few academics led by W. Kahan at Berkeley.
» Supported by all major CPUs
Driven by numerical concerns
» Nice standards for rounding, overflow, underflow
» Consistent representation of floating point numbers by all machines .
» Consistent treatment of exceptional situations such as division by zero.
» Hard to make fast in hardware
• Numerical analysts predominated over hardware designers in defining standard
14
Floating Point Representation
Numerical Form:
(–1)s M 2E
» Sign bit s determines whether number is negative or positive
» Significand M normally a fractional value in range [1.0,2.0).
» Exponent E weights value by power of two
Encoding
» MSB s is sign bit s
» exp field encodes E (but is not equal to E) » frac field encodes M (but is not equal to M)
s
exp
frac
15
Precision Options
Single precision: 32 bits
1 8-bits 23-bits
Double precision: 64 bits
1 11-bits 52-bits
Extended precision: 80 bits (Intel only) 1 15-bits 63 or 64-bits
s
exp
frac
s
exp
frac
s
exp
frac
16
Three Encoding Schemes Based on Exp
exp ≠ 0..0 or 11…1 normalized encoding
exp = 0… 000 denormalized encoding
exp = 1111…1 special value encoding » frac = 000…0
» frac = something else
17
Naed Vae
When: exp ≠ 000…0 and exp ≠ 111…1
Exponent coded as a biased value: E = Exp – Bias » Exp: unsigned value of exp field
» Bias = 2k-1 – 1, where k is number of exponent bits
• Single precision: 127 (Exp: 1…254, E: -126…127)
• Double precision: 1023 (Exp: 1…2046, E: -1022…1023)
Significand coded with implied leading 1: M = .xxx…x2 » xxx…x:bitsoffracfield
» Minimum when frac… (M = 1.0)
» Maximum when frac… (M = 2.0 ε
» Get extra leading bit for “free”
v = (–1)s M 2E
Range(E)=[-126,127] Range(E)=[-1022,1023]
18
Normalized Encoding Example
Value: float F = 15213.0;
» 1521310
Significand M =
frac =
Exponent E =
Bias = Exp =
Result:
s exp
= 111011011011012
= 1.11011011011012 x 213
1.11011011011012 110110110110100000000002
muumuu
25L I 2 E O
v = (–1)s M 2E E = Exp–Bias
Z th I
13
127
140 = 100011002
ion air
11011011011010000000000
frac
0
10001100
19
Deaed Vae (Sba Ecd a e 854 Sadad)
Condition: exp …
Exponent value: E = 1 – Bias (instead of E = 0 – Bias)
Significand coded with implied leading 0: M = 0.xxx…x2, instead of M = 1.xxx…x2
• xxx…x: bits of frac
Cases
» exp=0000,frac=0000
• Representszerovalue
• Note distinct values: +0 and –0 (why?) » exp = 0000, frac ≠ 0000
• Numbers closest to 0.0 • Equispaced
v = (–1)s M 2E E = 1–Bias
20
Special Values Encoding
Condition: exp = 1111
Case: exp = 1111, frac = 0000
» Represents value (infinity)
» Operation that overflows
» Both positive and negative
» E.g., 1.0/0.0 = −1.0/−0.0 = +, 1.0/−0.0 = −
Case: exp = 1111, frac ≠ 0000
» Not-a-Number (NaN)
» Represents case when no numeric value can be determined » E.g.,sqrt(–1),−,0
21
Visualization: Floating Point Encodings
− NaN
−Normalized
+Denorm +Normalized 0 +0
+
NaN
−Denorm
22
Bits, Bytes, and Floats
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication Floating point in C
Summary
23
Tiny Floating Point Example
s
exp
frac
1 4-bits 3-bits
8-bit Floating Point Representation » the sign bit is in the most significant bit
» the next four bits are the exponent, with a bias of 7 » the last three bits are the frac
Same general form as IEEE Format » normalized, denormalized
» representation of 0, NaN, infinity
24
Dynamic Range (Positive Only)
0 0000 000
0 0000 001
Denormalized 0 0000 010
-6 0
-6 1/8*1/64
-6 2/8*1/64
-6 6/8*1/64
-6 7/8*1/64
-6 8/8*1/64
-6 9/8*1/64
-1 14/8*1/2 -1 15/8*1/2 0 8/8*1
0 9/8*1
0 10/8*1
7 14/8*128
7 15/8*128
n/a inf
= 1/512
= 2/512
= 6/512
= 7/512
= 8/512
= 9/512
= 14/16 = 15/16 =1
= 9/8
= 10/8
= 224 = 240
closest to zero
largest denorm smallest norm
closest to 1 below closest to 1 above
largest norm
numbers
0 0000 110 0 0000 111 0 0001 000 0 0001 001
0 0110 110 0 0110 111 0 0111 000
sexpfracE Value
Normalized
numbers 0 0111 001
0 0111 010
0 1110 110
0 1110 111
0 1111 000
v = (–1)s M 2E n: E = Exp – Bias d: E = 1 – Bias
25
Distribution of Values
6-bit IEEE-like format » e = 3 exponent bits
» f = 2 fraction bits »Bias is 23-1-1 = 3
Notice how the distribution gets denser
s
exp
frac
toward zero.
8 values
1 3-bits 2-bits
-15 -10 -5 0 5 10 15
Denormalized Normalized Infinity
26
Distribution of Values (close-up view)
6-bit IEEE-like format » e = 3 exponent bits
» f = 2 fraction bits
» Bias is 3
s
exp
frac
1 3-bits 2-bits
-1 -0.5 0 0.5 1
Denormalized Normalized Infinity
27
Special Properties of the IEEE Encoding
FP Zero Same as Integer Zero » All bits = 0
Can (Almost) Use Unsigned Integer Comparison » Must first compare sign bits
» Must consider −0 = 0
» NaNs problematic
• Will be greater than any other values • What should comparison yield?
» Otherwise OK
• Denorm vs. normalized • Normalized vs. infinity
28
Bits, Bytes, and Floats
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication
Floating point in C Summary
29
Floating Point Operations: Basic Idea
x +f y = Round(x + y)
x f y = Round(x y)
Basic idea
» First compute exact result
» Make it fit into desired precision
• Possibly overflow if exponent too large
• Possibly round to fit into frac
30
Rounding
Rounding Modes (illustrate with $ rounding)
$1.40 $1.60 $1.50 $2.50 –$1.50
» Towards zero $1 » Round down (−) $1 » Round up (+) $2 » Nearest Even (default) $1
$1 $1 $1 $1 $2 $2 $2 $2
$2 –$1 $2 –$2 $3 –$1 $2 –$2
31
Closer Look at Round-To-Even
Default Rounding Mode
» Hard to get any other kind without dropping into assembly
» All others are statistically biased
• Sum of set of positive numbers will consistently be over- or under-
estimated
Applying to Other Decimal Places / Bit Positions
» When exactly halfway between two possible values • Round so that least significant digit is even
» E.g., round to nearest hundredth
7.8949999 7.8950001 7.8950000 7.8850000
7.89 (Less than half way) 7.90 (Greater than half way) 7.90 (Half way—round up) 7.88 (Half way—round down)
32
Rounding Binary Numbers
Binary Fractional Numbers
» “Even” when least significant bit is 0
» “Half way” when bits to right of rounding position = 1002
Examples
» Round to nearest 1/4 (2 bits right of binary point)
Value 2 3/32 2 3/16 2 7/8 2 5/8
Binary 10.000112 10.001102 10.111002 10.101002
Rounded Action
10.002 (<1/2—down) 10.012 (>1/2—up) 11.002 ( 1/2—up) 10.102 ( 1/2—down)
Rounded Value 2
2 1/4
3
2 1/2
33
FP Multiplication
(–1)s1 M1 2E1 x (–1)s2 M2 2E2 Exact Result: (–1)s M 2E
» Sign s:
» Significand M: » Exponent E:
s1 ^ s2 M1 x M2 E1 + E2
Fixing
» If M ≥ 2, shift M right, increment E
» If E out of range, overflow
» Round M to fit frac precision
Implementation
» Biggest chore is multiplying significands
34
Floating Point Addition
(–1)s1 M1 2E1 + (-1)s2 M2 2E2 »Assume E1 > E2
Exact Result: (–1)s M 2E
»Sign s, significand M:
• Result of signed align & add
»Exponent E: E1
Get binary points lined up
(–1)s1 M1 +
E1–E2 (–1)s2 M2
Fixing
»If M ≥ 2, shift M right, increment E
»if M < 1, shift M left k positions, decrement E by k »Overflow if E out of range
»Round M to fit frac precision
(–1)s M
35
Mathematical Properties of FP Add
Compare to those of Abelian Group
» Closed under addition? Yes
• But may generate infinity or NaN
» Commutative?
Yes
» Associative? No
• Overflow and inexactness of rounding
• (3.14+1e10)-1e10 = 0, 3.14+(1e10-1e10) = 3.14
» 0 is additive identity? Yes
» Every element has additive inverse? • Yes, except for infinities & NaNs
Monotonicity
» a ≥ b ⇒ a+c ≥ b+c?
• Except for infinities & NaNs
Almost
Almost
36
Mathematical Properties of FP Mult
Compare to Commutative Ring
» Closed under multiplication?
• But may generate infinity or NaN
» Multiplication Commutative?
Yes Yes
» Multiplication is Associative? No
• Possibility of overflow, inexactness of rounding
• Ex:(1e20*1e20)*1e-20=inf,1e20*(1e20*1e-20)=1e20
» 1 is multiplicative identity? Yes
» Multiplication distributes over addition? No
• Possibility of overflow, inexactness of rounding
• 1e20*(1e20-1e20)= 0.0, 1e20*1e20 – 1e20*1e20 = NaN
Monotonicity
» a ≥ b & c ≥ 0 ⇒ a * c ≥ b *c?
• Except for infinities & NaNs
Almost
37
Bits, Bytes, and Floats
Background: Fractional binary numbers IEEE floating point standard: Definition Example and properties
Rounding, addition, multiplication
Floating point in C Summary
38
Floating Point in C
C Guarantees Two Levels »float single precision »double double precision
Conversions/Casting
» Casting between int, float, and double changes bit representation
» double/float int
• Truncates fractional part
• Like rounding toward zero
• Not defined when out of range or NaN: Generally sets to TMin
» int double
• Exact conversion, as long as int has ≤ 53 bit word size
» int float
• Will round according to rounding mode
39
Floating Point Puzzles
For each of the following C expressions, either: » Argue that it is true for all argument values
» Explain why not true
ROUNDINDS NOTSAME NOM
• x == (int)(float) x
• x == (int)(double) x
• f == (float)(double) f Yes • d == (double)(float) d NO • f == -(-f);
• 2/3 == 2/3.0 NO
int = ; float f = ; doble d = ;
Assume neither dnorfis NaN
• d<0.0 •d>f
• d*d>=0.0 • (d+f)-d == f
Yes
Yes
⇒ ((d*2)<0.0) ⇒ -f>-d
40
Creating Floating Point Number
Steps
» Normalize to have leading 1
» Round to fit within fraction
» Postnormalize to deal with effects of rounding
3-bits
s
exp
frac
Case Study
» Convert 8-bit unsigned numbers to tiny floating point format
Example Numbers
128 10000000 15 00001101 33 00010001 35 00010011
138 10001010 63 00111111
1 4-bits
41
Normalize
s
exp
frac
Requirement 1 4-bits 3-bits
» Set binary point so that numbers of form 1.xxxxx
» Adjust all to have leading one • Decrement exponent as shift left
Value Binary
128 10000000 15 00001101 17 00010001 19 00010011
138 10001010 63 00111111
Fraction Exponent
1.0000000 7
1.1010000 3
2 2
1.0001000
1.0011000
1.0001010 7
1.1111100
4 24 4 24
27 5 25
42
Rounding
1.BBGRXXX
Sticky bit: OR of remaining bits
Round up conditions
» Round = 1, Sticky = 1 ➙ > 0.5
» Guard = 1, Round = 1, Sticky = 0 ➙ Round to even
Last Bit
nun
Guard bit: LSB of result Round bit: 1st bit removed
Value Fraction
128 1.0000000 II
15 1.1010000 I
17 1.0001000 A
19 1.0011000
138 1.0001010
63 1.1111100 II
GRS Incr?
000 N 100 N 010 N 110 Y 011 Y 111 Y
Rounded
1.000
1.101
1.000
1.010
1.001
10.000
43
Postnormalize
Issue
» Rounding may have caused overflow
» Handle by shifting right once & incrementing exponent
Value Rounded Exp Adjusted Result
128 1.000 7 15 1.101 3 17 1.000 4 19 1.010 4
138 1.001 7 63 10.000 5
128 15 16 20 134 1.000/6 64
44
Interesting Numbers
Description
{single,double} Numeric Value
0.0
2– {23,52} x 2– {126,1022}
(1.0 – ε) x 2– {126,1022}
1.0 x 2– {126,1022}
1.0
(2.0 – ε) x 2{127,1023}
Zero
Smallest Pos. Denorm. » Single ≈ 1.4 x 10–45
» Double ≈ 4.9 x 10–324
Largest Denormalized » Single ≈ 1.18 x 10–38 » Double ≈ 2.2 x 10–308
exp frac
00…00 00…00 00…00 00…01
00…00 11…11
Smallest Pos. Normalized
» Just larger than largest denormalized
One 01…11 00…00
Largest Normalized 11…10 11…11 » Single ≈ 3.4 x 1038
» Double ≈ 1.8 x 10308
00…01 00…00
45
Bits, Bytes, and Floats: Summary
As for integers, floats are stored in memory as 1s and 0s
The binary presentation by itself does not carry a
meaning, it depends on the interpretation.
IEEE Floating Point has clear mathematical properties
Represents numbers of form (–1)s x M x 2E
One can reason about operations independent of implementation
» As if computed with perfect precision and then rounded
Not the same as real arithmetic
» Violates associativity/distributivity
» Makes life difficult for compilers & serious numerical applications programmers
46
Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
47
Assignments & Readings
Readings
» Slides and Handouts posted on the course web site
» Syllabus, make sure you understand the rules associated with grading, due dates, lateness, etc.
» Textbook: Chapter 2.4 Assignment #1 / Lab #1
» Lab #1 TBD in later sessions
Development environment
» C development environment setup
» Create GitHub account
» See Announcements regarding invitation to join the course GitHub and related instructions to access the materials for the course and recitations (including private versions of them that you will work on during recitations)
48
Next Session: C Programming
49
Questions, Comments, Discussions ?
50