Multiplying __int64's

Question

Can someone explain to me (in detail) how to multiply two __int64 objs and check if the result will fit in __int64.

Note: Do not use any compiler or processor dependent routines.

Technically, signed integer overflow (or underflow) is undefined behavior, so you're going to have to make an assumption about the underlying platform if you want to define the behavior. — GManNickG, Apr 30 '11 at 08:33
Possibly related: http://stackoverflow.com/questions/1131833/how-do-you-multiply-two-64-bit-numbers-in-x86-assembler-closed http://stackoverflow.com/questions/87771/how-can-i-multiply-two-64bit-numbers-using-x86-assembly-language — rwong, Apr 30 '11 at 08:36
I was surprised that no one has provided an assembler solution so far, as here it would just be a matter of testing the overflow bit after the multiplication (even though it would be heavily architecture dependent, of course). Unfortunately I'm rusty on assembler and don't know Visual C++'s assembler syntax, but [this answer to a question @rwong linked to](http://stackoverflow.com/questions/1131833/how-do-you-multiply-two-64-bit-numbers-in-x86-assembler/1131905#1131905) does the 64-bit multiplication for x86_64... all that's missing is the test for the overflow flag. — DarkDust, Apr 30 '11 at 08:42
@DarkDust: no it's not "just" an overflow flag (which would be processor-dependent). I was originally planning to argue that it is necessary to get the full 128-bit result, and then test that the top 64 bits are all zero. However, @Mihran's new solution (checking inverse relation by division) seems to be a better way. — rwong, Apr 30 '11 at 08:46

Mihran Hovsepyan · Answer 1 · 2011-04-30T08:55:49.677

4

not assuming a and b are positive:

__int64 a,b;
//...
__int64  tmp_result = abs(a) * abs(b) ;
if (
    ( a && b ) &&
    (
     ( tmp_result < abs(a) || tmp_result < abs(b) ) ||
     ( tmp_result / abs(a) != abs(b)) ||
     ( a == TYPE_MIN && b != 1) ||
     ( b == TYPE_MIN && a != 1)
    )
   )
   std::cout << "overflow";
__int64 result = a * b;

EDIT: Adding corner cases to code.

EDIT: In my opinion just ( a && a * b / a != b) is enough.

edited Apr 30 '11 at 08:55

answered Apr 30 '11 at 08:24

Mihran Hovsepyan

10,810
14
61
111

@Mihran what will happen when you do abs on TYPE_MIN? – There is nothing we can do Apr 30 '11 at 08:26
1

