Math.mulx

Fedor Indutny fedor at indutny.com
Wed Jul 2 03:37:15 PDT 2014


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello everyone!

While working on bn.js, I have found one bottleneck in integer
multiplication
which could be solved with introduction of a new Math functions.

In [multiply operation][0] the most expensive part is obviously an integer
multiplication. EcmaScript could operate with 51bit numbers without the
loose of
precision, but the whole thing requires compilers to translate SMIs (small
integers) into a floating point values and operate on them.

Introduction of `Math.mulxHigh` and `Math.mulxLow` with a help of compiler
could
make this limitation go away. Namely, a compiler could coalesce these two
calls
into a one `mulx` instruction, making it possible to implement big numbers
with
a 32 bit limb.

The code sample is following:

    var hi = Math.mulxHigh(a, b);  // High 32 bits of the multiplication
result
    var lo = Math.mulxLow(a, b);  // Low 32 bits of the multiplication
result

And this could be translated to a just:

    movx rax, rbx, rcx

on IA32 platform. On the platforms that do not have a single instruction for
this operation, the resulting code should still be faster, because it could
avoid `integer -> floating point -> integer` conversion.

I'm open to any suggestions. What do you think?

Thank you,
Fedor.

[0]:
https://github.com/indutny/bn.js/blob/95e0623aaa637a3a6a87f9a7b30aafed758aa4eb/lib/bn.js#L590-L599

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJTs+A8AAoJEPsOEJWxeXmZ0O4P/2TmAjLCZ6HwKjPheaAXEXIB
tg3SbRyQNS/he/ZRs+0JkSePKVHlpgg/BBzlSJ4JGnFIEv2zYA/MfKzwrMGhkAXq
1vYSUgm5sAwXZpmsJwEND6Kvb7sAPP19y2eKuJ/FwiHdkJXgEsT+Mz0w3nKwYd04
9g1FHTTn5Z+hnRP/9evGwUCV05cLQaD1VMnlzYfVvRHkGy3coEH0+5HtvSB/bnFA
mkTQV26bimlllIhrE4QWWRPGR3bFq9Ec5kQr10Gm9LGYLgL7D7fBaQNvc+EkTMxE
ELyabtrSwpRxfDlrXHZZPFM7vta9dYFnYnYpd95q904d94U7wG0H5WM6SA30cFdE
J40/IIo5DBbDIHcGxypOvIEjBJvvBFCdKXd8JVYm5BUGowRrNVdWDK0HuurrWYwc
fDVrx1mD45+HBwmtBcvYrN84hDkgyXnZgoxBqUCzL4EBK0bT7dnvZKG7yBP4gUE0
UxptldK4MYSdcsczQcjVoDZ/crcgHMoW4vpK8t++Rpmqic0p786ijCjH3HMppyoO
LcPqGgWE2CyIm/VwS6omEoo5s9yYpDfpHuZ8ZnJp0/lD2s7DgQWtZsvveS4jGx4p
K5LrLUul8r6ydnkRLQCUmH23IwpoeA+NOZF06mIyMcObXrv8Gknp1WIA4/kt55Fs
xzciHPFWb/vavbGCEu+7
=9xHZ
-----END PGP SIGNATURE-----
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20140702/939a8dde/attachment.html>


More information about the es-discuss mailing list