Multiplication overflow in Matrix Encoding

January 14, 2008

I just noticed an exchange Help Implementing Nested Invervals using Maxtrix Encoding which never showed up in Google groups and, therefore, left unanswered. There Steven Johnston pointed out that multiplication of 32 bit integers (which is used when comparing if one tree node is a descendant of the other)would normally produce 64 bit integer. Then, what is the point using slightly more efficient Matrix encoding/Nested Intervals with continued fractions if integer multiplication overflow seems to render the whole method invalid? Well, the fix is straightforward, although not pretty. To reliably evaluate if

descendant.a11*node.a21-descendant.a11*node.a22 <=

one have to introduce a user defined function:

function isDescendant( da11 integer, na21 integer, da11 integer, ....)

Within the function implementation chop each 32 bit function argument into two 16 bit chunks. When multiplying the numbers, use the formula:

(A*216 + B)*(C*216 + D) = A*C*232 + (A*D+B*C)*216 + B*D

I understand the frustration of people who have to spend their time to workaround snags like this, but this is not really an interesting issue. More exciting question may be what if we change the ordinary addition&multiplication algebra (+,*) into tropical semiring (min,+)? There is no multiplication, so no matter what calculations we do the overflow is impossible. Unfortunately this idea don’t work:-(


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: