Multiplication of 32 bits numbers in C

Question

2.00/5 (3 votes)

See more:

, +

I am trying two multiply to matrices in C and I cant understand why I get these results...
(I am trying write a program that multiplies two 32 bits numbers to be imported on a system that has only 32 bit registers)

B = [ 15643 54056 -33591
24466 26823 54561
58751 -25563 -13777 ]

I want to do : Btranspose * B

#define LOW_WORD(x)  (((x) << 16) >> 16) 
#define HIGH_WORD(x) ((x) >> 16)
#define ABS(x) (((x) >= 0) ? (x) : -(x))
#define SIGN(x) (((x) >= 0) ? 1 : -1)
#define UNSIGNED_MULT(a, b) \
	(((LOW_WORD(a)  * LOW_WORD(b))  <<  0) + \
  	 ((LOW_WORD((a))  * HIGH_WORD((b))) << 16) + \
     ((HIGH_WORD((a)) * LOW_WORD((b)))  << 16) + \
     ((int64_t)(HIGH_WORD((a)) * HIGH_WORD((b))) << 32))
#define MULT(a, b)	(UNSIGNED_MULT(ABS((a)), ABS((b)))*SIGN((a))*SIGN((b)))

int c,d,k;
int64_t multmatrix[3][3];
int64_t sum64 = 0;
int32_t B, Btranspose;

for ( c = 0 ; c < 3 ; c++ ){
 for ( d = 0 ; d < 3 ; d++ ){
  for ( k = 0 ; k < 3 ; k++ ){
   sum64 = sum64 + MULT(Btranspose[c][k], B[k][d]);
   printf("\nthe MULT for k = %d is: %ld \n", k, MULT(Btranspose[c][k], B[k][d]));
   printf("\nthe sum for k = %d is: %ld \n", k, sum64);
   }
   multmatrix[c][d] = sum64;
   sum64 = 0;
  }
}

My output is below put that is wrong and I notice that the mistake is when is multiplying the 3rd element (58751 * 58751) for k=2.
I think is not overflowing because 58751^2 needs less than 32bits.

CSS

the MULT for k = 0 is: 244703449

the sum for k = 0 is: 244703449

the MULT for k = 1 is: 598585156

the sum for k = 1 is: 843288605

the MULT for k = 2 is: 46036225   // this is WRONG!!!

the sum for k = 2 is: 889324830
.
.
.
.
the MULT for k = 2 is: 189805729

the sum for k = 2 is: 1330739379


multmatrix

889324830   650114833   324678230
650114833   1504730698   -308929574
324678230   -308929574   1330739379

Why is the multiplication of the matrix wrong??
What should I change the above code so that the multiplication of two matrices will be overflow-proof??

Posted 8-Mar-15 9:55am

FranxCDO

Updated 8-Mar-15 10:06am

v3

Add a Solution

Comments

phil.o 8-Mar-15 16:06pm

For a signed 32-bits integer, 58751 * 58751 = -843287295 (the most significant bit is used to denote the sign of the integer; thus, if it is set, it means the number is a negative one; 0x7FFFFFFF = 2147483647, 0x80000000 = -2147483648)

FranxCDO 8-Mar-15 16:19pm

I am not sure that I understand what you are saying. You mean that the result is wrong because my numbers that I multiply are declared signed integers?
even so the previous two calculations are positive as well as the third one(the wrong one); why are they correct?

And why 58751*58751 = -843287295 ?

Thanks phil.o for your time :)

phil.o 8-Mar-15 16:24pm

Because, 58751 * 58751 = (binary) 11001101101111000111010100000001
Most significant bit is set, your number is signed, thus you get a negative value.
That is a typical overflow problem :) Maybe you should try to work with 64 bits integers for your intermediate results instead.

The maximum value you can square and expect it to fit in a 32-bits signed integer is 46340. 46341^2 will overflow and return a negative value.

FranxCDO 8-Mar-15 17:15pm

I tried casting to int64 the intermediate steps but again the result is the same.
OK so please correct me if I am mistaken!
1) You are saying that the multiplication is wrong because the numbers that C is multiplying thinks that are signed and so are treated accordingly.
2)The code above multiplies the absolute values and treats the numbers as unsigned. right? so it should matter if my numbers are signed or not.

Sergey Alexandrovich Kryukov 8-Mar-15 16:27pm

Let me tell you: you are the one who did not understand the above comment. It does not really matter what you are asking about, in this context.
Your problem is solved by doing appropriate debugging and checking up some elementary-mathematics expressions.
—SA

FranxCDO 8-Mar-15 16:56pm

Hey Sergey, if you are referring to me yes I didnt not understand as I am a beginner in this field. I am trying to debug and find the reason for the wrong multiplication. If you want to be more specific to the problem as to how I should debug and fix the algorithm please do. Thank you

Sergey Alexandrovich Kryukov 8-Mar-15 17:14pm

