CS 2401 Assignment #4

Due Date: Monday, February 22, 2010, or Tuesday, February 23, 2010, depending on the day of your lab.

Objective: The goal of this assignment is to practice recursion.

Problem to solve: Converting a positive real number to binary code with a given number of binary digits after the (binary) point. The binary code should be presented as a string of 0s and 1s, separated by the point.

Example: if we want to convert the decimal number 13.12510 with four binary digits after the point, we should get a string 1101.0010.

Method: Part 1. To covert a real number, we first extract its integer part (e.g., by using Java's floor method) and its fractional part -- e.g., by subtracting the integer part from the number itself.

Example: when we apply floor to the number 13.125, we get the integer part 13. By subtracting this integer part 13 from the original number, we then get the fractional part 0.125.

Method: Part 2. After we separate the integer and the fractional parts of the given number, we separately convert the integer part and the fractional part into binary.

The conversion of an integer part is described, in detail, in the Recursion chapter of our textbook. The corresponding algorithm is as follows:

Example: To convert n = 13, we first use the same method to convert 13 / 2 = 6 into binary, resulting in 110, and then append 13 % 2 = 1 to this string, resulting in the binary code 1101.

To convert n = 6, the method first converts 6 / 2 = 3 into binary, resulting in 11, and then appends 6 % 2 = 0 to this string, resulting in the binary code 110.

To convert n = 3, the method first converts 3 / 2 = 1 into binary, resulting in 1, and then appends 3 % 2 = 1 to this string, resulting in the binary code 11.

Finally, when asked to convert n = 1 into binary, the method simply returns the string consisting of a single binary digit 1.

Method: Part 3. For converting a fractional part, we can use a similar algorithm but with multiplication by two instead of division by two:

Motivation: For a fractional binary number like x = 0.11012, multiplication by 2 means simply a shift (just like for decimal numbers, multiplication by 10 is simply a shift), resulting in 2 * x = 1.1012. The integer part of this number (1) is thus indeed the first digit (1) of the binary expansion, and the remaining three digits 101 are the binary expansion of the fractional part 0.1012 of the value 2 * x.

Example: To convert x = 0.125 into d = 4 binary digits, we compute 2 * x = 0.25. The integer part 0 of this fraction is the first digit of the desired binary expansion, and the other d - 1 = 3 binary digits are obtained by converting the fractional part 0.25 into 3 binary digits. This conversion results in 010, so adding 0 as the first digit we get 0010.

To convert x = 0.25 into d = 3 binary digits, we compute 2 * x = 0.5. The integer part 0 of this fraction is the first digit of the desired binary expansion, and the other d - 1 = 2 binary digits are obtained by converting the fractional part 0.5 into 2 binary digits. This conversion results in 10, so adding 0 as the first digit we get 010.

To convert x = 0.5 into d = 2 binary digits, we compute 2 * x = 1.0. The integer part 1 of this fraction is the first digit of the desired binary expansion, and the other d - 1 = 1 binary digits are obtained by converting the fractional part 0.0 into 1 binary digit. This conversion results in 0, so adding 1 as the first digit we get 10.

To convert x = 0.0 into d = 1 binary digits, we compute 2 * x = 0.0. The integer part 0 of this fraction is the first digit of the desired binary expansion, and the other d - 1 = 0 binary digits are obtained by converting the fractional part 0.0 into 0 binary digits. This conversion results in an empty string (this is the base case of our recursion), so adding 0 as the first digit we get 0.

Assignment: Write a program that implements the above recursion-using algorithm to convert a real number into binary code with a given number of binary digits after the binary point.