This was a self-challenge I created in CSC165 to understand better how to calculate the value of the input in a machine. The way these notes were formatted helped me to understand better the way in which to find the big-Oh of a function.
######################################################
Machine 1:
How can we find z assuming x > 1?
For this, we will use x-y-z charts.
2:
2:
|
x
|
y
|
z
|
|
2
|
1+1
|
+1
|
|
2-1
|
2
|
+1
|
|
1
|
2
|
2
|
3:
|
x
|
y
|
z
|
|
3
|
1+1
|
+1
|
|
3-1
|
2
|
+1
|
|
2
|
2
|
2
|
4:
|
x
|
y
|
z
|
|
4
|
1+1
|
+1
|
|
4-1
|
2
|
+1
|
|
3
|
2
|
+0
|
|
3
|
2+1
|
+1
|
|
3
|
3
|
3
|
5:
|
x
|
y
|
z
|
|
5
|
1+1
|
+1
|
|
5-1
|
2
|
+1
|
|
4
|
2
|
+0
|
|
4
|
2+1
|
+1
|
|
4-1
|
3
|
+1
|
|
3
|
3
|
4
|
We can simplify this for the next few numbers by pointing out when z increases for each condition (x > y, x > z) and compare it to the previous results:
2: 1, 1 = 2
3: 1, 1 = 2
4: 1, 1, 0, 1 = 3
5: 1, 1, 0, 1, 1 = 4
6: 1, 1, 0, 1, 1, 0, 1 = 5
7: 1, 1, 0, 1, 1, 0, 1, 0, 1 = 6
8: 1, 1, 0, 1, 1, 0, 1, 1, 1 = 7
It can be gathered that z = x – 1 except at x = 2 when z = x. This means that at some point a condition that isn’t met before does get met or a new condition is met, adding to the chain.
Machine 2:
How can we find a assuming x > -1?
We know that machine_2(-1) returns 0. What does
machine_2(0) return?
x = x + 2 so x = 2
Since y = 1 and x > y, a goes up by 1 and so does y.
Since z = 2 and y == z, a goes up by 1 and z goes up by 2.
x > y is not in effect anymore, therefore machine_2(0) returns 2 (which is what a is).
Now what happens when machine_2(1) is executed? The same as machine_2(0) but we can add 1 to a since x = 3 and x still is greater than y when y = 2 making the function return 3. How about machine_2(2)? Again the same as before apply but x now equals 4 meaning that y has to increase by 1 in order to break the loop (which makes a increase by 1). By doing so, y = 4 and z = 4 making the y == z statement true and allowing a to go up by 1 again, meaning the function returns 5.
x = x + 2 so x = 2
Since y = 1 and x > y, a goes up by 1 and so does y.
Since z = 2 and y == z, a goes up by 1 and z goes up by 2.
x > y is not in effect anymore, therefore machine_2(0) returns 2 (which is what a is).
Now what happens when machine_2(1) is executed? The same as machine_2(0) but we can add 1 to a since x = 3 and x still is greater than y when y = 2 making the function return 3. How about machine_2(2)? Again the same as before apply but x now equals 4 meaning that y has to increase by 1 in order to break the loop (which makes a increase by 1). By doing so, y = 4 and z = 4 making the y == z statement true and allowing a to go up by 1 again, meaning the function returns 5.
The table illustrates this pattern:
|
x
|
m_2(x)
|
|
0
|
2
|
|
1
|
3
|
|
2
|
5
|
|
3
|
6
|
|
4
|
8
|
|
5
|
9
|
|
6
|
11
|
When x goes from odd to even, 2 is added. When x goes from even to odd, 1 is added. So machine_2(x) creates this pattern:
2 + 1 + 2 + 1 + 2 + 1 + 2 . . .
(based on 2, 3, 5, 6, 8, 9, 11 . . . )
To put it another way:
0 / 1 turns to 2 / 3 # by adding 2
2 / 3 turns to 5 / 6 # by adding 3
4 / 5 turns to 8 / 9 # by adding 4
6 / 7 turns to 11 / 12 # by adding 5
etc.
Another interesting element is that the even and odd
sets all differ by 3.
We can re-write the results of machine_2 like so:
-1: 0 + 0 // 0 + 2(0)
0 : 0 + 2 // 0 + 2(1)
1 : 1 + 2 // 1 + 2(1)
2 : 1 + 4 // 1 + 2(2)
3 : 2 + 4 // 2 + 2(2)
4 : 2 + 6 // 2 + 2(3)
5 : 3 + 6 // 3 + 2(3)
6 : 3 + 8 // 3 + 2(4)
7 : 4 + 8 // 4 + 2(4)
We can split this through conditions:
if x % 2 == 0 then a = x/2 + 2 * ceiling((x + 1)/2)
if x % 2 == 1 then a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
So we can combine the two to get:
a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
-1: 0 + 0 // 0 + 2(0)
0 : 0 + 2 // 0 + 2(1)
1 : 1 + 2 // 1 + 2(1)
2 : 1 + 4 // 1 + 2(2)
3 : 2 + 4 // 2 + 2(2)
4 : 2 + 6 // 2 + 2(3)
5 : 3 + 6 // 3 + 2(3)
6 : 3 + 8 // 3 + 2(4)
7 : 4 + 8 // 4 + 2(4)
We can split this through conditions:
if x % 2 == 0 then a = x/2 + 2 * ceiling((x + 1)/2)
if x % 2 == 1 then a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
So we can combine the two to get:
a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
Machine 3:
How can we find b assuming x > 3?
The while x > a loop indicates how many steps it
takes for a to equal x using the a + 1 approach, making b = (x - a).
Since a = 3, b = (x - 3).
Now xα = x + 2.
The while xα > z loop indicates how long it takes for xα == z (provided xα % 2 == 0) or xα < z (xα % 2 == 1) following the xα – 1 // z + 1 approach:
Since a = 3, b = (x - 3).
Now xα = x + 2.
The while xα > z loop indicates how long it takes for xα == z (provided xα % 2 == 0) or xα < z (xα % 2 == 1) following the xα – 1 // z + 1 approach:
|
X
|
z
|
B
|
|
xα
(x + 2)
|
2 (z)
|
+ 0
|
|
xα
- 1 (x + 2 - 1)
|
2 + 1 (z +
1)
|
+ 1
|
|
xα
- 2 (x + 2 - 1)
|
2 + 2 (z +
2)
|
+ 2
|
|
-
|
-
|
-
|
|
xα-final
(x + 2 – n)
|
zfinal
(z + n or 2 + n) |
+ n
|
By manipulating inequalities:
x + 2 - n ≤ 2 + n
x + 2 ≤ 2 + 2n
x + 2 ≤ 2(1 + n)
((x + 2) / 2) ≤ 1 + n
(((x + 2) / 2) – 1) ≤ n
So we have:
b = (x - 3) + (((x + 2) / 2) - 1) # if x % 2 == 0
b = (x - 3) + ceiling(((x + 2) / 2) - 1) # if x % 2 == 1
b = (x - 3) + ceiling(((x + 2) / 2) - 1) # if x % 2 == 1
Which means b
= (x - 3) + ceiling(((x + 2) / 2) – 1).
We will call
n = ceiling(((x + 2) / 2) – 1) # b = (x + 3) + n
At this point, xβ = xα – n. Consider xβ = xβ + 3 = xα – n + 3
At this point, xβ = xα – n. Consider xβ = xβ + 3 = xα – n + 3
The while xβ > y indicates how long it
takes for xβ == y (xβ % 2 == 0) or xβ < y
(x % 2 == 1) following the xβ - 1 // y + 2 approach:
|
xβ
|
y
|
b
|
|
xβ
(xα – n + 3)
|
1 (y)
|
+ 0
|
|
xβ
– 1 (xβ – 1)
(xα – n + 3 - 1) |
1 + 2
(y + 1(2)) |
+ 1
|
|
xβ
– 2 (xβ – 2)
(xα – n + 3 - 2) |
1 + 4
(y + 2(2)) |
+ 2
|
|
-
|
-
|
-
|
|
xβ-final
(xβ – q)
(xα – n + 3 - q) |
yfinal
(y + 2q or 1 + 2q) |
+ q
|
xβ – q ≤ 1 + 2q
xβ ≤ 1 + 3q
xβ – 1 ≤ 3q
(xβ – 1 / 3) ≤ q
So we have:
b = (x - 3) + n + (xβ – 1 / 3) # if x % 2 == 0
b = (x - 3) + n + ceiling(xβ – 1 / 3) # if x % 2 == 1
In conclusion, when x > 3:
b = (x – 3) + n + ceiling(xβ – 1 / 3)
b = (x – 3) + n + q # ultra-simplified
b = (x – 3) + n + ceiling(xα – n + 2 / 3) #in “x”-n terms
b = (x – 3) + n + ceiling(x – n + 4 / 3) #in x-n terms
b = (x - 3) + n + ceiling(xβ – 1 / 3) # if x % 2 == 1
In conclusion, when x > 3:
b = (x – 3) + n + ceiling(xβ – 1 / 3)
b = (x – 3) + n + q # ultra-simplified
b = (x – 3) + n + ceiling(xα – n + 2 / 3) #in “x”-n terms
b = (x – 3) + n + ceiling(x – n + 4 / 3) #in x-n terms
Machine 4:
How can we find b if x > 1?
This one will require checking inputs and outputs:
|
x
|
m_4(x)
|
|
2
|
3
|
|
3
|
3
|
|
4
|
4
|
|
5
|
4
|
|
6
|
6
|
|
7
|
6
|
|
8
|
7
|
In this case we have pairs that produce the same value thus creating a sequence like so:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18 . . .
This has a repeated pattern of + 3 + 1 + 2 + 1 + . . .
When a number is able to accomplish both boolean statements, b increases by 3 (machine_4(2)). When the z % 2 == 0 statement is accomplished by itself, b increases by 2 (machine_4(6)).
Now we can color code the sequence to indicate when b increase by 2 and when it increases by 3:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .
Both of these sets are separated by 7 (1 + 3 + 1 + 2 // 1 + 2 + 1 + 3). Let’s look at the pairs of some of these closely.
Both of these sets are separated by 7 (1 + 3 + 1 + 2 // 1 + 2 + 1 + 3). Let’s look at the pairs of some of these closely.
|
n ∊ Blue
|
Pair
|
n ∊ Red
|
Pair
|
|
3
|
2, 3
|
6
|
6, 7
|
|
10
|
10, 11
|
13
|
14, 15
|
|
17
|
18, 19
|
20
|
22, 23
|
These pairs have a difference of 8. If we were to assign a color to the other numbers with a 7 difference in a pattern, we might obtain something more concise:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .
We go B, Y, R, G with each pair differentiating by 8.
Pooling all this information to calculate b, we first establish the original
B-Y-R-G pairs.
B: 2, 3. Y: 4, 5. R: 6, 7. G: 8, 9
Then we say that if your x is an item in the original B-Y-R-G pairs + 8n, then you must get the original B-Y-R-G pair values (3, 4, 6, 7) and add it by 7n
Ex.1: machine_4(29) = b. Calculate b.
Can 29 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
29 % 8 = 5. Does this mean that 29 = 5 + 8n?
Prove: 29 – 5 = 8n. 24 = 8n. 3 = n.
Y: 4, 5 = 4
So therefore 29 could be 4 + 7(3).
check - machine_4(29) == 25. True!
(Note: this also means that machine_4(28) == 25 is True)
Ex.2: machine_3(33) = b. Calculate b.
Can 33 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
33 % 8 = 1. What does this mean? Consider an int such that it can be represented by 8 + 8n. This int % 8 = 0. Does this mean that if an int % 8 = 1, it would have to be represented as 9 + 8n?
Prove: 33 – 9 = 8n. 24 = 8n. 3 = n.
(Note: You can also consider 9 + 8n as 1 + 8 + 8n)
G: 8, 9 = 7
So therefore 33 could be 7 + 7(3).
check – machine_4(33) == 28. True!
(Note: this also means that machine_4(32) == 28 is True)
B: 2, 3. Y: 4, 5. R: 6, 7. G: 8, 9
Then we say that if your x is an item in the original B-Y-R-G pairs + 8n, then you must get the original B-Y-R-G pair values (3, 4, 6, 7) and add it by 7n
Ex.1: machine_4(29) = b. Calculate b.
Can 29 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
29 % 8 = 5. Does this mean that 29 = 5 + 8n?
Prove: 29 – 5 = 8n. 24 = 8n. 3 = n.
Y: 4, 5 = 4
So therefore 29 could be 4 + 7(3).
check - machine_4(29) == 25. True!
(Note: this also means that machine_4(28) == 25 is True)
Ex.2: machine_3(33) = b. Calculate b.
Can 33 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
33 % 8 = 1. What does this mean? Consider an int such that it can be represented by 8 + 8n. This int % 8 = 0. Does this mean that if an int % 8 = 1, it would have to be represented as 9 + 8n?
Prove: 33 – 9 = 8n. 24 = 8n. 3 = n.
(Note: You can also consider 9 + 8n as 1 + 8 + 8n)
G: 8, 9 = 7
So therefore 33 could be 7 + 7(3).
check – machine_4(33) == 28. True!
(Note: this also means that machine_4(32) == 28 is True)
Basically:
Let x % 8 = m
If m = 2 or 3: x can be written as 2 + 8n or 3 + 8n
Solve for n, then plug in for 3 + 7n = b
If m = 4 or 5: x can be written as 4 + 8n or 5 + 8n
Solve for n, then plug in for 4 + 7n = b
If m = 6 or 7: x can be written as 6 + 8n or 7 + 8n
Solve for n, then plug in for 6 + 7n = b
If m = 0 or 1: x can be written as 8 + 8n or 9 + 8n
Solve for n, then plug in for 7 + 7n = b
Machine 5:
How can we find a if x > 2?
The while x > z loop will stop when x ≤ 2 and a
increases every time x decreases by 1, meaning a so far equals:
a = (x – 2) + inner while loop
The inner while loop creates the x + x – 1 + x – 2 … + 1 sequence with x – 2. Since that sequence is normally (x)(x – 1)/2 and (x – 1) represents the lowest point, we must change this to (x – 2)(x – 1) / 2. Thus:
a = (x – 2) + ((x – 2)(x – 1) / 2)
a = (x – 2) + ((x2 – 3x – 2) / 2)
a = (x – 2) + inner while loop
The inner while loop creates the x + x – 1 + x – 2 … + 1 sequence with x – 2. Since that sequence is normally (x)(x – 1)/2 and (x – 1) represents the lowest point, we must change this to (x – 2)(x – 1) / 2. Thus:
a = (x – 2) + ((x – 2)(x – 1) / 2)
a = (x – 2) + ((x2 – 3x – 2) / 2)
###################################################################
def machine_1(x):
y = 1
z = 0
while x > y:
y = y + 1
z = z + 1
if x > z:
x = x - 1
z = z + 1
return z
def machine_2(x):
x = x + 2
y = 1
z = 2
a = 0
while x > y:
y = y + 1
if y == z:
a = a + 1
z = z + 2
a = a + 1
return a
def machine_3(x):
y = 1
z = 2
a = 3
b = 0
while x > a:
a = a + 1
b = b + 1
x = x + 2
while x > z:
x = x - 1
z = z + 1
b = b + 1
x = x + 3
while x > y:
y = y + 2
x = x - 1
b = b + 1
return b
def machine_4(x):
y = 0
z = 0
a = 1
b = 0
while x > a:
a = a + 1
x = x - 1
b = b + 1
z = a
if z % 2 == 0:
y = y + 1
b = b + 1
if y % 2 == 1:
b = b + 1
return b
def machine_5(x):
z = 2
a = 0
while x > z:
y = x
while y > z:
y = y - 1
a = a + 1
x = x - 1
a = a + 1
return a
No comments:
Post a Comment