iki10230 pengantar organisasi komputer bab 6: aritmatika

65
1 IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika 7 & 14 Mei 2003 Bobby Nazief ([email protected]) Qonita Shahab ([email protected]) bahan kuliah: http://www.cs.ui.ac.id/kuliah/iki10230/ Sumber : 1. Hamacher. Computer Organization, ed-5. 2. Materi kuliah CS61C/2000 & CS152/1997, UCB.

Upload: rhea

Post on 15-Jan-2016

50 views

Category:

Documents


0 download

DESCRIPTION

IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika. Sumber : 1. Hamacher. Computer Organization , ed-5. 2. Materi kuliah CS61C/2000 & CS152/1997, UCB. 7 & 14 Mei 2003 Bobby Nazief ([email protected]) Qonita Shahab ([email protected]) bahan kuliah: http://www.cs.ui.ac.id/kuliah/iki10230/. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

1

IKI10230Pengantar Organisasi Komputer

Bab 6: Aritmatika

7 & 14 Mei 2003

Bobby Nazief ([email protected])Qonita Shahab ([email protected])

bahan kuliah: http://www.cs.ui.ac.id/kuliah/iki10230/

Sumber:1. Hamacher. Computer Organization, ed-5.2. Materi kuliah CS61C/2000 & CS152/1997, UCB.

Page 2: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

2

Number Representation

Page 3: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

3

How to Represent Negative Numbers?

° So far, unsigned numbers

° Obvious solution: define leftmost bit to be sign! • 0 => +, 1 => -

• Rest of bits can be numerical value of number

° Representation called sign and magnitude

Page 4: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

4

Shortcomings of sign and magnitude?

° Arithmetic circuit more complicated• Special steps depending whether signs are the same or not

° Also, Two zeros• 0x00000000 = +0ten

• 0x80000000 = -0ten

• What would it mean for programming?

° Sign and magnitude abandoned

Page 5: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

5

Another try: complement the bits

° Example: 710 = 001112 -710 = 110002

° Called one’s Complement

° Note: postive numbers have leading 0s, negative numbers have leadings 1s.

00000 00001 01111...

111111111010000 ...

° What is -00000 ?

° How many positive numbers in N bits?

° How many negative ones?

Page 6: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

6

Shortcomings of ones complement?

° Arithmetic not too hard

° Still two zeros• 0x00000000 = +0ten

• 0xFFFFFFFF = -0ten

• What would it mean for programming?

° One’s complement eventually abandoned because another solution was better

Page 7: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

7

Search for Negative Number Representation

° Obvious solution didn’t work, find another

° What is result for unsigned numbers if tried to subtract large number from a small one?• Would try to borrow from string of leading 0s,

so result would have a string of leading 1s

• With no obvious better alternative, pick representation that made the hardware simple: leading 0s positive, leading 1s negative

• 000000...xxx is >=0, 111111...xxx is < 0

° This representation called two’s complement

Page 8: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

8

Two’s Complement Number line

° 2 N-1 non-negatives

° 2 N-1 negatives

° one zero

° how many positives?

° comparison?

° overflow?

00000 0000100010

11111

11110

10000 0111110001

0 12

-1-2

-15-16 15

.

.

.

.

.

.

Page 9: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

9

Two’s Complement Numbers

0000 ... 0000 0000 0000 0000two =

0ten0000 ... 0000 0000 0000 0001two =

1ten0000 ... 0000 0000 0000 0010two =

2ten. . .0111 ... 1111 1111 1111 1101two =

2,147,483,645ten0111 ... 1111 1111 1111 1110two =

2,147,483,646ten0111 ... 1111 1111 1111 1111two =

2,147,483,647ten1000 ... 0000 0000 0000 0000two =

–2,147,483,648ten1000 ... 0000 0000 0000 0001two =

–2,147,483,647ten1000 ... 0000 0000 0000 0010two =

–2,147,483,646ten. . . 1111 ... 1111 1111 1111 1101two =

