CODEWITHSUNDEEP
pythoninteger64-bitdivisionmultiplication
Juicy
Juicy

Reputation: 12520

Reversing a multiplication in 64 bit arithmetic

I'm trying to do some multiplications and divisions with 64 bit integers. I want my results to have 64 bit, any overflow should be truncated. I've managed to get it working with multiplications:

z = 0xed5c6911
y = 0xFFFFFFFF & (z * 33)

print hex(z)
print hex(y)

This outputs:

0xed5c6911
0x98e98b31

as expected.

I would like to reverse this now:

z = 0xFFFFFFFF & (y / 33)
print hex(z)

I would expect 0xed5c6911, the original value of z, but I am getting 0x4a23a85.

How can I reverse the operation done in the first snippet and retrieve the original value of z from y?

Upvotes: 1

Views: 724

Answers (3)

hiro protagonist
hiro protagonist

Reputation: 46889

update: after comment by harold: your mask is only 32 bit - in oder to mask 64 bit you'd need to mask all your integers with & 0xFFFFFFFFFFFFFFFF.

all that follows is for 32-bit:

it is possible to reverse the operation: by truncating to 32 bits you are effectively doing calculations in the integer ring Z/2^32 Z. 33 does have a modular multiplicative inverse in there:

1/33 = 0x3e0f83e1  mod  2^32

so for any 32-bit number you can reverse the multiplication by 33 by multipliying with the number above (and truncating to 32-bit).

you would find the inverse by using the extended euclidean algorithm. mathematically this in the domain of number theory.

note that only the odd numbers in this ring have an inverse (2 is the only prime factor of 2^32).

for 64 bit the inverse of 33 is:

1/33 = 0x0f83e0f83e0f83e1  mod  2^64

Upvotes: 4

alexgolec
alexgolec

Reputation: 28252

This operation is irreversible. When you multiply z by 33, you're pushing the uppermost 64th bit over the 64 bit limit and destroying information by overflowing.

You can see the value of 0xed5c6911 in binary using google.

In other words, you need to use a datatype that's wider than 64 bits to perform this operation. For instance, you can use long:

z = long(0xed5c6911)
y = long(0xFFFFFFFFFFFF) & (z * 33) # Note the added F's
print hex(z)  # 0xed5c6911L
print hex(y)  # 0x1e98e98b31L

Using long you can reverse this operation:

z = 0xFFFFFFFFFFFF & (y / 33) # Again, note the added F's
print hex(z) # 0xed5c6911L

Upvotes: 0

Andrew Huang
Andrew Huang

Reputation: 132

You won't be able to retrieve the original value of z from y.

When you truncate the multiplication of (z * 33) in your first example, you are losing information - in this case the upper bits. Then when you do the division, you are dividing a different value then (z * 33) and therefore wont be able to recover z.

In order to actually get z back, you need to store some additional information - the easiest way is by using a data type with more bits.

Upvotes: -2

Related Questions