-
Notifications
You must be signed in to change notification settings - Fork 3
/
divisor.html
177 lines (165 loc) · 5.54 KB
/
divisor.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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- Bootstrap core CSS -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<link href="ie10-viewport-bug-workaround.css" rel="stylesheet">
<!-- Custom styles for this template -->
<link href="scrolling-nav.css" rel="stylesheet">
<link href="https://bootswatch.com/flatly/bootstrap.min.css" rel="stylesheet">
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body id="page-top" data-target=".navbar-fixed-top">
<nav class="navbar navbar-inverse navbar-fixed-top top-nav-collapse">
<div class="container">
<div class="navbar-header page-scroll">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
<span class="sr-only">Toggle navigation</span>
</button>
<a class="navbar-brand page-scroll" href="index.html">Quine8</a>
<a class="navbar-brand page-scroll" href="bubble.html">Previous</a>
<a class="navbar-brand page-scroll" href="q8.html">Next</a>
</div>
</div>
</nav>
<section style="margin-top: 5em; max-width: 50em;">
<h1>Calculating Divisors with Q8</h1>
<p>This next problem gets a little more mathy, diving into
the middle of a real algorithm, finding divisors of a given value.
As a limitation of the program, it can produce bad data if <code>i * j > 255</code>.
Q8 can only handle values from 0-255, and will overflow if pushed past that maximum.
With that in mind, let's dig into our program!</p>
<p>One of the things put in place here is a bit of an early exit to dramatically
shorten run time. The check to see if <code>i < j</code> ensures that the code doesn't
run past the halfway point and print duplicate divisors. Without the early exit, the
code would print <code>1 12 2 6 3 4 4 3 6 2 12 1</code>, which is a giant waste of time and
effort.</p>
<p>One of the things this program doesn't do, is sort the divisor list. That remains as
a bonus challenge for the reader. You'll notice that it doesn't need a full sort. Half the values
are ascending, and the other half the values are descending. with a little clever array walking code,
you could collate the two, only walking the list once or twice.</p>
</section>
<section>
<div class="multi_code_container">
<div class="c_and_img">
<div>
<h3>C-like Program</h3>
<pre><code class="language-c; line-numbers">int input_value = 12;
int candidate = 0;
// I-LOOP
for (int i = 0; i <= input_value; i++) {
// J-LOOP
for (int j = 0; j <= input_value; j++) {
// GET NEXT CANDIDATE
candidate += i;
if (candidate == input_value) {
if (i > j) {
// EXIT
return;
} else {
// APPEND LIST
// add i, j to divisor array
}
}
}
candidate = 0;
}
</code></pre>
</div>
<div>
<h3>Bytecode Program</h3>
<a href="q8.html#IwQwTADF07fwxT7AMbAmVFgDYxgBmhwkArOqAMxJqRY75hXrmpihlQCc0FbVUJGQioaGlgwAjCBQnY8BAOw4QNURtrpM7PMACmxCEpkQAHFIzBTYS6XuCaZU7jtrNHz19H6I+jN6I2IEhoWHhoixAA==">
<div class="img_container">
<img class="img_link" style="width: 90%; margin-left: 1.5em;" src="divisor.gif">
</div>
</a>
</div>
</div>
<div>
<h3>Assembly Program</h3>
<pre><code class="language-none; line-numbers">; I typically jump into real code at the beginning
; like this to give myself scratch-room if I forget
; something, or need a little more space
>0
JMP i-loop ; Hop into actual code
>32
i-loop:
LOAD A i ; Read in i
LOAD B in ; Read in input_value
CMP A B ; Check to see if the loop has finished
JE exit ; goto exit if done
INC A ; i++
STORE A i ; store i
JMP j-loop
>48
j-loop:
LOAD A j ; Read in j
LOAD B in ; Read in input_value
CMP A B ; Check to see if loop has finished
JE j-loop_reset
INC A ; j++
STORE A j ; store j
JMP get_next_candidate ; goto get next candidate
>60
; reset j and candiate to 0
j-loop_reset:
SET A 0
STORE A j ; set j to 0
STORE A candidate ; set candiate to 0
JMP i-loop
>80
get_next_candidate:
LOAD A candidate ; read in candidate
LOAD B i ; read in i
ADD A B ; candidate += i
STORE A candidate ; store new candiate
LOAD B in ; load input_value
CMP A B ; candidate == input_value?
JE append_list
JMP j-loop
>112
append_list:
LOAD A i ; read in i
LOAD B j ; read in j
CMP A B ; i > j?
JG exit
STOREI A idx ; store i to array[n]
STOREI B idx+ ; store j to array[n+1]
LOAD A idx ; load n
LOAD B idx+ ; load n+1
INC A ;
INC A ; n += 2
INC B ;
INC B ; (n+1) += 2
STORE A idx ; store new n
STORE B idx+ ; store new n+1
JMP j-loop
>255
exit:
HALT
; DATA
>176
idx: $224
idx+: $225
>192
in: $12
i: $0
j: $0
candidate: $0
</code></pre>
</div>
</div>
</section>
<link rel="stylesheet" href="prism.css">
<link href="tutorial_style.css" rel="stylesheet">
<script src="prism.js"></script>
</body>
<footer style="margin-top: 4em; padding-bottom: 4em; background-color: #555"></footer>
</html>