–3ten1111 ... 1111 1111 1111 1110two =

–2ten1111 ... 1111 1111 1111 1111two =

–1ten

° One zero, 1st bit => >=0 or <0, called sign bit • but one negative with no positive –2,147,483,648ten

Page 10: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

10

Two’s Complement Formula

° Can represent positive and negative numbers in terms of the bit value times a power of 2:

• d31 x -231 + d30 x 230 + ... + d2 x 22 + d1 x 21 + d0 x 20

° Example1111 1111 1111 1111 1111 1111 1111 1100two

= 1x-231 +1x230 +1x229+... +1x22+0x21+0x20

= -231 + 230 + 229 + ... + 22 + 0 + 0

= -2,147,483,648ten + 2,147,483,644ten

= -4ten

° Note: need to specify width: we use 32 bits

Page 11: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

11

Two’s complement shortcut: Negation

° Invert every 0 to 1 and every 1 to 0, then add 1 to the result

• Sum of number and its one’s complement must be 111...111two

• 111...111two= -1ten

• Let x’ mean the inverted representation of x

• Then x + x’ = -1 x + x’ + 1 = 0 x’ + 1 = -x

° Example: -4 to +4 to -4x : 1111 1111 1111 1111 1111 1111 1111 1100two

x’: 0000 0000 0000 0000 0000 0000 0000 0011two

+1: 0000 0000 0000 0000 0000 0000 0000 0100two

()’: 1111 1111 1111 1111 1111 1111 1111 1011two

+1: 1111 1111 1111 1111 1111 1111 1111 1100two

Page 12: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

12

Two’s comp. shortcut: Sign extension

° Convert 2’s complement number using n bits to more than n bits

° Simply replicate the most significant bit (sign bit) of smaller to fill new bits

•2’s comp. positive number has infinite 0s

•2’s comp. negative number has infinite 1s

•Bit representation hides leading bits; sign extension restores some of them

•16-bit -4ten to 32-bit:

1111 1111 1111 1100two

1111 1111 1111 1111 1111 1111 1111 1100two

Page 13: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

13

Distribusi Nilai UTS

1

7

32 31

20

16

6

3

0

5

10

15

20

25

30

35

10 20 30 40 50 60 70 80

Page 14: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

14

Addition of Positive Numbers

Page 15: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

15

One-Bit Full Adder (1/3)

° Example Binary Addition:

Carries

° Thus for any bit of addition:• The inputs are ai, bi, CarryIni

• The outputs are Sumi, CarryOuti

° Note: CarryIni+1 = CarryOuti

a: 0 0 1 1

b: 0 1 0 1

Sum: 1 0 0 0

Page 16: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

16

One-Bit Full Adder (2/3)

DefinitionA B CarryIn CarryOut Sum0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1

Sum = ABCin + ABCin + ABCin + ABCin

CarryOut = AB + ACin + BCin

¯ ¯ ¯ ¯ ¯ ¯

Page 17: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

17

One-Bit Full Adder (3/3)

° To create one-bit full adder:• implement gates for Sum

• implement gates for CarryOut

• connect all inputs with same name

SumA

B

CarryIn

CarryOut

+

Page 18: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

18

Ripple-Carry Adders: adding n-bits numbers

° Critical Path of n-bit Rippled-carry adder is n*CP• CP = 2 gate-delays (Cout = AB + ACin + BCin)

A0

B0

1-bitFA

Sum0

CarryIn0

CarryOut0

A1

B1

1-bitFA

Sum1

CarryIn1

CarryOut1

A2

B2

1-bitFA

Sum2

CarryIn2

CarryOut2

A3

B3

1-bitFA

Sum3

CarryIn3

CarryOut3

Page 19: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

19

Fast Adders

Page 20: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

20

Carry Look Ahead: reducing Carry Propagation delay

A

B

SGP

A

B

SGP

A

B

SGP

C1 = G0 + C0 P0 = A0B0 + C0(A0+B0)

C2 = G1 + G0 P1 + C0 P0 P1

