32-bit Number * 32-bit Number = 64-bit result

J

Jeff.M

I need to do multiplication that mirrors how C handles integer
multiplication. That is, one 32-bit number times another 32-bit number
equals the least significant 32-bits of the 64-bit result.

In theory, I could mimic that behavior like so:

(x * x) & 0xFFFFFFFF

But this doesn't work quite right because the initial multiplication
can produce such a large result that JavaScript looses some precision.

Any thoughts? Ideas?
 
L

Lasse Reichstein Nielsen

Jeff.M said:
I need to do multiplication that mirrors how C handles integer
multiplication. That is, one 32-bit number times another 32-bit number
equals the least significant 32-bits of the 64-bit result.

In theory, I could mimic that behavior like so:

(x * x) & 0xFFFFFFFF


or (x * x) | 0, since binary operations truncates to 32 bits ...
But this doesn't work quite right because the initial multiplication
can produce such a large result that JavaScript looses some precision.

That is a problem, yes.
Any thoughts? Ideas?

Split the numbers into smaller parts and do the multiplication yourself.
Something like:

function mul32(n, m) {
n = n | 0;
m = m | 0;
var nlo = n & 0xffff;
var nhi = n >> 16; // Sign extending.
var res = ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
return res;
}

(NOT tested throughly!)
/L
 
J

Jeff.M

or (x * x) | 0, since binary operations truncates to 32 bits ...


That is a problem, yes.


Split the numbers into smaller parts and do the multiplication yourself.
Something like:

function mul32(n, m) {
  n = n | 0;
  m = m | 0;
  var nlo = n & 0xffff;
  var nhi = n >> 16; // Sign extending.
  var res = ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
  return res;

}

(NOT tested throughly!)
/L

Beautiful. Thanks.
 
D

Dr J R Stockton

Sun said:
or (x * x) | 0, since binary operations truncates to 32 bits ...


That is a problem, yes.


Split the numbers into smaller parts and do the multiplication yourself.
Something like:

function mul32(n, m) {
n = n | 0;
m = m | 0;
var nlo = n & 0xffff;
var nhi = n >> 16; // Sign extending.
var res = ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
return res;
}

(NOT tested throughly!)

More un-thoroughly tested :

function mult32(n, m) {
n |= 0
m |= 0
var nlo = n & 0xffff
var nhi = n - nlo
return ( (nhi * m | 0) + (nlo * m | 0) ) | 0
}

The outermost parentheses may aid the reader.

It has been thoroughly tested for mult32(x, y) == mult32(y, x) :

for (j=0 ; j<1e5 ; j++) {
x = Math.floor((Math.random()*2-1)*0x100000000)
y = Math.floor((Math.random()*2-1)*0x100000000)
a = mult32(x, y)
b = mult32(y, x)
if (a!=b) { alert([j, a, b]) ; break }
}

Yours passes the same test; and using
a = mul32(x, y)
b = mult32(y, x)
also passes.

In FF 3.0.10, using js-quick.htm, mine is slightly faster.
 
L

Lasse Reichstein Nielsen

Dr J R Stockton said:
More un-thoroughly tested :

function mult32(n, m) {
n |= 0
m |= 0
var nlo = n & 0xffff
var nhi = n - nlo
return ( (nhi * m | 0) + (nlo * m | 0) ) | 0
}

That's well spotted - there's no need to make numbers small, it only
matters to keep the number of significant digits below 53.
With that in mind, the last line can be reduced (slightly) to:
return ( (nhi * m | 0) + (nlo * m) ) | 0

(the first summand has 32 bits of precission, the second 48, and they
overlap, so it should be fine).

/L
 
D

Dr J R Stockton

Sun said:
(the first summand has 32 bits of precission, the second 48, and they
overlap, so it should be fine).

Good.

The FAQ apparently contains no mention of 32-bit within JavaScript, and
no instance of the operators | ~ ^ >> >>> << . There're not often asked
about, but they fairly often appear in solutions here.

Using >>>0 seems to be the way to get an unsigned result from a signed
one by apparently adding 2^32 if necessary. That might be wanted by the
OP. The reverse is done by |0 .

I have a page partly about those operators, "JavaScript Uses of
Operators",
<URL:http://www.merlyn.demon.co.uk/js-logic.htm> (I must update it to
answer the question I just asked myself) ... (I did).

<FAQENTRY> Something about 32-bit.
<FAQENTRY> Which parts of JavaScript get no mention in the FAQ?
 
L

Lasse Reichstein Nielsen

Dr J R Stockton said:
Using >>>0 seems to be the way to get an unsigned result from a signed
one by apparently adding 2^32 if necessary. That might be wanted by the
OP. The reverse is done by |0 .

Indeed they do (I never noticed that >>> could be used that way).
The technical explanation is that the algorithms for >>> and | perform
ToUInt32 and ToInt32 on their first operand, and the operation then
returns that as the result.

Genrally, the internal conversions of operators can be very useful
(like prefix "+" which does ToNumber and '+""' which does ToString).

/L
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top