I just wanted to advise you to listen to the words by phil.o more thoroughly, this is the root of your problem. This is me who wanted to tell you "if you want to be more specific to the problem,...". How should you debug? This is done by "hypothesis and confirmation" steps, in a converging manner. Set a break point based on a hypothesis that there is not any problem before you reach this point. Execute to this point and inspect the numbers (create different test data sets which are easy to check up manually). Depending on the result of inspection, move a break point or add another one... But couldn't you figure this idea yourself? This is what all people I know did...
—SA

Afzaal Ahmad Zeeshan 8-Mar-15 18:28pm

Funny, that you, trying to not answer him, did answer him and in a way that even if someone answered him "How to debug an application" wouldn't answer. Now, it is up to him to whether understand this answer of yours, or to think like you're just trying to annoy him. I would have up-voted this comments of yours, but there is just a flagging option here. :D

Sergey Alexandrovich Kryukov 9-Mar-15 1:02am

Thank you; you often say convincing things. :-)
In this case, you convinced me to write a bit more on the topic, this time, in a formal answer post...
As to the risk to annoy someone: I would not worry about that too much; the ability to get easily annoyed (so much to even miss something important) is one of the factors of Darwin's natural selection. :-)
—SA

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2015-03-08T18:58:00

FranxCDOFranx wrote:

Hey Sergey, if you are referring to me yes I didn't not understand as I am a beginner in this field. I am trying to debug and find the reason for the wrong multiplication. If you want to be more specific to the problem as to how I should debug and fix the algorithm please do. Thank you.

Being the beginner does not provide an excuse for not debugging; it's just that at first you have to debug more then when you get more experience.

Please see my comment to the question. Let me continue. For most bugs, the process of debugging shows the property of convergence (https://en.wikipedia.org/wiki/Series_%28mathematics%29#Absolute_convergence[^]): after next step, you come closer to figuring out of the bug, which you can do in a finite number (practically, small number of steps). Your task is to build a process of converging debugging step. I already described the idea "hypothesis and confirmation" steps in one of my comments to the question.

Some more hints:

When you stopped at some break point, you can always find where it comes from using Debug window "call stack". It is most useful when you debug incorrect recursion. In all cases, to understand programming in general, you need to understand how call stack works to provide the usual mechanism of calls, parameter passing and return, and also the nature of stack variables and exception.
In "hypothesis" approach, you can temporary disable some or all break point instead of removing them, as it's very likely that eventually you have to start over. In the watch window, you can mark the object with the tag revealing its referential identity (you can do the same in code only using System.Object.ReferenceEquals, but it's more useful during debugging).

Certainly scan all menus of all debug windows and try it all out. It will take minimal time but will be extremely useful and pay off very soon. Look at help pages on all those operations.

—SA

FranxCDO · Accepted Answer · 2015-03-08T22:49:00

As phil.o and Sergey Alexandrovich Kryukov state above, the problem was with the representation of the numbers. The below code works.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>                        
#include <math.h>     

#define LOW_WORD(x)  (((x) << 16) >> 16) 
#define HIGH_WORD(x) ((x) >> 16)
#define ABS(x) (((x) >= 0) ? (x) : -(x))
#define SIGN(x) (((x) >= 0) ? 1 : -1)

#define UNSIGNED_MULT(a, b) \
    (((LOW_WORD(a)  * LOW_WORD(b))  <<  0) + \
     (((int64_t)((LOW_WORD((a)) * HIGH_WORD((b))) + (HIGH_WORD((a)) * LOW_WORD((b))))) << 16) + \
     ((int64_t)(HIGH_WORD((a)) * HIGH_WORD((b))) << 32))

#define MULT(a, b)  (UNSIGNED_MULT(ABS((a)), ABS((b))) * SIGN((a)) * SIGN((b)))


int main()
{
    int c,d,k;
    int64_t multmatrix[3][3];
    int64_t sum64 = 0;
    int32_t Btranspose[3][3] = {{15643, 24466, 58751},
                               {54056, 26823, -25563},
                               {-33591, 54561, -13777}};
    int32_t B[3][3] = {{15643, 54056, -33591},
                      {24466, 26823, 54561},
                      {58751, -25563, -13777}};

    for ( c = 0 ; c < 3 ; c++ ){
        for ( d = 0 ; d < 3 ; d++ ){
            for ( k = 0 ; k < 3 ; k++ ){
                sum64 = sum64 + MULT(Btranspose[c][k], B[k][d]);
                printf("\n the MULT for k = %d is: %ld \n", k, MULT(Btranspose[c][k], B[k][d]));
                printf("\n the sum for k = %d is: %ld \n", k, sum64);
            }
            multmatrix[c][d] = sum64;
            sum64 = 0;
        }
    }       

    printf("\n\n multmatrix \n");
    for( c = 0 ; c < 3; c++ ){
        printf("\n");
        for( d = 0 ; d < 3 ; d++ ){
            printf(" %ld  ", multmatrix[c][d]);
        }
    }
    return 0;
}</math.h></stdbool.h></stdlib.h></stdio.h>

Multiplication of 32 bits numbers in C

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0