C3 = G2 + G1 P2 + G0 P1 P2 + C0 P0 P1 P2

G = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0

C4 = . . .

P = P3·P2·P1·P0

A B C-out0 0 0 “kill”0 1 C-in “propagate”1 0 C-in “propagate”1 1 1 “generate”

A0

B0

S0GP

P = A + BG = A B

Cin

Page 21: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

21

Carry Look Ahead: Delays

° Expression for any carry:• Ci+1 = Gi + PiGi-1 + … + PiPi-1 … P0C0

° All carries can be obtained in 3 gate-delays:• 1 needed to developed all Pi and Gi

• 2 needed in the AND-OR circuit

° All sums can be obtained in 6 gate-delays:• 3 needed to obtain carries

• 1 needed to invert carry

• 2 needed in the AND-OR circuit of Sum’s circuit

° Independent of the number of bits (n)

° 4-bit Adder:• CLA: 6 gate-delays

• RC: (3*2 + 3) gate-delays

° 16-bit Adder:• CLA: 6 gate-delays

• RC: (15*2 + 3) gate-delays

Sum = ABCin + ABCin + ABCin + ABCin ¯ ¯ ¯ ¯ ¯ ¯

Page 22: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

22

Cascaded CLA: overcoming Fan-in constraint

CLA

4-bitAdder

4-bitAdder

4-bitAdder

C1 = G0 + C0 P0

C2 = G1 + G0 P1 + C0 P0 P1

C3 = G2 + G1 P2 + G0 P1 P2 + C0 P0 P1 P2

GP

G0P0

C4 = . . .

C0

Delay = 3 + 2 + 3 = 8

DelayRC = 15*2 + 3 = 33

Page 23: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

23

Signed Addition & Subtraction

Page 24: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

24

Addition & Subtraction Operations

° Addition:• Just add the two numbers

• Ignore the Carry-out from MSB

• Result will be correct, provided there’s no overflow

0 1 0 1 (+5)+0 0 1 0 (+2) 0 1 1 1 (+7)

0 1 0 1 (+5)+1 0 1 0 (-6) 1 1 1 1 (-1)

1 0 1 1 (-5)+1 1 1 0 (-2)11 0 0 1 (-7)

0 1 1 1 (+7)+1 1 0 1 (-3)10 1 0 0 (+4)

0 0 1 0 (+2) 0 0 1 00 1 0 0 (+4) +1 1 0 0 (-4)

1 1 1 0 (-2)

1 1 1 0 (-2) 1 1 1 01 0 1 1 (-5) +0 1 0 1 (+5)

10 0 1 1 (+3)

° Subtraction:• Form 2’s complement of the

subtrahend

• Add the two numbers as in Addition

Page 25: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

25

Overflow

° Examples: 7 + 3 = 10 but ...

° - 4 5 = - 9 but ...

2’s ComplementBinaryDecimal

0 0000

1 0001

2 0010

3 0011

0000

1111

1110

1101

Decimal

0

-1

-2

-3

4 0100

5 0101

6 0110

7 0111

1100

1011

1010

1001

-4

-5

-6

-7

1000-8

0 1 1 1

0 0 1 1+

1 0 1 0

1

1 1 0 0

1 0 1 1+

0 1 1 1

110

7

3

1

– 6

– 4

– 5

7

Page 26: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

26

Overflow Detection

° Overflow: the result is too large (or too small) to represent properly

• Example: - 8 < = 4-bit binary number <= 7

° When adding operands with different signs, overflow cannot occur!

° Overflow occurs when adding:• 2 positive numbers and the sum is negative

• 2 negative numbers and the sum is positive

° On your own: Prove you can detect overflow by:• Carry into MSB ° Carry out of MSB

0 1 1 1

0 0 1 1+

1 0 1 0

1

1 1 0 0

1 0 1 1+

0 1 1 1

110

7

3

1

– 6

–4

– 5

7

0

Page 27: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

27

Overflow Detection Logic

