Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
integer multiplication modulo 2^32

Subject: integer multiplication modulo 2^32

From: Jennifer Faggi Renault

Date: 21 Apr, 2010 21:49:05

Message: 1 of 5

Hi all,
i have a variabla B= '2A66311C'
so to calculate mod(B*(2*B + 1),2^32)
i did Bc=hex2dec(B,8) then i tried:
t= mod(Bc*(2*Bc + 1),2^32) but, i get after conversion into hex
t='E1DDA700' instead of t='E1DDA73C' wich i should find !!

So, can anyone help me to find my error and fix it please??

Subject: integer multiplication modulo 2^32

From: Roger Stafford

Date: 21 Apr, 2010 22:17:04

Message: 2 of 5

"Jennifer Faggi Renault" <asma_192@live.fr> wrote in message <hqnrsh$qjg$1@fred.mathworks.com>...
> Hi all,
> i have a variabla B= '2A66311C'
> so to calculate mod(B*(2*B + 1),2^32)
> i did Bc=hex2dec(B,8) then i tried:
> t= mod(Bc*(2*Bc + 1),2^32) but, i get after conversion into hex
> t='E1DDA700' instead of t='E1DDA73C' wich i should find !!
>
> So, can anyone help me to find my error and fix it please??

  You are expecting too much of double precision floating point's 53 bits of significand accuracy. Notice that your error lies in the least six bits of the desired answer. You need to somehow have about 61 or so bits of accuracy for your calculations or to divide up the hex number into two parts and carry out the desired operations on it in an appropriate piecemeal fashion. There is a way to do the latter, even though it is rather annoying. I sometimes have to do it on my hand calculator in hex mode with its limit of eight hex characters.

Roger Stafford

Subject: integer multiplication modulo 2^32

From: Roger Stafford

Date: 21 Apr, 2010 23:41:05

Message: 3 of 5

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hqnth0$o0d$1@fred.mathworks.com>...
> You are expecting too much of double precision floating point's 53 bits of significand accuracy. Notice that your error lies in the least six bits of the desired answer. You need to somehow have about 61 or so bits of accuracy for your calculations or to divide up the hex number into two parts and carry out the desired operations on it in an appropriate piecemeal fashion. There is a way to do the latter, even though it is rather annoying. I sometimes have to do it on my hand calculator in hex mode with its limit of eight hex characters.
>
> Roger Stafford

  Here is an example of doing that "piecemeal" method I mentioned. If you had to do many multiplications like this, you could write this as a function.

B = '2A66311C';
Bc = hex2dec(B);
B1 = mod(Bc,2^16);
B2 = (Bc-B1)/2^16;
C = 2*Bc+1;
C1 = mod(C,2^16);
C2 = (C-C1)/2^16;
D = mod(B1*C2+B2*C1,2^16);
E = mod(D*2^16+B1*C1,2^32);
e = dec2hex(E)
ans = 'E1DDA73C'

It doesn't demand much more than 32-bit accuracy of the double calculations.

Roger Stafford

Subject: integer multiplication modulo 2^32

From: Walter Roberson

Date: 22 Apr, 2010 00:28:09

Message: 4 of 5

Roger Stafford wrote:
> "Jennifer Faggi Renault" <asma_192@live.fr> wrote in message
> <hqnrsh$qjg$1@fred.mathworks.com>...

>> i have a variabla B= '2A66311C'
>> so to calculate mod(B*(2*B + 1),2^32)
>> i did Bc=hex2dec(B,8) then i tried:
>> t= mod(Bc*(2*Bc + 1),2^32) but, i get after conversion into hex
>> t='E1DDA700' instead of t='E1DDA73C' wich i should find !!

> You are expecting too much of double precision floating point's 53 bits
> of significand accuracy. Notice that your error lies in the least six
> bits of the desired answer. You need to somehow have about 61 or so
> bits of accuracy for your calculations or to divide up the hex number
> into two parts and carry out the desired operations on it in an
> appropriate piecemeal fashion.

In addition to Roger's entirely correct analysis, note that there is a bug in
fprintf that cause the lower bits to be lost when %lx format is used with uint64:

 >> num2hex(.9)
ans =
3feccccccccccccd
 >> fprintf('%lx\n', typecast(.9,'uint64'))
3feccccccccccc00

This bug does not, however, affect any of the routines that have 'hex' in
their name, such as hex2dec or num2hex.

Subject: integer multiplication modulo 2^32

From: Bruno Luong

Date: 22 Apr, 2010 06:55:20

Message: 5 of 5

There is a tool on FEX allows to do operation on uint64/int64
http://www.mathworks.com/matlabcentral/fileexchange/24725-int64-arithmetic-in-matlab

>> B = '2A66311C';
>> Bc = uint64(hex2dec(B));
>> dec2hex(mod(Bc*(2*Bc + 1),2^32))

ans =

E1DDA73C

% Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us