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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.8"/>
<title>Dillo: How to Avoid Rounding Errors</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="https://www.dillo.org/dw/html/jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">Dillo
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.8 -->
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
</div><!-- top -->
<div class="header">
<div class="headertitle">
<div class="title">How to Avoid Rounding Errors </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>(Probably, this is a standard algorithm, so if someone knows the name, drop me a note.)</p>
<p>If something like</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[y_i = {x_i a \over b}\]" src="form_49.png"/>
</p>
<p>is to be calculated, and all numbers are integers, a naive implementation would result in something, for which</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[\sum y_i \ne {(\sum x_i) a \over b}\]" src="form_50.png"/>
</p>
<p>because of rounding errors, due to the integer division. This can be avoided by transforming the formula into</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[y_i = {(\sum_{j=0}^{j=i} x_j) a \over b} - \sum_{j=0}^{j=i-1} y_j\]" src="form_51.png"/>
</p>
<p>Of corse, when all <img class="formulaInl" alt="$y_i$" src="form_8.png"/> are calculated in a sequence, <img class="formulaInl" alt="$\sum_{j=0}^{j=i} x_j$" src="form_52.png"/> and <img class="formulaInl" alt="$\sum_{j=0}^{j=i-1} y_j$" src="form_53.png"/> can be accumulated in the same loop. Regard this as sample:</p>
<div class="fragment"><div class="line"><span class="keywordtype">int</span> n, x[n], a, b; <span class="comment">// Should all be initialized.</span></div>
<div class="line"><span class="keywordtype">int</span> y[n], cumX = 0, cumY = 0;</div>
<div class="line"></div>
<div class="line"><span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < n; i++) {</div>
<div class="line"> cumX += x[i]</div>
<div class="line"> y[i] = (cumX * a) / b - cumY;</div>
<div class="line"> cumY += y[i];</div>
<div class="line">}</div>
</div><!-- fragment --> </div></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Sat May 28 2016 11:47:43 for Dillo by  <a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.8
</small></address>
</body>
</html>
|
