-
Notifications
You must be signed in to change notification settings - Fork 3
/
mult.html
165 lines (151 loc) · 5.84 KB
/
mult.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
<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="q8.html#challenge0">Previous</a>
<a class="navbar-brand page-scroll" href="pong.html">Next</a>
</div>
</div>
</nav>
<section style="margin-top: 5em; max-width: 50em;">
<h1>Multiplication with Q8</h1>
<p>As a gentle introduction to the Quine8 (Q8) tool, we'll start by multiplying two numbers.
Because the Q8 instruction set does not contain a multiply operation, we'll have to write our own.
The algorithm for multiplication is pretty easy, you probably learned it in grade school.</p>
<div class="code_container">
<pre><code class="language-none">6 * 4 = 24</code></pre>
</div>
<p style="text-align: center;">That can be expanded in one of two ways:</p>
<div class="code_container">
<div style="margin-right: 0.25em;">
<pre><code class="language-none;">6 + 6 + 6 + 6 = 24
6, 4 times is 24</pre></code>
</div>
<div style="margin-left: 0.25em;">
<pre><code class="language-none;">4 + 4 + 4 + 4 + 4 + 4 = 24
4, 6 times is 24</pre></code>
</div>
</div>
<p style="text-align: center">In a C-like language, they look like this:</p>
<div class="code_container">
<div style="margin-right: 0.25em;">
<pre><code class="language-c; line-numbers">int x = 0;
for (int i = 4; i > 0; i--) {
x += 6;
}</code></pre>
</div>
<div style="margin-left: 0.25em;">
<pre><code class="language-c; line-numbers">int x = 0;
for (int i = 6; i > 0; i--) {
x += 4;
}</code></pre>
</div>
</div>
<p>If you look at the two examples carefully, you'll notice that one of the 2 will resolve faster than the other.
4 times through the loop is faster than 6, and the larger the difference between the two numbers, the more this
will effect runtime. If we ran 2 * 50, it would either run through the incremental loop twice or fifty times. That
makes a huge difference, especially for the Q8 bytecode.</p>
<pre><code class="language-none">Loop ops: 10
Add Increment tiles: 11
1 time through the loop: 10 + 11 = 21 tiles
2 times through the loop: 21 * 2 = 42 tiles
50 times through the loop: 21 * 50 = 1,050 tiles
</code></pre>
<p>Assuming each tile takes 1 second, that's the difference between running in 42 seconds,
and running for 17 and a half minutes. This is an optimization definitely worth having.</p>
</section>
<section>
<div class="multi_code_container">
<div class="img_col_container">
<h3>Bytecode Program</h3>
<a href="q8.html#AwRgrMwExikgNhAUypSYGQQdnSAQygBZ0zyLLKoAzQ4ATnyxAA4QBjGu0zUA4gGYqI0WPKI4UPMABGUBN2CYQhEuSylx2nbr36Dho8ZOmz5i5avlBHIA">
<img class="img_link" style="width: 80%;" src="mult.gif">
</a>
</div>
<div>
<h3>Assembly Program</h3>
<pre><code class="language-none; line-numbers">>0
start:
LOAD A x ; load x
LOAD B y ; load y
CMP A B ; is x > y?
JG swap ; goto swap
>9
save_var:
STORE A i ; save min(x, y) as i
STORE B inc ; save max(x, y) as increment
JMP loop
>32
swap:
SWAP A B ; (x, y) -> (y, x)
JMP save_var
>36
loop:
LOAD A i ; get i
ISZERO A ; is i == 0?
JZ exit
DEC A ; i--
STORE A i ; save new i
JMP add_increment
>67
add_increment:
LOAD A cumulative ; read in cumulative value
LOAD B inc ; read in increment
ADD A B ; cumulative = cumulative + increment
JERR exit ; if overflow, exit
STORE A cumulative ; save new cumulative
JMP loop
>255
exit:
HALT
; DATA
>80
x: $6
y: $4
>96
i: $0
cumulative: $0
>112
inc: $0
</code></pre>
</div>
</div>
</section>
<!-- Bootstrap core JavaScript
================================================== -->
<!-- Placed at the end of the document so the pages load faster -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.3/jquery.min.js"></script>
<script>window.jQuery || document.write('<script src="../../assets/js/vendor/jquery.min.js"><\/script>')</script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js" integrity="sha384-0mSbJDEHialfmuBBQP6A4Qrprq5OVfW37PRR3j5ELqxss1yVqOtnepnHVP9aJ7xS" crossorigin="anonymous"></script>
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<script src="ie10-viewport-bug-workaround.js"></script>
<script src="jquery.easing.min.js"></script>
<script src="scrolling-nav.js"></script>
<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>