° Carry into MSB ° Carry out of MSB• For a N-bit Adder: Overflow = CarryIn[N - 1] XOR CarryOut[N - 1]

A0

B0

1-bitFA

Result0

CarryIn0

CarryOut0

A1

B1

1-bitFA

Result1

CarryIn1

CarryOut1

A2

B2

1-bitFA

Result2

CarryIn2

A3

B3

1-bitFA

Result3

CarryIn3

CarryOut3

Overflow

X Y X XOR Y

0 0 0

0 1 1

1 0 1

1 1 0

Page 28: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

28

Arithmetic & Branching Conditions

Page 29: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

29

Condition Codes

° CC Flags will be set/cleared by arithmetic operations:

• N (negative): 1 if result is negative (MSB = 1), otherwise 0

• C (carry): 1 if carry-out(borrow) is generated, otherwise 0

• V (overflow): 1 if overflow occurs, otherwise 0

• Z (zero): 1 if result is zero, otherwise 0

0 1 0 1 (+5)+1 0 1 0 (-6) 1 1 1 1 (-1)

0 1 1 1 (+7)+1 1 0 1 (-3)10 1 0 0 (+4)

0 1 0 1 (+5)+0 1 0 0 (+4) 1 0 0 1 (-7?)

0 0 1 1 (+3)+1 1 0 1 (-3)10 0 0 0 (0)

Page 30: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

30

Multiplication of Positive Numbers

Page 31: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

31

Unsigned Multiplication

° Paper and pencil example (unsigned):

Multiplicand 1101 (13)Multiplier 1011 (11)

1101 1101 0000

1101 Product 10001111 (143)

° m bits x n bits = m+n bit product

° Binary makes it easy:•0 => place 0 ( 0 x multiplicand)

•1 => place a copy ( 1 x multiplicand)

Page 32: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

32

Unsigned Combinational Multiplier

° Stage i accumulates A * 2 i if Bi == 1

B0

A0A1A2A3

A0A1A2A3

A0A1A2A3

A0A1A2A3

B1

B2

B3

P0P1P2P3P4P5P6P7

0 0 0 0

Page 33: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

33

How does it work?

° at each stage shift A left ( x 2)

° use next bit of B to determine whether to add in shifted multiplicand

° accumulate 2n bit partial product at each stage

B0

A0A1A2A3

A0A1A2A3

A0A1A2A3

A0A1A2A3

B1

B2

B3

P0P1P2P3P4P5P6P7

0 0 0 00 0 0

Page 34: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

34

Multiplier Circuit

Product (Multiplier)

Multiplicand

4-bit FA

Add/NoAdd

Control

4 bits

8 bits

Shift Right

MUX

0

4 bits

C

Multiplicand 1101

C Product Multiplier0 0000 1011

0 1101 1011 Add0 0110 1101 Shift

1 0011 1101 Add0 1001 1110 Shift

0 1001 1110 NoAdd0 0100 1111 Shift

1 0001 1111 Add0 1000 1111 Shift

Page 35: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

35

Signed-Operand & Multiplication

Page 36: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

36

Signed Multiplication

° Negative Multiplicand:

Multiplicand 10011 (-13)Multiplier 01011 (+11)

1111110011 111110011 00000000 1110011 000000

Product 1101110001 (-143)

° Negative Multiplier:•Form 2’s complement of both multiplier and multiplicand

•Proceed as above

Page 37: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

37

Motivation for Booth’s Algorithm° Works well for both Negative & Positive Multipliers

° Example 2 x 6 = 0010 x 0110: 0010

x 0110 + 0000 shift (0 in multiplier) + 0010 add (1 in multiplier) + 0100 add (1 in multiplier) + 0000 shift (0 in multiplier) 00001100

° FA with add or subtract gets same result in more than one way:6 = – 2 + 8 0110 = – 00010 + 01000 = 11110 + 01000

° For example

° 0010 x 0110 00000000 shift (0 in multiplier) 1111110 sub (first 1 in multpl.)

