Guy Barmoha

-Assignment 1: Convert the following numbers into base 2, 3, and 5

To convert the following fractions into the bases we use the method described in the lecture. When we discussed converting numbers into bases the question arises:

How do we represent a fractional part (less than 1) of a number?

We first experimented with numbers written in Base 10. For example,

2364.67843…

We see that the integer part is: 2364, and the fractional part is: 0.67843…

To see how to find the representation of this number we will multiply the number by the base and then take away the integer part of that as our first digit after the decimal point, and then repeat the process with the remaining fractional part, for instance:

0.67843… x 10 à 6 remainder 0.7843…

0.7843… x 10 à 7 remainder 0.843…

0.843… x 10 à 8 remainder 0.43…

Etc….

If we look at the integer part of each multiplication we see the digits after the decimal point. A question one may have is:

Why do we multiply by the base?

Multiplying by the base accomplishes one thing that is important to our procedure; it moves the decimal point over one space to the right. So if we have a number written in Base 5, let’s say 43.021base 5, and we multiply that by 5 we should get 430.21base 5. So, in order to convert a number to a base we will use this method, if the method works with numbers written in positional notation then it should work with numbers written in fractional notation.

I will show an example of each base, converting 1/6, and then show the rest of the solutions in a table:

Base 2

integer part remainder
0
0
1 / Since the fraction repeats itself in the remainder we have a periodic positional name for.

Base 3

integer part remainder
0
1 / Since the fraction repeats itself in the remainder we have a periodic positional name for.

Base 5

integer part remainder
0
4 / Since the fraction repeats itself in the remainder we have a periodic positional name for.


Here are the completed tables for each base.

Base 10 / Base 2 / Base 3 / Base 5

-Assignment 2: Implement the Saw-Tooth function in a SS and explore various values of x

In order to make the spreadsheet for the Saw-Tooth function we need to use a conditional statement. We will enter the following equation into a cell.

=IF (B1 0.5, 2*B1, 2*B1-1)

*note: B1 is the previous cell

Now to translate the above function into Base 2 we need to look at the output of the function. If the output is less than ½ then we assign a zero, and if the output is greater or equal to ½ then we assign a one. That list of zeros and ones will make up the positional name in Base 2 of the original input (that was in Base 10).

For example,

Here the initial value is once that is put into our iterative function we can see that. We also notice that this number is eventually periodic, (even though the only digit that repeats is zero.)

Or another example,

Here the initial value is once that is put into our iterative function we can see that. We also notice that this number is immediately periodic, (I think that is the correct description.)


After experimenting with some of values of x with the Saw-Tooth function we can notice that it appears that every number is eventually periodic with 0’s. However, we know this is not the case, if we look at as our value for x, input 0.2 into the initial value and we end up with:

As we look at the iteration that Excel is doing we can see that it seems to be repeating 0.0011001100110011…, however towards the bottom of the spreadsheet we can see that only 0’s repeat. Is this because the number 0.2 is a ‘terminating’ decimal when written in Base 2? No, not at all, what it means is that the Excel program has run out of memory to handle the many digits that is necessary to do this calculation correctly. We know from our answer to question 1 that

So we need to be especially careful when using a spreadsheet program to help us convert bases.


-Assignment 3: Find a Saw-Tooth function for the conversion into base 3.

The Saw-Tooth function is a piece-wise function that uses graphical iteration to convert fractional parts of numbers into different bases.

The Base 2 conversion of the Saw-Tooth function is below. Notice how we keep the square a 1x1 square because we are looking for the fractional part of a number is Base 2. So we need two sections because we have two digits in Base 2. We can clearly see that the equation of the first blue segment is y = 2x and the second equation is y = 2x – 1.

Base 2 conversion

The Base 3 conversion of the Saw-Tooth function is below. Notice how we still keep the square a 1x1 square; however, we broke the square into three parts because there are three digits to use in Base 3. We can use some basic Algebra skills to find the equations of each part of the function.

Base 3 conversions

-Assignment 4: Given x = 1/2, find values for y, so that |x-y| < 1/64, <1/128, <1/256, <1/512, <1/1024 and |fk(x) - fk(y)| > 1/2, for some k.

We will attack this problem in steps. We will first look at the inequality:

Since we are given the value of x we can plug that in and find the values of y that satisfy the inequality.

In a similar fashion we can find the values of y that satisfy all the inequalities.

/ Values of y

Now we can try to attack the second part of the problem, and we have to look at the following inequality:

|fk(x) - fk(y)| > 1/2

Again we are given the value of x and by observing what happens to the value ½ in the Chaos Lab we notice that after one iteration it goes to zero. So now we have three cases to consider with each problem. We will look at the first problem, whose solution is. We want to know for how many iterations of the Saw-Tooth function will the difference of the values of x and y is more than ½. Since there are many different values for y we will look at them in cases. Case 1 will be when y < ½, Case 2 will be when

