Computer Organization and Design
(Textbook. Click for information.)
 CS 2733/2731
 Computer Organization II
 Fall 2004
 Recitation 14
 Floating Point
    Week 14: Nov 22-24
 Due (on time): 2004-12-01  23:59:59
 Due (late):        2004-12-05  23:59:59

Recitation 14 must be submitted following directions at: submissions on or before
  • 2004-12-01  23:59:59 (that's Wednesday, 1 December 2004, 11:59:59 pm) for full credit.
  • 2004-12-05  23:59:59 (that's Sunday, 5 December 2004, 11:59:59 pm) for 75% credit.

Outline: This recitation has two parts:

  1. For the first part, you are to experiment with the bit pattern used to represent a double by computers that adhere to the IEEE standard for doubles. (See text, Section 3.6. Most hardware now follows the standard, although some floating point units implement a permitted extension.

  2. The second part asks you to write a simple program using MIPS instructions for doubles. (See text, sections 3.6 and A.10.)

Details about part 1: Given either an "ordinary" floating point number or a bit pattern, it is easy to get the other representation, say, with programs like the following in C and in Java. The Java program uses another class to read a double: GetData.java. Both the C and the Java use the Unix command line below, rather than a development environment, but of course you may use JBuilder or some other development tool if you wish. The runs shown below are on Sun hardware. Beware: On certain other hardware (e.g., Intel), the two halves that make up the bits of a double come out in reverse order.

C Program Java Program

/* double_rep.c: hex for doubles */
#include <stdio.h>
#include <ctype.h>
void print_bits(unsigned int r) {
   int i;
   for (i = 0; i < 32; i++) {
      printf("%1i", ( (r >> 31) ? 1 : 0));
      r = r << 1;
   }
}

int main() {
   union {
      double d;
      struct {
         unsigned int p;
         unsigned int q;
      } b;
   } r;
   char ch;
   for( ; ; ) {
      while (isspace(ch = getchar()))
         ;
      if (ch == 'x')
         scanf("%x %x", &r.b.p, &r.b.q);
      else if (ch == 'f')
         scanf("%lf", &r.d);
      else break;

      printf(" Dec: %20.16e\n", r.d);
      printf(" Hex: %08x %08x\n",
            r.b.p, r.b.q);
      printf(" Bin: ");
      print_bits(r.b.p); printf("\n      ");
      print_bits(r.b.q); printf("\n");
   }
}


// DoubleRep.java: bin and hex
public class DoubleRep {

   // main function to try out Base class
   public static void main (String[] args) {
      GetData  getData = new GetData();
      double d;
      long drep;
      while (true) {
         d = getData.getNextDouble();
         if (d == 0.0) break;
         drep = Double.doubleToLongBits(d);
         String s = Long.toBinaryString(drep);
         while (s.length() < 64) s = "0" + s;
         String t = Long.toHexString(drep);
         while (t.length() < 16) t = "0" + t;
         System.out.print(" Bin: ");
         for (int i = 0; i < 64; i++) {
            if (i == 31)
               System.out.print("\n      ");
            System.out.print(s.charAt(i));
         }
         System.out.println();
         System.out.println(" Hex: " + t);
      }
   } // end of main
}
C Run and Output Java Run and Output
% cc -o double_rep double_rep.c
% double_rep
f -0.75
 Dec: -7.5000000000000000e-01
 Hex: bfe80000 00000000
 Bin: 10111111111010000000000000000000
      00000000000000000000000000000000
f 16.0
 Dec: 1.6000000000000000e+01
 Hex: 40300000 00000000
 Bin: 01000000001100000000000000000000
      00000000000000000000000000000000
f 1.5
 Dec: 1.5000000000000000e+00
 Hex: 3ff80000 00000000
 Bin: 00111111111110000000000000000000
      00000000000000000000000000000000
x 3fe80000 00000000
 Dec: 7.5000000000000000e-01
 Hex: 3fe80000 00000000
 Bin: 00111111111010000000000000000000
      00000000000000000000000000000000
q
%

% javac GetData.java
% javac DoubleRep.java
% java DoubleRep
-.75
 Bin: 10111111111010000000000000000000
      00000000000000000000000000000000
 Hex: bfe8000000000000
16.0
 Bin: 01000000001100000000000000000000
      00000000000000000000000000000000
 Hex: 4030000000000000
.75
 Bin: 00111111111010000000000000000000
      00000000000000000000000000000000
 Hex: 3fe8000000000000
1.5
 Bin: 00111111111110000000000000000000
      00000000000000000000000000000000
 Hex: 3ff8000000000000
15.0
 Bin: 01000000001011100000000000000000
      00000000000000000000000000000000
 Hex: 402e000000000000
0
%

An Elaborate C double Representation Program: This is a more interesting program that tears an input double apart and assembles the individual pieces as in the book:

Details about part 2: Here are three sample assembler programs that work with floating point numbers (the floating point instructions are in red):

The first is a simple calculation of 355.0/113.0 as a double. These numbers take up 8 bytes, and are stored in special floating point registers: $f0 through $f31, but doubles are only stored in an even numbered floating point register, along with the following odd-numbered register. With $v0 = 3, syscall will print the double value in $f12 (and $f13). Many MIPS instructions have an analog for doubles with .d tacked onto the end.

MIPS, PI = (approx) 355/113 spim output
# calculate  pi = 355.0/113.0
        .globl main
main:   addu     $s7, $zero, $ra
        la       $a0, Nums
        l.d      $f2, 0($a0)  $ load double
        l.d      $f4, 8($a0)  $ load double
        div.d    $f6, $f2, $f4  $ divide double
        li       $v0, 3
        mov.d    $f12, $f6  $ move double
        syscall
        addu     $ra, $zero, $s7
        jr       $ra
       .data
       .align  3
Nums:  .double 355., 113.

$ spim -file pi.s
3.14159292035398252

The next program below uses an approximation algorithm to calculate pi, but the looping is just an integer loop like the ones you are used to. Notice that MIPS has a sqrt.d hardware instruction to take the square root.

MIPS: Pi approximation C equivalent and spim output
        .globl main
main:   addu       $s7, $zero, $ra

        la         $a0, Nums
        l.d        $f2, 0($a0)   # p = 2.0
        l.d        $f4, 8($a0)   # b = 0.0
        mov.d      $f6, $f2      # 2.0
        li         $t0, 0
        li         $t1, 26

Loop:   add.d      $f8, $f4, $f6  # $f8 = 2+b
        sqrt.d     $f4, $f8   # b = sqrt($f8)
        div.d      $f10, $f6, $f4 # t = 2/b
        mul.d      $f2, $f2, $f10
        addi       $t0, $t0, 1

        li         $v0, 3
        mov.d      $f12, $f2
        syscall                # print p

        li         $v0, 4
        la         $a0, Newl
        syscall                # print Newl

        bne        $t0, $t1, Loop

        li         $v0, 3
        mov.d      $f12, $f2
        syscall                # print p
        
        li         $v0, 4
        la         $a0, Newl
        syscall                # print Newl

        addu       $ra, $zero, $s7
        jr         $ra

       .data
       .align  3
Nums:  .double 2., 0.
Newl:  .asciiz  "\n"

$ cat pi2.c
#include <stdio.h>
#include <math.h>
int main() {
   double p = 2; /* final product */
   double b = 0; /* each denom */
   double t;  /* term */
   int i;
   for (i = 0; i < 24; i++) {
      b = sqrt(2 + b);
      t = 2.0/b;
      p = p*t;
      printf("%20.15f\n", p);
   }
   printf("%20.15f\n", p);
}
$ spim -file pi2.s
SPIM Version 7.0 of July 7, 2004
2.82842712474618985
3.06146745892071825
3.12144515225805241
3.13654849054593932
3.14033115695475296
3.14127725093277288
3.1415138011443009
3.14157294036709178
3.14158772527716001
3.14159142151120019
3.14159234557011802
3.1415925765848729
3.14159263433856362
3.14159264877698652
3.14159265238659202
3.14159265328899373
3.14159265351459416
3.14159265357099438
3.14159265358509465
3.14159265358861939
3.14159265358950046
3.14159265358972073
3.1415926535897758
3.14159265358978956
3.14159265358979312
3.141592653589794
3.141592653589794

The third program below creates a loop that depends on the results of the floating point calculations. These use MIPS floating point Condition Codes. There are 8 binary Condition Codes, but we are only using Condition Code number 0 here (the default). I couldn't find out how to use the other numbers.

The instruction

sets the Condition Code 0 to true (1) in case the first argument is less than the second, and sets it to false (0) otherwise. The instruction

branches to Loop in case the default condition code 0 was set to false, and doesn't branch otherwise. Automatically setting a condition code whose value can be used by a later instruction is more like a real assembly language, although in MIPS it seems to be in a rudimentary form.

MIPS: simple branch example C equivalent and spim output
main:   addu       $s7, $zero, $ra

        la         $a0, Nums
        l.d        $f2, 0($a0)   # n = 2.0
        l.d        $f4, 8($a0)   # d = 37.0
        l.d        $f6, 16($a0)  # e = 1.0e-15

Loop:   div.d      $f2, $f2, $f4 # n = n/37

        li         $v0, 3
        mov.d      $f12, $f2
        syscall              # print n
        li         $v0, 4
        la         $a0, Newl
        syscall

        c.lt.d     $f2, $f6  # is n < e ?
        bc1f       Loop   # branch back if not

        li         $v0, 3
        mov.d      $f12, $f2
        syscall              # print n
        li         $v0, 4
        la         $a0, Newl
        syscall

        addu       $s7, $zero, $ra
        jr         $ra

       .data
       .align  3
Nums:  .double 2., 37., 1.0e-15
       .align 2
Newl:  .asciiz  "\n"

$ cat branch.c
#include <stdio.h>
#include <math.h>
int main() {
   double n = 2.0;
   double d = 37.0;
   double e = 1.0e-15;
   while (1) {
      n = n/d;
      printf("%20.15e\n", n);
      if (n < e) break;
   }
   printf("  %20.15e\n", n);
}
$ spim -file branch.s
0.0540540540540540571
0.00146092037983929879
3.94843345902513217e-05
1.06714417811490052e-06
2.88417345436459609e-08
7.79506339017458388e-10
2.10677388923637414e-11
5.69398348442263239e-13
1.5389144552493601e-14
4.15922825743070287e-16
4.15922825743070287e-16

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate number 1-5.

  Contents of submission for Recitation 14:

Last Name, First Name; Course Number; Recitation Number (14).

  1. Download and run one of the first two programs above, either of which shows the bits that represent a double. Try out the inputs shown above.

  2. Try the following inputs, then print the resulting bits in each case and observe the pattern:

    1.    0.125  
    2.    0.25  
    3.    0.5  
    4.    1.0  
    5.    2.0  
    6.    4.0  
    7.    8.0  
    8.   16.0  
    9.   32.0  

  3. Similarly, try:

    1.    0.1875  
    2.    0.375  
    3.    0.75  
    4.    1.5  
    5.    3.0  
    6.    6.0  
    7.   12.0  
    8.   24.0  

  4. Next, try the following inputs:

    1.    1.0              = 1
    2.    1.5              = 1 - 1/2
    3.    1.75             = 1 - 1/4
    4.    1.875            = 1 - 1/8
    5.    1.9375           = 1 - 1/16
    6.    1.96875          = 1 - 1/32
    7.    1.984375         = 1 - 1/64
    8.    1.99999999999999     (14 9's)
    9.    1.999999999999999    (15 9's)
    10.    1.9999999999999999   (16 9's)

  5. Convert the following C program into MIPS assembler language. This program calculates the square root of n from scratch, and compares the answer with the build-in square root. Be sure to run the MIPS program and get the output from spim.

    If you have difficulties with the first program, then do the second instead (for less credit). It is simpler because it just uses a normal MIPS integer loop, and this simpler program just repeats a fixed number of times, rather than repeating until it converges.

      C Program Output
      $ cat sqrtn.c
#include <stdio.h>
#include <math.h>
int main() {
   double n = 10;
   double x0 = n;
   double x1;
   int i;
   while (1) {
      x1 = x0/2 + n/(2*x0);
      printf("%20.15f\n", x1);
      if (x0 - x1 < 1.0e-14) break;
      x0 = x1;
   }
   printf("%20.15f\n", x1);
   printf("  %20.15f\n", sqrt(n));
}

      $ cc -o sqrtn -lm sqrtn.c
$ sqrtn
   5.500000000000000
   3.659090909090909
   3.196005081874647
   3.162455622803890
   3.162277665175675
   3.162277660168380
   3.162277660168380
   3.162277660168380
   3.162277660168380
     3.162277660168380

      C Program (simpler version) Output
      $ cat sqrtn.c
#include <stdio.h>
#include <math.h>
int main() {
   double n = 10000;
   double x0 = n;
   double x1;
   int i;
   for (i = 0; i < 8; i++) {
      x1 = x0/2 + n/(2*x0);
      printf("%20.15f\n", x1);
      x0 = x1;
   }
   printf("%20.15f\n", x1);
   printf("  %20.15f\n", sqrt(n));
}

      $ cc -o sqrtn -lm sqrtn.c
$ sqrtn
5000.500000000000000
2501.249900009998782
1252.623950584661543
 630.303596239436501
 323.084483304812181
 177.018069983297437
 116.754738949847876
 101.202183653539464
 100.007140387117460
 100.000000254907434
 100.000000000000000
 100.000000000000000
 100.000000000000000
   100.000000000000000

Revision date: 2004-11-20. (Please use ISO 8601, the International Standard.)