f



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

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?
0
Jeff
5/2/2009 9:49:43 PM
comp.lang.javascript 38370 articles. 2 followers. javascript4 (1315) is leader. Post Follow

6 Replies
1279 Views

Similar Articles

[PageSpeed] 47

"Jeff.M" <Mott.Jeff@gmail.com> writes:

> 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
-- 
Lasse Reichstein Holst Nielsen
 'Javascript frameworks is a disruptive technology'
  
0
Lasse
5/2/2009 10:54:18 PM
On May 2, 3:54=A0pm, Lasse Reichstein Nielsen <lrn.unr...@gmail.com>
wrote:
> "Jeff.M" <Mott.J...@gmail.com> writes:
> > 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) {
> =A0 n =3D n | 0;
> =A0 m =3D m | 0;
> =A0 var nlo =3D n & 0xffff;
> =A0 var nhi =3D n >> 16; // Sign extending.
> =A0 var res =3D ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
> =A0 return res;
>
> }
>
> (NOT tested throughly!)
> /L
> --
> Lasse Reichstein Holst Nielsen
> =A0'Javascript frameworks is a disruptive technology'

Beautiful. Thanks.
0
Jeff
5/2/2009 11:19:01 PM
In comp.lang.javascript message <4ow36rqd.fsf@gmail.com>, Sun, 3 May
2009 00:54:18, Lasse Reichstein Nielsen <lrn.unread@gmail.com> posted:
>"Jeff.M" <Mott.Jeff@gmail.com> writes:
>
>> 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!)

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.

-- 
 (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk  Turnpike v6.05  IE 7.
 Web  <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
 I find MiniTrue useful for viewing/searching/altering files, at a DOS prompt;
 free, DOS/Win/UNIX, <URL:http://www.idiotsdelight.net/minitrue/> unsupported.
0
Dr
5/3/2009 2:19:07 PM
Dr J R Stockton <reply0918@merlyn.demon.co.uk> writes:

> 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
-- 
Lasse Reichstein Holst Nielsen
 'Javascript frameworks is a disruptive technology'
  
0
Lasse
5/3/2009 8:57:31 PM
In comp.lang.javascript message <skjlhpl0.fsf@gmail.com>, Sun, 3 May
2009 22:57:31, Lasse Reichstein Nielsen <lrn.unread@gmail.com> posted:
>
>(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?

-- 
 (c) John Stockton, Surrey, UK.  ?@merlyn.demon.co.uk   Turnpike v6.05   MIME.
 Web  <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
 Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
 Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)
0
Dr
5/4/2009 4:13:24 PM
Dr J R Stockton <reply0919@merlyn.demon.co.uk> writes:

> 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
-- 
Lasse Reichstein Holst Nielsen
 'Javascript frameworks is a disruptive technology'
  
0
Lasse
5/4/2009 9:21:47 PM
Reply: