StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can decompose a larger division into multiple chunks that do division with less bits. As another poster already mentioned the algorithm can be found in TAOCP from Knuth.</p> <p>However, no need to buy the book!</p> <p>There is a code on the hackers delight website that implements the algorithm in C. It's written to do 64 bit unsigned divisions using 32 bit arithmetic only, so you can't directly cut'n'paste the code. To get from 64 to 128 bit you have to widen all types, masks and constans by two e.g. a short becomes a int, a 0xffff becomes 0xffffffffll ect. </p> <p>After this easy easy change you should be able to do 128bit divisions. </p> <p>The code is here: <a href="http://www.hackersdelight.org/HDcode/divlu.c" rel="noreferrer">http://www.hackersdelight.org/HDcode/divlu.c</a> (may wrap badly in a web-browser due to line-endings. If so just save the code and open it with notepad or so).</p> <p>Since your largest values only need 96 bit, One of the 64 bit divisions will <strong>always</strong> return zero, so you can even simplify the code a bit. </p> <p>Oh - and before I forget this: The code only works with unsigned values. To convert from signed to unsigned divide you can do something like this (pseudo-code style):</p> <pre><code>fixpoint Divide (fixpoint a, fixpoint b) { // check if the integers are of different sign: fixpoint sign_difference = a ^ b; // do unsigned division: fixpoint x = unsigned_divide (abs(a), abs(b)); // if the signs have been different: negate the result. if (sign_difference < 0) { x = -x; } return x; } </code></pre> <p>The website itself is worth checking out as well: <a href="http://www.hackersdelight.org/" rel="noreferrer">http://www.hackersdelight.org/</a></p> <p>Hope it helps.</p> <p>Btw - nice task that you're working on.. Do you mind telling us for what you need the fixedpoint library?</p> <hr> <p>Btw - the ordinary shift and subtract algorithm for division would work as well. </p> <p>If you target x86 you can implement it using MMX or SSE intrinsics. The algoritm relies only on primitive operations, so it could perform quite fast as well.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload