in knuth algorithm d there is a shift-and-add. this has been discussed before and is worth considering -- for (int i = 0; i <= n; i++) { uint64_t result = (((uint64_t)phi[i] << 32) | plo[i]) + carry; uint32_t result_high = result >> 32; if (carry <= 1) result_high++; carry = result_high; un[i + j] = (uint32_t)result; }
(In reply to shriya.sharma from comment #0) > in knuth algorithm d there is a shift-and-add. actually, not really. this is just a convoluted way (when combined with the loop computing phi/plo) of writing a bigint multiply-subtract. I instead used the algorithm in (with #define MADDEDU_SUBFE): https://git.libre-soc.org/?p=libreriscv.git;a=blob;f=openpower/sv/biginteger/divmnu64.c;h=b4bd10659796f36812e67bc22d2814d176813054;hb=6ecafc9cfa1cf13f25fa851d012b20989d770108#l375 the actual code that I use has no shifts and is (converting extraneous bits that setup VL and stuff into comments): # do multiply part # t = 0 # VL = n sv.maddedu *product, *vn, qhat, t # product = vn * qhat # product[n] = t # do subtract part # CA = 1 # no borrow initially # VL = n + 1 # set REMAP to offset RT and RB by j sv.subfe *un, *product, *un # un[j:] -= product if borrowed: # there was a borrow, aka. product was too big # we need to adjust qhat by one and un[j:] to match # qhat -= 1 # CA = 0 # no carry # VL = n # set REMAP to offset RT and RA by j sv.adde *un, *un, *vn # un[j:] += vn # un[j + n] += CA # add last digit
(In reply to Jacob Lifshay from comment #1) > (In reply to shriya.sharma from comment #0) > > in knuth algorithm d there is a shift-and-add. > > actually, not really. that said, shift and add is possibly useful for other things.
(In reply to Jacob Lifshay from comment #2) > (In reply to Jacob Lifshay from comment #1) > > (In reply to shriya.sharma from comment #0) > > > in knuth algorithm d there is a shift-and-add. > > > > actually, not really. ok - it's been a while. > that said, shift and add is possibly useful for other things. yes - i just couldn't quite remember where, i think it was poly1305?