0

How can we divide 2^{128} by an odd number (unsigned 64-bit integer), which is a floor more precisely, without using arbitrary multi-precision arithmetic library?

The problem is even with gcc, 2^{128} cannot be expressed. So I'm considering creating 192-bit integer type. But, I have no idea how to do that (especially subtraction part). I want the result of the floor to be an unsigned number.

user9414424
  • 498
  • 3
  • 15
  • You can create your data type based on an array of bytes with a custom `operator/` in which you will define how your bits are operated – Adrien Givry Jul 24 '19 at 15:51
  • 1
    Do you have 128-bit arithmetic or just 64? – Eric Postpischil Jul 24 '19 at 15:57
  • 1
    Possible duplicate of [Calculating pow(a,b) mod n](https://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – Marek R Jul 24 '19 at 15:57
  • If you have 128 bit integers, see Eric's answer. If you do not, then what data type would you intend to store the answer in? Instead of writing your own, use a tried and tested one (it'll save you the work, the debugging and will most likely be faster on top of it all). – Max Langhof Jul 24 '19 at 16:29
  • 1
    I am voting to close this question as unclear because it is missing key information, namely the data type, as Eric Postpischil already mentioned. – L. F. Jul 25 '19 at 10:52

1 Answers1

3

For any odd d > 1, UINT128_MAX / d equals floor(2128/d).

This is because 2128/d must have a remainder, as the only factors of 2128 are powers of two (including 1), so the odd d (excluding 1) cannot be a divisor. Therefore, 2128/d and (2128−1)/d have the same integral quotient, and UINT128_MAX is 2128−1.

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312