000000 shift (mid string of 1s) + 00010 add (prior step had last 1)

00001100

Page 38: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

38

Booth’s Algorithm

Current Bit Bit to the Right Explanation Example Op

1 0 Begins run of 1s 0001111000 sub

1 1 Middle of run of 1s 0001111000none

0 1 End of run of 1s 0001111000 add

0 0 Middle of run of 0s 0001111000none

Originally for Speed (when shift was faster than add)• Small number of additions needed when multiplier has a few large blocks of

1s

0 1 1 1 1 0beginning of runend of run

middle of run

Page 39: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

39

Booths Example (2 x 7)

1a. P = P - m 1110 + 11101110 0111 0 shift P (sign

ext)

1b. 0010 1111 0011 1 11 -> nop, shift

2. 0010 1111 1001 1 11 -> nop, shift

3. 0010 1111 1100 1 01 -> add

4a. 0010 + 0010

0001 1100 1 shift

4b. 0010 0000 1110 0 done

Operation Multiplicand Product next?

0. initial value 0010 0000 0111 0 10 -> sub

Page 40: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

40

Booths Example (2 x -3)

1a. P = P - m 1110 + 11101110 1101 0 shift P (sign

ext)

1b. 0010 1111 0110 1 01 -> add + 0010

2a. 0001 0110 1 shift P

2b. 0010 0000 1011 0 10 -> sub + 1110

3a. 0010 1110 1011 0 shift

3b. 0010 1111 0101 1 11 -> nop4a 1111 0101 1 shift

4b. 0010 1111 1010 1 done

Operation Multiplicand Product next?

0. initial value 0010 0000 1101 0 10 -> sub

Page 41: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

41

Fast Multiplication

(read yourself!)

Page 42: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

42

Integer Division

Page 43: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

43

Divide: Paper & Pencil

1001 Quotient

Divisor 1000 1001010 Dividend–1000 10 101 1010 –1000 10 Remainder (or Modulo result)

° See how big a number can be subtracted, creating quotient bit on each step

Binary => 1 * divisor or 0 * divisor

° Dividend = Quotient x Divisor + Remainder=> | Dividend | = | Quotient | + | Divisor |

Page 44: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

44

Division Circuit

Remainder (Quotient)

Divisor

33-bit FA Control

33 bits

65 bits

Shift Left

33 bits

Q Setting

Sign-bit Checking

Page 45: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

45

Remainder Quotient

Initially 00000 1000

Shift 00001 000_Sub(-11) 11101Set q0 11110Restore 00001 0000

Shift 00010 000_Sub(-11) 11101Set q0 11111Restore 00010 0000

Shift 00100 000_Sub(-11) 11101Set q0 00001

00001 0001

Shift 00010 001_Sub(-11) 11101 001_Set q0 11111Restore 00010 0010

Restoring Division Algorithm

0010 QuotientDivisor 11 1000 Dividend

11 10

Remainder

Page 46: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

46

Floating-point Numbers & Operations

Page 47: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

47

Review of Numbers

° Computers are made to deal with numbers

° What can we represent in N bits?• Unsigned integers:

0 to 2N - 1

• Signed Integers (Two’s Complement)

-2(N-1) to 2(N-1) - 1

Page 48: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

48

Other Numbers

° What about other numbers?• Very large numbers? (seconds/century)

3,155,760,00010 (3.1557610 x 109)

• Very small numbers? (atomic diameter)0.0000000110 (1.010 x 10-8)

• Rationals (repeating pattern)2/3 (0.666666666. . .)

• Irrationals21/2 (1.414213562373. . .)

• Transcendentalse (2.718...), (3.141...)

° All represented in scientific notation

Page 49: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

49

Scientific Notation Review

6.02 x 1023

radix (base)decimal point

mantissa exponent

° Normalized form: no leadings 0s (exactly one digit to left of decimal point)

° Alternatives to representing 1/1,000,000,000

• Normalized: 1.0 x 10-9

• Not normalized: 0.1 x 10-8,10.0 x 10-10