y = ½, and Case 3 will be when y > ½. While playing with the Chaos Lab and entering two values x = ½ and y being a little less than ½ we can see how many iterations it would take for the distance between the corresponding values to be more than ½.

Here is a table of results from the Chaos Lab experimentation.

/ k = 1
/ k = “never”
/ k = 6

The first two cases should be the same for every value of y, however, with the third case it depends on how far away you started from ½. In Case 1, we know that = 0 since x=½, and the closer we start y at ½ the quicker we go to 1. So for all the Case 1’s we should have a k = 1. In Case 2, we know that = 0 since x=½, and since y = ½ we know that = 0. So we will never be more than ½ away. So for all Case 2’s we should have a k = “never”. Now the question arises what happens for Case 3. This is when we will not have the same answer for each question. The following table shows how many iterations it will take for each problem.

, (given x=1/2) /

Here we notice that the value of k is always the denominators power of 2. In general:

, (given x=1/2) /


-Assignment 5: Find a number x (in binary form) so that when iterating the Saw-Tooth function f, the iterations fk(x) will visit all the intervals:

[0,1/16 ], [1/16,2/16], [2/16,3/16], [3/16,4/16], [4/16,5/16], [5/16,6/16], [6/16,7/16], [7/16,8/16], [8/16,9/16], [9/16,10/16], [10/16,11/16], [11/16,12/16], [12/16,13/16], [13/16,14/16], [14/16,15/16], [15/16,16/16].

At first when I was thinking about this problem I knew that the function had to iterate at least 16 times in order to at least hit all 16 intervals. From problem 4 I knew in order to be sure to have at least 16 iterations we have to have a number (in binary form) that has at least 16 decimal places. For example, 0.00000000000000001, however when entering this into the Chaos Lab it did iterate 16 times however all values were less than ½. So that solution was not correct. After reading the forum I noticed an idea from Ana, that allowed me to experiment on my own and with the help of Ana’s post was able to find an array of numbers that should work.

Here is the entry from the forum:

Let's say we want a number that hits the intervals (0, 1/2), (1/2, 1) then the number in binary would be .01. Does that sound right?
Since he wants the subdivisions in 16ths or 2^(-4) (order 4 in the Chaos Lab?). Is he asking to find a number that hits all those intervals? Every interval, in binary, would be represented by 4 digits from 0000 to 1111. Could the number be:


.0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Using the same reasoning I wanted to see if this idea would also work if we broke up the intervals into fourths. So the intervals we are looking at are:

[0, 1/4], [1/4, 2/4], [2/4, 3/4], [3/4, 4/4]

Since we are using fourths and it takes two decimal places to write ¼ in binary we will use every combination of two decimal place numbers in binary and concatenate those numbers. For example:

0.00 01 10 11


This number seems to work in the Chaos Lab. However, is there a certain order that the 2-digit binary numbers have to be in? So, let’s try:

0.10 11 00 01

This number also seemed to work in the Chaos Lab; however, it hit the intervals in a different order. Therefore, if are using 16 intervals and it takes four decimal places to write 1/16 in binary we have to find all the 4-digit numbers that can be written in binary and concatenate them. For example,

0.0000 0001 0010 0100 1000 0011 0110 1100 1010 0101 1001 1110 0111 1101 1011 1111

This should be a number that hits all 16 intervals. The question I am struggling with is…Why does it work? It seems like each “4-digit” value in the number above stands for one of the intervals.


-Assignment 6: Use the Chaos Lab Applet: For x = 0.1 choose y = 0.11,

y = 0.101, y = 0.1001, y = 0.1001, y = 0.10001, y = 0.100001. Now iterate x and y and find for which iterate the distance |fk(x) - fk(y)| is greater than ½.

x = 0.1 |fk(x) - fk(y)| > ½

y = 0.11 / y = 0.101 / y = 0.1001 / y = 0.10001 / y = 0.100001
k = 7 / k = 9 / k = 11 / k = 15 / k = 23

The numbers supplied to us seemed to be in Base 2 since they are only using 0’s and 1’s. However if the numbers are converted from Base 2 to Base 10 then the iterations all go to zero after a while and don’t become more than ½ away. So, the only conclusion is that the numbers are already written in Base 10. Looking for a pattern in the number of iterations, k, it does not seem to have a pattern that can be predicted. Looking at the next value of y that would be in the progression, y = 0.1000001, we get k = 27. Even with another data point it doesn’t help us find a pattern in the number of iterations.


-Assignment 7: Create a GeoGebra construction for the Saw-Tooth function with movable initial value x0.

Here is a screen shot of my GeoGebra construction. The file can be found on my Tiki user page.