From c3d7c3b2cc0e66495c38127d1ea6bdab18eea4c6 Mon Sep 17 00:00:00 2001 From: lkcl Date: Wed, 13 Apr 2022 10:07:29 +0100 Subject: [PATCH] --- openpower/sv/bitmanip/appendix.mdwn | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 openpower/sv/bitmanip/appendix.mdwn diff --git a/openpower/sv/bitmanip/appendix.mdwn b/openpower/sv/bitmanip/appendix.mdwn new file mode 100644 index 000000000..fffd8c735 --- /dev/null +++ b/openpower/sv/bitmanip/appendix.mdwn @@ -0,0 +1,29 @@ +# big integer division + +the most efficient division algorithm is probably Knuth's Algorithm D (with modifications from the exercises section of his book) which is O(n^2) and uses 2N-by-N-bit div/rem + +an oversimplified version of the knuth algorithm d with 32-bit words is: +(TODO find original) + +``` +void div(uint32_t *n, uint32_t *d, uint32_t* q, int n_bytes, int d_bytes) { + // assumes d[0] != 0, also n, d, and q have their most-significant-word in index 0 + int q_bytes = n_bytes - d_bytes; + for(int i = 0; i < q_bytes / sizeof(n[0]); i++) { + // calculate guess for quotient word + q[i] = (((uint64_t)n[i] << 32) + n[i + 1]) / d[0]; + // n -= q[i] * d + uint32_t carry = 0, carry2 = 0; + for(int j = d_bytes / sizeof(d[0]) - 1; j >= 0; j--) { + uint64_t v = (uint64_t)q[i] * d[j] + carry; + carry = v >> 32; + v = (uint32_t)v; + v = n[i + j] - v + carry2; + carry2 = v >> 32; // either ~0 or 0 + n[i + j] = v; + } + // fixup if carry2 != 0 + } + // now remainder is in n and quotient is in q +} +``` -- 2.30.2