It doesn't work, consider `a = b = 1+2^33`, then `a*b = 1 + 2^34 + 2^66 = 1 + 1^34`, it overflowed, but you don't detect it. – Yakov Galka Apr 30 '11 at 08:29
@There is nothing we can do @ybungalobill both bugs are fixed. – Mihran Hovsepyan Apr 30 '11 at 08:36
also need to catch the `a == 0 || b == 0` case before your `if` statement. – rwong Apr 30 '11 at 08:39
@Mihran thanks for your answer. Not tested yet but assuming that it is correct (and I **really** hope it is), what about LeBlanc's SafeInt's way of doing long multiplication? This guy went into such an effort to do it and you did it if less than 5 lines really. Congrats! (but only if it's fully workable with all corner cases covered) – There is nothing we can do Apr 30 '11 at 09:11
Thank you @There is nothing we can do! I think it is not difficult to proof that my last condition `( a && a * b / a != b)` is what you want. – Mihran Hovsepyan Apr 30 '11 at 09:21
@Mihran I've deleted my last comment because it wasn't true what I've said there. – There is nothing we can do Apr 30 '11 at 09:22
@Mihran you mean just ( a && a * b / a != b) instead of everything else? – There is nothing we can do Apr 30 '11 at 09:23
@There is nothing we can do. If TYPE_MIN is -1 => TYPE is one bit type => ther is no 1 in valueset of that type only 0 and -1. So the program will give correct answer. – Mihran Hovsepyan Apr 30 '11 at 09:23
`@Mihran you mean just ( a && a * b / a != b) instead of everything else?` Yes. – Mihran Hovsepyan Apr 30 '11 at 09:25
@Mihran why not just (a * b / a != b)? – There is nothing we can do Apr 30 '11 at 09:26
@There is nothing we can do. Because we can't divide by 0. – Mihran Hovsepyan Apr 30 '11 at 09:27
@Mihran yes, but if I were to check before if one of them is zero and immediately returned zero if it is (for this is about multiplication and multiplying by zero is legal) then I would not have to check second time, am I right? – There is nothing we can do Apr 30 '11 at 09:30
@Mihran with your last way (a && a * b / a != b) when multiplying signed char == SCHAR_MIN by -1 gives **incorrect** result but the first ver seems to be working. – There is nothing we can do Apr 30 '11 at 09:35
@Mihran but then **your first ver is incorrect** for lhs = std::numeric_limits<__int64>::max() + 1 and rhs = -1; – There is nothing we can do Apr 30 '11 at 09:45
@There is nothing we can do. I have tested this and strang thing happens. Yes multiplying SCHAR_MIN by -1 gives **incorrect** result, but If I assigned it to some value and only after divided to `a` (i.e. `signed char x = a * b;` `if(x / a != b)`) it gives correct result. – Mihran Hovsepyan Apr 30 '11 at 09:47
`@Mihran but then your first ver is incorrect for lhs = std::numeric_limits<__int64>::max() + 1 and rhs = -1; ` @There is nothing we can do in this case `lhs` becomes equal to `MIN_VALUE` of `__int64` so the problem is same as above and will be solved in such way. – Mihran Hovsepyan Apr 30 '11 at 09:52
@Mihran well then you have uac and int conv. But the point is that it doesn't work as it should. The same if you have lhs = TYPE_MAX + 1 and rhs = -1. **it doesn't have to be __int64, int is enough to brake your code** I've edited the last sentence from signed char to int – There is nothing we can do Apr 30 '11 at 09:52
@There is nothing we can do. I have already answered to this question. `TYPE_MAX + 1 == TYPE_MIN`. And for case `lhs = TYPE_MIN` `rhs = -1` both codes work. – Mihran Hovsepyan Apr 30 '11 at 09:59
@there is nothing we can de. Take a look to question http://stackoverflow.com/questions/5841000/whats-the-problem You should store `a * b` in seperate variable. – Mihran Hovsepyan Apr 30 '11 at 10:06
@Mihran fair enough, I'm going to test this code for next few hours and hopefuly this will do the trick. Thanks – There is nothing we can do Apr 30 '11 at 10:12
@Mihran, @There: I have proven that `(a && a * b / a != b)` is correct, for 2's-complement at least. I simply scaled the problem down to the 16-bit version, and looped over all possible input combinations. I guess I could prove it for other number representations as well, by emulating their overflow behaviour. Once I've done that, then I'll give this answer a +1. – Oliver Charlesworth Apr 30 '11 at 12:24
@Oli that's great news. But in the light of this, why on earth LeBlanc tried to reinvent the wheel in his SafeInt class? I mean his code is so lengthy that if Mihran's solution is **correct**, which mean that it works on any type I'm going to say that it is far better than LeBlanc's. What's your opinion? – There is nothing we can do Apr 30 '11 at 16:03
@There: I'm not sure what solution you're referring to (link?), but I can imagine. The answer could well be that it's faster than doing a 64-bit divide. – Oliver Charlesworth Apr 30 '11 at 16:05
@Oli google: "SafeInt, LeBlanc". I don't see how his could be faster, this solution (Mihran's) doesn't depend on any particular type at all, and is two freaking lines. Check his solution and you see how many lines "his" method takes up. – There is nothing we can do Apr 30 '11 at 16:13
@There: That header has an awful lot of stuff in it. Could you point me at the relevant function or whatever? – Oliver Charlesworth Apr 30 '11 at 16:18
@There: Anyway, either way, a 64-bit divide is probably sloooow. You could try profiling to find out which is faster? – Oliver Charlesworth Apr 30 '11 at 16:49
@Oli we are talking here about multiplying so my advice for you is to use ctrl+f in VS and type "multiply". Believe me if I could I would do it for you. First you cannot deduce for yourself when I talk about safeint class:"why on earth LeBlanc tried to reinvent the wheel in his SafeInt class" and you ask me for a link now you can't be bothered to look through this file to find relevant info. It took me less than 30 just now to find it. Oli you know what? Don't waste my time! – There is nothing we can do May 01 '11 at 09:28
@There: Why always with knee-jerk reaction? Believe me, I did do some cursory searches, but quickly gave up because it's very complex template-based code. I would've assumed you'd be interested in investing some time in this, since it was you that asked the question (whereas I'm spending time on this out of the goodness of my heart...). My suggestion is that rather than guessing which is faster by inspection, you profile them. – Oliver Charlesworth May 01 '11 at 11:08
@Oli I tell you why "always with knee-jerk reaction", if you would tell me what you've said in your last comment I would be more than happy to give you the exact line number in the file, but you didn't. And what about "why on earth LeBlanc tried to reinvent the wheel in his SafeInt class" and not being able to deduce what I'm talking about? And as for profiler? Do you know any good for C++? I've asked months ago on SO about it and what did I got in response? And don't tell me that you're doing this out of the goodness of your heart - you have some reason for doing so (not necessarily material) – There is nothing we can do May 01 '11 at 13:13
@Oli continue but non the less there is a reason behind it (Whatever it may be there is always a reason). – There is nothing we can do May 01 '11 at 13:17
@There: I didn't know who LeBlanc was; I had assumed you were referring to a solution someone had posted as an answer to one of the linked-to questions here on SO. Please, in future, don't always assume that people will know *precisely* what you're talking about; it doesn't hurt to simply provide a link. – Oliver Charlesworth May 01 '11 at 13:19
@There: You don't necessarily need a full-blown profiler. You can just run, say, a million iterations on random input data, and time the result (make sure that you're using the highest compiler optimization settings). – Oliver Charlesworth May 01 '11 at 13:20
@Oli fair enough, I might be to harsh, but seriously sometimes on SO I'm dealing with such geniuses that I'm loosing my patience. http://stackoverflow.com/questions/2851526/how-do-i-use-a-profiler, read that (skim through really) and decide for yourself if any of those links would be of any use to me. I'm asking about profiler for C++ code and none of those "geniuses" seems to mind that. – There is nothing we can do May 01 '11 at 13:25

Multiplying __int64's

1 Answers1

Linked