Reversing a multiplication in 64 bit arithmetic

Question

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?

score 4 · Accepted Answer · edited May 23 '17 at 12:22

4

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

edited May 23 '17 at 12:22

Community

1
1

answered Sep 20 '15 at 19:53

hiro protagonist

44,693
14
86
111

Pardon my ignorance but I'm not sure how to interpret that. How can I implement it in Python? – Juicy Sep 20 '15 at 19:55
1

sure! the pseudo-code on wikipedia is close to python; otherwise try this: http://stackoverflow.com/questions/12519535/extended-euclidean-algorithm-and-the-concept-of-multiplicative-inverse – hiro protagonist Sep 20 '15 at 19:59
1

Isn't it Z/2^32Z though? Because of the masking? – harold Sep 21 '15 at 06:54
you are correct! this `FF` sequence seemed awfully short! oh. i'll have to check out your blog! – hiro protagonist Sep 21 '15 at 07:58

alexgolec · Answer 2 · 2015-09-20T19:51:17.887

0

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

edited Sep 20 '15 at 19:51

answered Sep 20 '15 at 19:45

alexgolec

26,898
33
107
159

No information is lost on multiplication by 33 (or any other odd number); see @hiro-protagonist's answer. – Don Hatch Jul 24 '19 at 01:20

score -2 · Answer 3 · answered Sep 20 '15 at 19:47

-2

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.

answered Sep 20 '15 at 19:47

Andrew Huang

132
5

No information is lost on multiplication by 33 (or any other odd number); see @hiro-protagonist's answer. – Don Hatch Jul 24 '19 at 01:20

Reversing a multiplication in 64 bit arithmetic

3 Answers3