-
Notifications
You must be signed in to change notification settings - Fork 0
/
Collatz.html
131 lines (122 loc) · 8.57 KB
/
Collatz.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module Collatz</title>
</head><body bgcolor="#f0f0f8">
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"> <br><big><big><strong>Collatz</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/v/filer4b/v38q001/mas5774/summer14/private-repo/Collatz.py">/v/filer4b/v38q001/mas5774/summer14/private-repo/Collatz.py</a></font></td></tr></table>
<p><tt># ---------------------------<br>
# Copyright (C) 2014<br>
# Mark Sandan<br>
# ---------------------------</tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
<tr><td bgcolor="#ee77aa"><tt> </tt></td><td> </td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="Collatz.html#Cache">Cache</a>
</font></dt></dl>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom> <br>
<font color="#000000" face="helvetica, arial"><a name="Cache">class <strong>Cache</strong></a></font></td></tr>
<tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
<td colspan=2><tt>The <a href="#Cache">Cache</a> object is initialized with an integer that<br>
determines the size of the cache.<br>
<br>
The cache is an object that keeps a list.<br>
It has basic read and write functions as well<br>
as a size function.<br>
<br>
Since the Collatz inputs are > 0, but the cache <br>
is zero-indexed, the nth entry is read[n-1] and<br>
similarly for write.<br>
<br>
<br>
see cycle_length and collatz_eval for details on usage<br> </tt></td></tr>
<tr><td> </td>
<td width="100%">Methods defined here:<br>
<dl><dt><a name="Cache-__init__"><strong>__init__</strong></a>(self, size)</dt></dl>
<dl><dt><a name="Cache-read"><strong>read</strong></a>(self, i)</dt><dd><tt>The read method takes an index i as input.<br>
An assertion is placed to make sure i > 0.<br>
A try block is used to return whatever is<br>
in the ith index of the cache. Since the cache<br>
is implemented as a list, the i-1 th element<br>
is indexed and returned.<br>
<br>
If an IndexError exception is raised,<br>
it is caught and the value 0 is returned instead.</tt></dd></dl>
<dl><dt><a name="Cache-size"><strong>size</strong></a>(self)</dt><dd><tt>The size method takes no arguments and simply returns<br>
the length of the cache (i.e. len(cache))</tt></dd></dl>
<dl><dt><a name="Cache-write"><strong>write</strong></a>(self, i, val)</dt><dd><tt>The write method takes an index i as input as <br>
well as value val to write in index i.<br>
<br>
An assertion is placed to make sure i > 0.<br>
<br>
A try block is used in case an IndexError exception<br>
is raised. In case it is raised, the write to the<br>
cache fails and the cache is not modified and no <br>
value is returned.<br>
<br>
Otherwise, the cache is modified by writing val to <br>
cache[i-1]. Again, no value is returned.</tt></dd></dl>
</td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#eeaa77">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Functions</strong></big></font></td></tr>
<tr><td bgcolor="#eeaa77"><tt> </tt></td><td> </td>
<td width="100%"><dl><dt><a name="-collatz_eval"><strong>collatz_eval</strong></a>(i, j)</dt><dd><tt>i is the beginning of the range, inclusive<br>
j is the end of the range, inclusive<br>
return the max cycle length in the range [i, j]<br>
<br>
implements optimization 2 which halves the space<br>
of cycle_length calculations:<br>
let i,j natural numbers<br>
if i<=j and i < j/2 then <br>
<a href="#-collatz_eval">collatz_eval</a>(i,j)=<a href="#-collatz_eval">collatz_eval</a>(j/2,j)<br>
<br>
cache usage:<br>
An empty cache is instantiated here with size k<br>
which is the maximim of the inputs i,j given.<br>
Thus the cache will contain indices from 0 to k-1. <br>
The cache is passed to the cycle_length function<br>
which uses it to look up and write to the cache.</tt></dd></dl>
<dl><dt><a name="-collatz_print"><strong>collatz_print</strong></a>(w, i, j, v)</dt><dd><tt>print three ints<br>
w is a writer<br>
i is the beginning of the range, inclusive<br>
j is the end of the range, inclusive<br>
v is the max cycle length</tt></dd></dl>
<dl><dt><a name="-collatz_read"><strong>collatz_read</strong></a>(r)</dt><dd><tt>read two ints<br>
r is a reader<br>
return a list of the two ints, otherwise a list of zeros</tt></dd></dl>
<dl><dt><a name="-collatz_solve"><strong>collatz_solve</strong></a>(r, w)</dt><dd><tt>read, eval, print loop<br>
r is a reader<br>
w is a writer</tt></dd></dl>
<dl><dt><a name="-cycle_length"><strong>cycle_length</strong></a>(n, cache)</dt><dd><tt>read two ints<br>
r is a reader<br>
return a list of the two ints, otherwise a list of zeros<br>
<br>
implements optimization 1 which combines two steps of the <br>
collatz algorithm into one whenever n is odd by<br>
calculating n = n + (n>>1) +1. The cycle length c_len<br>
is incremented accordingly.<br>
<br>
cache usage:<br>
Before the cycle length is actually calculated,<br>
it will first read the cache to obtain the value in <br>
the nth index. If there is no such value, 0 is returned<br>
since the cache is intialized to 0.<br>
Otherwise if there is a cache hit then the cycle length<br>
is adjusted accordingly and the cache is written to <br>
accordingly with that value. The value is then returned.<br>
<br>
In any case once the cycle_length calculation is done,<br>
the cache is written to.</tt></dd></dl>
</td></tr></table>
</body></html>