Page 50: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

50

Scientific Notation for Binary Numbers

1.0two x 2-1

radix (base)“binary point”

Mantissa exponent

° Computer arithmetic that supports it called floating point, because it represents numbers where binary point is not fixed, as it is for integers

• Declare such variable in C as float

Page 51: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

51

Floating Point Representation (1/2)° Normal format: +1.xxxxxxxxxxtwo*2yyyytwo

° Multiple of Word Size (32 bits)

031S Exponent30 23 22

Significand

1 bit 8 bits 23 bits

° S represents SignExponent represents y’sSignificand represents x’s

° Represent numbers as small as 2.0 x 10-38 to as large as 2.0 x 1038

Page 52: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

52

Floating Point Representation (2/2)

° What if result too large? (> 2.0x1038 )• Overflow!

• Overflow => Exponent larger than represented in 8-bit Exponent field

° What if result too small? (>0, < 2.0x10-38 )• Underflow!

• Underflow => Negative exponent larger than represented in 8-bit Exponent field

° How to reduce chances of overflow or underflow?

Page 53: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

53

Double Precision Fl. Pt. Representation

° Next Multiple of Word Size (64 bits)

° Double Precision (vs. Single Precision)• C variable declared as double

• Represent numbers almost as small as 2.0 x 10-308 to almost as large as 2.0 x 10308

• But primary advantage is greater accuracy due to larger significand

031S Exponent

30 20 19Significand

1 bit 11 bits 20 bitsSignificand (cont’d)

32 bits

Page 54: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

54

IEEE 754 Floating Point Standard (1/4)

° Single Precision, DP similar

° Sign bit: 1 means negative0 means positive

° Significand:• To pack more bits, leading 1 implicit for normalized numbers

• 1 + 23 bits single, 1 + 52 bits double

• always true: 0 < Significand < 1 (for normalized numbers)

° Note: 0 has no leading 1, so reserve exponent value 0 just for number 0

Page 55: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

55

IEEE 754 Floating Point Standard (2/4)

° Kahan wanted FP numbers to be used even if no FP hardware; e.g., sort records with FP numbers using integer compares

° Could break FP number into 3 parts: compare signs, then compare exponents, then compare significands

° Wanted it to be faster, single compare if possible, especially if positive numbers

° Then want order:• Highest order bit is sign ( negative < positive)

• Exponent next, so big exponent => bigger #

• Significand last: exponents same => bigger #

Page 56: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

56

IEEE 754 Floating Point Standard (3/4)

° Negative Exponent?• 2’s comp? 1.0 x 2-1 v. 1.0 x2+1 (1/2 v. 2)

0 1111 1111 000 0000 0000 0000 0000 00001/20 0000 0001 000 0000 0000 0000 0000 00002

• This notation using integer compare of 1/2 v. 2 makes 1/2 > 2!

° Instead, pick notation 0000 0001 is most negative, and 1111 1111 is most positive• 1.0 x 2-1 v. 1.0 x2+1 (1/2 v. 2)

1/2 0 0111 1110 000 0000 0000 0000 0000 0000

0 1000 0000 000 0000 0000 0000 0000 00002

Page 57: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

57

IEEE 754 Floating Point Standard (4/4)

° Called Biased Notation, where bias is number subtract to get real number• IEEE 754 uses bias of 127 for single prec.

• Subtract 127 from Exponent field to get actual value for exponent

• 1023 is bias for double precision

° Summary (single precision):

031S Exponent30 23 22

Significand

1 bit 8 bits 23 bits° (-1)S x (1 + Significand) x 2(Exponent-127)

• Double precision identical, except with exponent bias of 1023

Page 58: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

58

Special Numbers

° What have we defined so far? (Single Precision)

Exponent Significand Object

0 0 0

0 nonzero ???

1-254 anything +/- fl. pt. #

255 0 +/- infinity

255 nonzero NaN

Page 59: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

59

Infinity and NaNs

result of operation overflows, i.e., is larger than the largest number that can be represented

