Mike Gerwitz

Activist for User Freedom

 summaryrefslogtreecommitdiffstats log msg author committer range
blob: 078d383f66b2478b992fc9d1689a0638bd7d420e (plain)
 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 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238  .highlight .hll { background-color: #ffffcc } .highlight .c { color: #888888 } /* Comment */ .highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */ .highlight .k { color: #008800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */% Host Environment \begindeptgroup{it} \def\minmem{$128$~megabytes} This specification defines a rater designed for integration with LoVullo's Quote Server. \section{Quote Server Integration} \label{s:hostenv-qs} \index{quote server|(} \incomplete The implementation \must satisfy at least one of the following criteria: \begin{enumerate} \item The implementation \shall be written in, or compile to, ^JavaScript and shall provide a \func{rate} function, which \shall itself exchange data with the Quote Server in an implementation-defined manner.\footnote{There is currently no specification for the Quote Server; one is needed.} \item The implementation \shall be written in, or compile to, ^PHP and shall integrate with the \index{REST}RESTful interface provided by the ^[LoVullo website] to provide an interface to the Quote Server. \end{enumerate} The implementation \shall return all data suitable for immediate storage in the ^[bucket]. \index{quote server|)} \section{Host Architecture and Operating System} The implementation \shallnot make any assumptions regarding the host architecture, except for those that are enumerated in this section. Furthermore, the implementation \shall ensure that the programming language in which the implementation is written does not violate the requirements of this section, but \shallnot be responsible for any assumptions made by the programming language that are not contradicted within this section.\footnote{This section is intentionally small, as the high-level languages used in the implementation implementation do not rely on many architectural details.} \subsection{Word Size} \p{word-size} The host machine ^[word size] \shall be at least 32-bits long;\footnote{This word size is limited by the architectures of developer PCs and the PCs of users who may be testing the implementation outside of its integration with the Quote Server.} implementation \shallnot depend on the availability of a larger word size unless such an implementation cannot affect the result of any calculation. The requirement of \pref{word-size} does not apply to ^floating-point datatypes, which \may use the full 80~bits permitted by the lower bound of the ^[floating-point!IEEE 754] ^[floating-point!double-extended] precision format. \subsection{Memory Requirements} \index{memory|(} The implementation \shall have at least \minmem\ of memory available exclusively for its use. The implementation \may use additional memory if available, but \shallnot fail to operate within the requirements of this specification if additional memory is not available. If an implementation does not explicitly allocate its own memory (e.g. is a dynamically allocated and garbage-collected language) and the implementation will automatically fail\footnotemark\ if the memory limit is exceeded (a hard memory limit), then the host environment \shall provide at least $32$~extra megabytes of memory in addition to the \minmem, allowing the implementation to query its memory usage and determine when the minimum memory limit has been exceeded. \footnotetext{An example of such a language is ^[PHP]. Other languages, such as JavaScript, will attempt to garbage collect rather than immediately dying.} It is the responsibility of the host environment---not the implementation---to limit memory consumption. Should the implementation be unable to allocate additional memory before reaching \minmem, and such a failure prohibits successful execution of all remaining applicable calculations, then the implementation \shall fail with an unspecified error; the remaining execution path after such a failure is \undefined. \index{memory|)} \subsection{Scheduling} The implementation \shallnot depend on any reasonable scheduling expectations and \shall thus continue operation until explicitly interrupted in any unspecified manner. \section{Numeric Datatypes} An implementation \shallnot use ^fixed-point or ^[binary-coded decimal] (BCD) representations of numbers; ^floating-point \shall be used instead.\footnote{This restriction exists simply because LoVullo does not make use of these other formats.} All floating-point values \shall be represented as a single-precision floating point value as defined by ^[floating-point!IEEE 754]'s ^[floating-point!IEEE 754!binary32] format. This format as a base of $2$; a 24-bit significand (with the highest-order bit implied); an 8-bit exponent; and a single sign bit. Whether higher-precision values are truncated or rounded in order to fit into a single-precision format is unspecified; the rounding mode is also unspecified. All other scalar datatypes that are not ^floating-point \shall be able to be represented by a signed, two's compliment, 32-bit integer representation. Unsigned integer types \shallnot be used as the result of any calculation, but may be used to hold intermediate results, so long as those intermediate values are not returned as the result of another calculation. Intermediate results returned only for debugging purposes are exempt from this requirement and their limits are unspecified, so long as their values are not returned to the Quote Server.\footnote{These restrictions exist to cope with implicit numeric representations of various systems and languages.} Unsigned integer results that can be represented exactly as a ^floating-point value are too exempt from this restriction, so long as the return value indicates that the data type is ^[floating-point]. \subsection{Floating Point Arithmetic} \index{floating-point|(} This section applies only to implementations that make use of ^floating-point arithmetic. Floating point is so-called because the radix point does not have a fixed position. A ^[floating-point!IEEE 754!binary32] ^floating-point value may be computed as $$(-1)^s \left(1+\sum\limits_{i=1}^{23} c_{23-i} 2^{-i}\right) 2^{e-127},$$ where $s$ is the value of the sign bit, $c_i$ represents the base-2 significand (coefficient'') digit $i$, and $e$ represents the exponent. The added $1$ in the calculation is to account for the implicit higher-order bit in the significand. The $-127$ offset at the end of the equation is the exponent bias.\footnote{While it is unlikely that an implementation will have to explicitly compute the value of a binary ^floating-point representation, the knowledge is very useful for understanding issues that arise from ^floating-point arithmetic.} \subsubsection{Handling of Precision Loss} \index{floating-point!rounding|(} Rounding errors are particularly problematic with the use of \func{floor} and \func{ceil} functions, in which the smallest precision error can drastically affect the result of a calculation. The implementation \shallnot assume the availability of access to hardware ^floating-point ^[floating-point!status registers]---or any equivalent software representation---that indicates loss of precision due to truncation or rounding errors.\footnote{Such flags would be ideal, but are inaccessible from both JavaScript and ^[PHP]; we must cater to the lowest common denominator.} The implementation \may employ the common method of performing intermediate calculations in a higher-precision format (higher than single-precision) before storing the result in a single-precision ^floating-point format.\footnote{The rationale behind this decision is that all systems in this office use x86 processors, which support 80-bit ^[floating-point!double-extended] precision ^floating-point registers.} To avoid problems inherent with ^floating-point arithmetic, an implementation \may (and is encouraged to) use integer arithmetic, so long as the results can be sufficiently represented as a signed 32-bit integer type; the integer value may then be converted back into a ^floating-point type. Since a single-precision significand is $23$ bits in length, excluding the implicit high-order bit, this therefore means that an integer value of $-2^{23} \leq n \leq 2^{23}-1$ can be converted between the two types without loss of data, yielding a range of $-8388608 \leq n \leq 8388607$. \begin{ex} Let~$a=0.60$, $b=0.30$ and~$c=0.10$, where~$a$, $b$ and~$c$ are single-precision ^floating-point numbers (^[floating-point!IEEE 754!binary32]). Consider that we wish to apply these variables to the seemingly innocuous calculation $${\left\lfloor 100\left(a+b+c\right) \right\rfloor \over100},$$ which will round up to the nearest penny. Intuitively (and mathematically), we would expect that $${\left\lfloor 100\left(0.60+0.30+0.10\right) \right\rfloor \over100} = {\left\lfloor 100\left(1.00\right) \right\rfloor \over100} = {\left\lfloor 100 \right\rfloor \over100} = 1.00.$$ However, none of the values of~$a$, $b$ or~$c$ can be represented exactly in any binary ^floating-point format due to how it is converted from decimal. Therefore (leaving the details aside), depending on how the implementation performs its arithmetic, we could end up with something like this: $${\left\lfloor 100\left(0.60+0.30+0.10\right) \right\rfloor \over100} = {\left\lfloor 100\left(0.99\overline{9}\right) \right\rfloor \over100} = {\left\lfloor 99.9\overline{9} \right\rfloor \over100} = {99 \over100} = 0.99.\footnotemark$$\footnotetext{This can be seen in ^PHP with \code{var\_dump( floor( 100 * (0.60+0.30+0.10) ) / 100 )}, which yields the value $0.99$. Using the v8 ^JavaScript engine, the same result of $0.99$ is obtained with \code{Math.floor( 100 * (0.60+0.30+0.10) ) / 100}.} While this specific equation may not seem too bad---resulting in only a $0.01$ difference from the expected value, which is still very bad in financial systems---consider what would have happened if we had simply taken the floor; this would have resulted in a $1.00$ difference. Alternatively, we could let~$a=60$, $b=30$ and~$c=10$, add the values using integer arithmetic which will always yield the value~$100$, and then use that value in the equation, eliminating the floating-point precision loss. Since we only care about values up to two decimal places here, such a conversion could be done by casting the value of $100n$ to an integer, which would truncate at the radix point, thereby removing the least inaccurate bits.\footnote{In v8, \code{(0.6*100)+(0.3*100)+(0.1*100)} yields $100$; the same is true for ^[PHP].} \end{ex} It is likely that an implementation does not need the full 24-bits of the significand. When the erroneous portion of a floating-point value is entirely contained within the low-order bits of the significand, an implementation \may truncate or round in an unspecified manner the value to the desired level of precision (if supported by the source language). This method may be useful in preventing rounding errors when using \func{floor} and~\func{ceil} functions. \begin{ex} In IEEE 754 ^[floating-point!IEEE 754!binary32] floating-point, $0.1-0.01 \approx 0.09000000000000001$. This will cause problems if we try to round to the nearest penny, as it would then produce $0.10$ instead of the intended $0.09$. This problem may be eliminated by truncating the value to two decimal places before rounding, if supported by the source language.\footnote{In ^[JavaScript], one could use the convoluted syntax \code{+(0.1-0.01).toPrecision(1)} to yield $0.09$. In ^[PHP], \func{round} will produce the closest floating-point approximation, which could potentially introduce other problems, but happens to work in this case.} \end{ex} \begin{ex} One sure way of truncating a value is to store the portion of the significand desired into an integer. For example, we could obtain $0.09$ by multiplying by $100$, perform integer arithmetic and then divide by $100$ once we are done. \end{ex} \index{floating-point!rounding|)} \index{floating-point|)} \enddeptgroup