Given 64-bit unsigned integer n and 0 <= k <= 63, can floor(n/(1 + 2^-k)) be computed more quickly than by general integer division?
Depends rather on how fast your division and how large k --- eg. n/(1 + 2^-k) = n - n 2^-k + n 2^-2k - ... costs [63/k] logical shifts, ignoring final tweaking. WFL On 4/22/17, David Wilson <davidwwilson@comcast.net> wrote:
Given 64-bit unsigned integer n and 0 <= k <= 63, can floor(n/(1 + 2^-k)) be computed more quickly than by general integer division?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This one may help: Torbj\"{o}rn Granlund, Peter L.\ Montgomery: {Division by Invariant Integers using Multiplication}, SIGPLAN Notices, vol.~29, pp.~61-72, (June-1994). http://gmplib.org/~tege/ * David Wilson <davidwwilson@comcast.net> [Apr 22. 2017 13:08]:
Given 64-bit unsigned integer n and 0 <= k <= 63, can floor(n/(1 + 2^-k)) be computed more quickly than by general integer division?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
David Wilson -
Fred Lunnon -
Joerg Arndt