overflow is not the same as divide by zero (raises a different exception)

+/- infinity S 1 . . . 1 0 . . . 0

It may make sense to do further computations with infinity e.g., X/0 > Y may be a valid comparison

Not a number, but not infinity (e.q. sqrt(-4)) invalid operation exception (unless operation is = or =)

NaN S 1 . . . 1 non-zero

NaNs propagate: f(NaN) = NaN

HW decides what goes here

Page 60: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

60

FP Addition

° Much more difficult than with integers

° Can’t just add significands

° How do we do it?• De-normalize to match exponents

• Add significands to get resulting one

• Keep the same exponent

• Normalize (possibly changing exponent)

° Note: If signs differ, just perform a subtract instead.

Page 61: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

61

FP Subtraction

° Similar to addition

° How do we do it?• De-normalize to match exponents

• Subtract significands

• Keep the same exponent

• Normalize (possibly changing exponent)

Page 62: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

62

Extra Bits for rounding"Floating Point numbers are like piles of sand; every time you move one

you lose a little sand, but you pick up a little dirt."

How many extra bits?

IEEE: As if computed the result exactly and rounded.

Addition:

1.xxxxx 1.xxxxx 1.xxxxx

+ 1.xxxxx 0.001xxxxx 0.01xxxxx

1x.xxxxy 1.xxxxxyyy 1x.xxxxyyypost-normalization pre-normalization pre and post

° Guard Digits: digits to the right of the first p digits of significand to guard against loss of digits – can later be shifted left into first P places during normalization.

° Addition: carry-out shifted in

° Subtraction: borrow digit and guard

° Multiplication: carry and guard, Division requires guard

Page 63: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

63

Rounding Digits

normalized result, but some non-zero digits to the right of the significand --> the number should be rounded

E.g., B = 10, p = 3: 0 2 1.69

0 0 7.85

0 2 1.61

= 1.6900 * 10

= - .0785 * 10

= 1.6115 * 10

2-bias

2-bias

2-bias-

one round digit must be carried to the right of the guard digit so that after a normalizing left shift, the result can be rounded, according to the value of the round digit

IEEE Standard: four rounding modes: round to nearest (default)

round towards plus infinityround towards minus infinityround towards 0

round to nearest: round digit < B/2 then truncate > B/2 then round up (add 1 to ULP: unit in last place) = B/2 then round to nearest even digit

it can be shown that this strategy minimizes the mean error introduced by rounding

Page 64: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

64

Sticky Bit

Additional bit to the right of the round digit to better fine tune rounding

d0 . d1 d2 d3 . . . dp-1 0 0 0 0 . 0 0 X . . . X X X S X X S

+Sticky bit: set to 1 if any 1 bits fall off the end of the round digit

d0 . d1 d2 d3 . . . dp-1 0 0 0 0 . 0 0 X . . . X X X 0

X X 0-

d0 . d1 d2 d3 . . . dp-1 0 0 0 0 . 0 0 X . . . X X X 1-

generates a borrow

Rounding Summary:

Radix 2 minimizes wobble in precision

Normal operations in +,-,*,/ require one carry/borrow bit + one guard digit

One round digit needed for correct rounding

Sticky bit needed when round digit is B/2 for max accuracy

Rounding to nearest has mean error = 0 if uniform distribution of digits are assumed

Page 65: IKI10230 Pengantar Organisasi Komputer Bab 6: Aritmatika

65

Denormalized Numbers

0 2 2 2-bias 1-bias 2-bias

B = 2, p = 4normal numbers with hidden bit -->

denormgap

The gap between 0 and the next representable number is much larger than the gaps between nearby representable numbers.

IEEE standard uses denormalized numbers to fill in the gap, making the distances between numbers near 0 more alike.

0 2 2 2-bias 1-bias 2-bias

p bits ofprecision

p-1bits of

precision

same spacing, half as many values!

NOTE: PDP-11, VAX cannot represent subnormal numbers. These machines underflow to zero instead.