mirror of
https://github.com/reactos/web-content.git
synced 2025-05-16 03:55:55 +00:00
45d33cf1ba
That way they really work as on our old website, otherwise it was reactos.org/project-news/node/295 and not reactos.org/node/295
10 lines
6.2 KiB
HTML
10 lines
6.2 KiB
HTML
---
|
||
title: "Rounding and integer math"
|
||
author: "ThePhysicist"
|
||
date: 2015-05-16
|
||
aliases: [ /node/941 ]
|
||
|
||
---
|
||
|
||
<p><br />It sometimes happens that in your program you need to divide integer values and then round the result.<br />Something like</p><p><code> int result = lrint((double)int_a / (double)int_b);</code><br /><br />But sometimes it is desirable to not use floating point math at all. The question is: Can we do the same calculation with integer math and get exactly the same result?<br /><br />Let's simplify our case, by limiting to unsigned values (for signed values it is very similar, only the formulas get a bit more complex).<br />Let's also convert the lrint() into integer truncation:<br /><br /><code> #define trunc(x) ((int)(x))<br /> unsigned int result = trunc( ((double)uint_a / (double)uint_b) + 0.5 );</code><br /><br />If we wanted to write this in integer math, we could do something like<br /><br /><code> unsigned int result = (uint_a + (uint_b/2)) / uint_b;</code><br /><br />But is this really the same?<br /><br />Lets have a look at it in a more mathematical way:<br /><br />We define 2 functions:<br />round(<em>x</em>) rounds <em>x</em> to the nearest natural number<br />trunc(<em>x</em>) rounds <em>x</em> to the next natural number towards 0<br /><br />First the case where <em>b</em> is an even number.<br />Let <em>a</em> be a positive natural number and <em>b</em> be an even positive natural number<br />(<em>b</em> = 2·<em>c</em>)<br /><br /> round(<em>a</em> ∕ <em>b</em>)<br /> = trunc((<em>a</em> ∕ <em>b</em>) + 0.5)<br /> = trunc((<em>a</em> ∕ (2·<em>c</em>)) + 0.5)<br /> = trunc((<em>a</em> ∕ (2·<em>c</em>)) + (0.5·(2·<em>c</em>) ∕ (2·<em>c</em>)))<br /> = trunc((<em>a</em> + <em>c</em>) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + (<em>b</em>∕2)) ∕ <em>b</em>)<br /><br />So if <em>b</em> is an even number, the math is right.<br />What about odd numbers? obviously we are truncating the <em>b</em> ∕ 2 inside our formula, when using intergers only.<br /><br />Let <em>a</em> be a positive natural number and <em>b</em> be an odd positive natural number<br /> <em>b</em> = <em>2</em>·c + 1<br /> => <em>b</em> ∕ 2 = <em>c</em> + 0.5<br /> => <em>c</em> = <em>b</em> ∕ 2 - 0.5<br /><br />We still have<br /><br /> trunc((<em>a</em> + (<em>b</em> ∕ 2)) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + ((2·<em>c</em> + 1) / 2)) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + <em>c</em> + 0.5) ∕ <em>b</em>)<br /> = trunc(((<em>a</em> + <em>c</em>) ∕ <em>b</em>) + (0.5 ∕ <em>b</em>))<br /><br />This is different from our integer math, which would look like this:<br /><br /> trunc((<em>a</em> + trunc(<em>b</em> ∕ 2)) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + trunc((2·<em>c </em>+ 1) ∕ 2)) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + trunc(<em>c</em> + 0.5)) ∕ <em>b</em>)<br /> = trunc((<em>a</em> + <em>c</em>) ∕ <em>b</em>)<br /><br />But are those different?<br />Let's make the assumption they are different. Let us also limit the<br />range of <em>a</em> to a value between 1 and <em>b</em>. This can be justified, since you can always<br />factor out an instance of <em>b</em> for all <em>a</em> > <em>b</em>, with <em>a</em> = <em>a</em><sub>0</sub> + <em>n</em>·<em>b</em>.<br /><br />Let 1 <= <em>a</em> < <em>b</em><br /><br />First some pre-investigation, that will be helpful later:<br /><br /> (<em>a</em> + <em>c</em>) ∕ <em>b</em><br /> = (<em>a</em> + (<em>b ∕ </em>2 - 0.5)) ∕ <em>b</em><br /> < (<em>a</em> + <em>b</em> ∕ 2) ∕ <em>b</em><br /> = <em>a ∕ </em><em>b</em> + 0.5<br /><br /> => (<em>a</em> + <em>c</em>) ∕ <em>b</em> < <em>a</em> ∕ <em>b</em> + 0.5<br /> [since <em>a</em> < <em>b</em> => <em>a ∕ </em><em>b</em> < 1]<br /> => (<em>a</em> + <em>c</em>) ∕ <em>b</em> < 1.5<br /><br />Assumption:<br /> trunc((<em>a</em> + <em>c</em>) ∕ <em>b</em>) ≠ trunc((<em>a</em> + <em>c</em>) ∕ <em>b</em> + 0.5 ∕ <em>b</em>)<br /><br />There are 2 cases, where this can be true:<br />case A: (<em>a</em> + <em>c</em>) ∕ <em>b</em> + 0.5 ∕ <em>b</em> ≥ 2<br />case B: (<em>a</em> + <em>c</em>)<em> ∕ b</em> < 1 & (<em>a</em> + <em>c</em>) ∕ <em>b</em> + 0.5 ∕ <em>b</em> > 1<br /><br /><strong>case A:</strong><br /> (<em>a</em> + <em>c</em>) ∕ <em>b</em> + 0.5 ∕ <em>b</em> ≥ 2<br /> [since (<em>a</em> + <em>c</em>) ∕ <em>b</em> < 1.5]<br /> => 0.5 ∕ <em>b</em> ≥ 0.5<br /> => contradiction!<br /><br /><strong>case B:</strong><br /> (<em>a</em> + <em>c</em>) ∕ <em>b</em> < 1 & (<em>a</em> + <em>c</em>) ∕ <em>b</em> + 0.5 ∕ <em>b</em> > 1<br /> => (<em>a</em> + <em>c</em>) ∕ <em>b</em> < 1 & (<em>a</em> + <em>c</em> + 0.5) ∕ <em>b</em> > 1<br /> => (<em>a</em> + <em>c</em>) < <em>b</em> & (<em>a</em> + <em>c</em> + 0.5) > <em>b</em><br /> [since <em>b</em> = (2·<em>c</em> + 1)]<br /> => (<em>a</em> + <em>c</em>) < (2·<em>c</em> + 1) & (<em>a</em> + <em>c</em> + 0.5) > (2·<em>c</em> + 1)<br /> => <em>a</em> < <em>c</em> + 1 & <em>a</em> > <em>c</em> + 0.5<br /><br /> => (<em>c</em> + 0.5) < <em>a</em> < (<em>c</em> + 1)<br /> [since a is an integer]<br /> => (<em>c</em> + 1) ≤ <em>a</em> < (<em>c</em> + 1)<br /> => contradiction!<br /><br />Q.E.D.<br /> </p>
|