/
pseudocode.html
130 lines (99 loc) · 9.15 KB
/
pseudocode.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
<!DOCTYPE html><html xmlns:dc="http://purl.org/dc/terms/"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name="viewport" content="width=device-width"><link rel=stylesheet type="text/css" href="/style.css">
<script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { availableFonts: ["STIX","TeX"], linebreaks: { automatic:true }, preferredFont: "TeX" },
tex2jax: { displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], processEscapes: true } });
</script><script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_HTML-full"></script></head><body> <div class="header">
<nav><p><a href="#navigation">Menu</a> - <a href="#top">Top</a> - <a href="/">Home</a></nav></div>
<div class="mainarea" id="top">
<h1 id="pseudocode-conventions">Pseudocode Conventions</h1>
<p><a href="mailto:poccil14@gmail.com"><strong>Peter Occil</strong></a></p>
<p><a id="Introduction"></a></p>
<h2 id="introduction">Introduction</h2>
<p>This document explains the conventions and common functions used in some of my articles that use pseudocode.</p>
<p><a id="Symbols"></a></p>
<h2 id="symbols">Symbols</h2>
<p>In addition to the familiar <code>+</code>, <code>-</code>, <code>*</code> (multiplication), and <code>/</code> (division) operators, other symbols are defined below.</p>
<ul>
<li><code>pi</code> is the constant π, the ratio of a circle’s circumference to its diameter.</li>
<li><code>nothing</code> indicates the absence of a value. It corresponds to <code>null</code> in Java, C#, and JavaScript, <code>nil</code> in Ruby, and <code>None</code> in Python.</li>
<li><code>true</code> and <code>false</code> are the two Boolean values.</li>
<li><code>==</code> means “is equal to”.</li>
<li><code>!=</code> means “is not equal to”.</li>
<li>A minus before a variable means 0 minus that variable. For example, <code>-a</code> means <code>(0 - a)</code>.</li>
<li>The <code><<</code> operator in the pseudocode is a bitwise left shift, with both sides of the operator being integers. If each side is 0 or greater, it is the same as multiplying the left-hand side by 2<sup><em>n</em></sup>, where <em>n</em> is the right-hand side.</li>
<li>The <code>>></code> operator in the pseudocode is a bitwise right shift, with both sides of the operator being integers. If each side is 0 or greater, it is the same as dividing the left-hand side by 2<sup><em>n</em></sup>, where <em>n</em> is the right-hand side, and discarding the fractional part of the result.</li>
<li>The <code>|</code> operator in the pseudocode is a bitwise OR operator between two integers. It combines the bits of both integers so that each bit is set in the result if the corresponding bit is set on either or both sides of the operator.</li>
</ul>
<p><a id="Loops"></a></p>
<h2 id="loops">Loops</h2>
<p>Pseudocode may use <code>while</code> loops, which are self-explanatory.</p>
<p>Pseudocode may also use <code>for</code> loops, defined as follows:</p>
<ul>
<li><code>for X in Y...Z; [[Statements]] ; end</code> is shorthand for <code>X = Y; while X < Z; [[Statements]]; X = X + 1; end</code>.</li>
<li><code>for X in Y...Z: [[Single-Statement]]</code> is shorthand for <code>X = Y; while X < Z; [[Single-Statement]]; X = X + 1; end</code>.</li>
</ul>
<p><a id="Lists_and_Files"></a></p>
<h2 id="lists-and-files">Lists and Files</h2>
<p>In the pseudocode, lists are indexed starting with 0. That means the first item in the list has index 0, the second item in the list has index 1, and so on, up to the last item, whose index is the list’s size minus 1.</p>
<p>In this context, a <em>list</em> is to be understood as a resizable array of items, not as a linked list.</p>
<p>A <em>list</em> can be expressed by wrapping items in brackets; for example, <code>[0, 1, 2]</code> is a three-item list.</p>
<ul>
<li><code>NewList()</code> or <code>[]</code> creates a new empty list.</li>
<li><code>AddItem(list, item)</code> adds the item <code>item</code> to the list <code>list</code>.</li>
<li><code>size(list)</code> returns the size of the list <code>list</code>.</li>
<li><code>list[k]</code> refers to the item at index <code>k</code> of the list <code>list</code>.</li>
<li><code>GetNextLine(file)</code> is a method that gets the next line from a file, or returns <code>nothing</code> if the end of the file was reached.</li>
</ul>
<p><a id="Functions"></a></p>
<h2 id="functions">Functions</h2>
<ul>
<li><code>sqrt(a)</code> is the square root of <code>a</code>, and is equivalent to <code>pow(a, 0.5)</code>.</li>
<li><code>ln(a)</code> is the natural logarithm of <code>a</code>.</li>
<li><code>exp(a)</code> is the inverse natural logarithm of <code>a</code>. Also known as the base of natural logarithms raised to the power <code>a</code>, so that <code>exp(1)</code> is the base of natural logarithms commonly denoted <em>e</em>.</li>
<li><code>pow(a, b)</code> is the number <code>a</code> raised to the power <code>b</code>.</li>
<li><code>sin(a)</code>, <code>cos(a)</code>, and <code>tan(a)</code> are the sine, cosine, and tangent of the angle <code>a</code>, respectively, where <code>a</code> is in radians.</li>
<li><code>atan2(y, x)</code> is—
<ul>
<li>the inverse tangent of <code>y/x</code>, in radians, if <code>x > 0</code>,</li>
<li>π plus the inverse tangent of <code>y/x</code>, in radians, if <code>y >= 0 and x < 0</code>,</li>
<li>−π plus the inverse tangent of <code>y/x</code>, in radians, if <code>y < 0 and x < 0</code>,</li>
<li>−π divided by 2 if <code>y < 0 and x == 0</code>,</li>
<li>π divided by 2 if <code>y > 0 and x == 0</code>, and</li>
<li>0 if <code>y == 0 and x == 0</code>.</li>
</ul>
</li>
<li><code>abs(a)</code> is the absolute value of <code>a</code>; it makes negative numbers nonnegative.</li>
<li><code>min(a, b)</code> is the smaller of <code>a</code> and <code>b</code>.</li>
<li><code>max(a, b)</code> is the larger of <code>a</code> and <code>b</code>.</li>
<li><code>floor(a)</code> is the highest integer that is less than or equal to <code>a</code>.</li>
<li><code>rem(a, b)</code> is the part of <code>b</code> that does not divide evenly into <code>a</code>, where the result has the sign of <code>b</code>. This operation is equivalent to <code>a - floor(a / b) * b</code>.</li>
<li><code>ceil(a)</code> is the lowest integer that is greater than or equal to <code>a</code>. This function is equivalent to <code>(0 - floor(0 - a))</code>.</li>
</ul>
<p><strong>Notes:</strong></p>
<ul>
<li>The inverse sine, in radians, of <code>a</code> is equivalent to <code>atan2(a, sqrt(1.0 - a * a))</code>.</li>
<li>The inverse cosine, in radians, of <code>a</code> is equivalent to <code>atan2(sqrt(1.0 - a * a), a)</code>.</li>
<li>An integer <code>n</code> is <em>odd</em> if <code>rem(n, 2)</code> is 1.</li>
<li>An integer <code>n</code> is <em>even</em> if <code>rem(n, 2)</code> is 0.</li>
</ul>
<p><a id="Pseudocode_Notes"></a></p>
<h2 id="pseudocode-notes">Pseudocode Notes</h2>
<p>In the pseudocode:</p>
<ul>
<li>Divisions do not round to an integer. (In some programming languages, division of two integers results in an integer, which may be rounded differently depending on the language. For instance, Python’s and Ruby’s integer division does a floor rounding on the result of division, while Java’s discards the fractional part of the result of division.)</li>
<li>The pseudocode shown is not guaranteed to cover all error handling, such as recovery from overflows, out-of-bounds memory accesses, divisions by zero, unexpected infinity values, and other errors that might happen in a particular implementation.</li>
<li>The pseudocode shown is not guaranteed to yield high performance in a particular implementation, either in time or memory.</li>
<li>In general, computer implementations of the operators and functions above risk numerical errors, since computers generally can’t operate “exactly” on real numbers. (This is less of an issue if the implementation uses an arbitrary-precision rational number format and the pseudocode uses only rational arithmetic and inputs. In addition, an implementation can work with <em>symbolic</em> representations of real numbers instead of those numbers.)</li>
</ul>
<p><a id="License"></a></p>
<h2 id="license">License</h2>
<p>This page is licensed under <a href="https://creativecommons.org/publicdomain/zero/1.0/"><strong>Creative Commons Zero</strong></a>.</p>
</div><nav id="navigation"><ul>
<li><a href="/">Back to start site.</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io">This site's repository (source code)</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io/issues">Post an issue or comment</a></ul>
<div class="noprint">
<p>
<a href="//twitter.com/intent/tweet">Share via Twitter</a>, <a href="//www.facebook.com/sharer/sharer.php" id="sharer">Share via Facebook</a>
</p>
</div>
<p style='font-size:120%;font-weight:bold'><a href='https://peteroupc.github.io/pseudocode.pdf'>Download a PDF of this page</a></p></nav></body></html>