Efficient 64 bit arithmetic

Vyacheslav Egorov vegorov at google.com
Wed Jul 9 03:44:30 PDT 2014


> Note: my proposal is not limited to 64 bit operations. It can be used to
efficiently implement arbitrary precision arithmetic.

True, it is easier to arrive to the efficient and clear code with lowered
representation. With (lo, hi)-result API compiler will have to figure more
things out on it's own. Though I don't see any issues as both APIs are
strictly of the same power:

Math.imuluh(a, b) === Math.u64mul(a, 0, b, 0).hi

But then again the question would be: does it make sense to let people
implement say bigints in pure JavaScript or better give them bigints as
part of the language.

> If you really want such an API, it is not worth proposing a lowered
version because division is slow anyway

This is also a fair point. But having inconsistent APIs is very weird if
you ask me.





// Vyacheslav Egorov


On Wed, Jul 9, 2014 at 12:07 PM, Fabrice Bellard <fabrice at bellard.org>
wrote:

> Note: my proposal is not limited to 64 bit operations. It can be used to
> efficiently implement arbitrary precision arithmetic.
>
> 64 bit integer division and remainder are less critical than the other
> operations because they are seldom used and slow anyway. Moreover, it is
> more difficult to define them because they are undefined cases (division by
> zero and overflow). So not proposing a specific API for them can be
> acceptable.
>
> If you really want such an API, it is not worth proposing a lowered
> version because division is slow anyway. You can define for example:
>
> {quo_lo:q0, quo_hi:q1, rem_lo:r0, rem_hi:r1 } = Math.idiv64(lo0, hi0, lo1,
> hi1)
>
> for signed 64 bit division and
>
> {quo_lo:q0, quo_hi:q1, rem_lo:r0, rem_hi:r1 } = Math.idivu64(lo0, hi0,
> lo1, hi1)
>
> for unsigned 64 bit division. In case of division by zero or overflow,
> null is returned. Instead of returning an object, you can use a
> preallocated Int32Array to return the 4 32 bit numbers but you also need to
> return a boolean to indicate the error cases.
>
> Fabrice.
>
>
> On 07/09/14 11:36, Vyacheslav Egorov wrote:
>
>> Hi Fabrice,
>>
>> The main reason why I was proposing (hi, lo)-pair based API instead of
>> lower version is to
>>
>> a) avoid necessity writing low-level looking code in the high-level
>> language which is JS;
>>
>> b) avoid pattern matching in the JS code to recognize construction
>> built out of low-level 32-bit counterparts.
>>
>> This is too much like first writing 32-bit assembly and then trying to
>> pattern match it to emit 64-bit one. If we are starting to add
>> low-level intrisics like that maybe it's time to actually agree that
>> we want a bytecode with a full range of numeric types and operations?
>>
>> Math.H part of the proposal was an awful hack though in attempt to
>> avoid degrading polyfill performance while keeping API high-level and
>> "atomic".
>>
>> To be honest I think the actual API for high level language like JS
>> should be either value-object or pair based.
>>
>> Given that ES6 defines typed-arrays it might be possible to make API
>> based on that:
>>
>> var a = new Int32Array(2),
>>        b = new Int32Array(2),
>>        c = new Int32Array(2);
>> Math.div64(c, a, b);
>>
>> But again it has bad performance unless you pool both a, b, c in the
>> right way (pooling is good for unoptimized code, but pooling globally
>> is bad for optimized code).
>>
>> Lowered version
>>
>> cl = Math.div64l(al, ah, bl, bh);
>> ch = Math.div64h(al, ah, bl, bh);
>>
>> should perform well (no allocations, potentially only some boxing if
>> engine requires that) and can be assembled into a single instruction
>> by the optimizer... but this just looks slightly bizarre.
>>
>> // Vyacheslav Egorov
>> _______________________________________________
>> es-discuss mailing list
>> es-discuss at mozilla.org
>> https://mail.mozilla.org/listinfo/es-discuss
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20140709/aaa0c2c6/attachment.html>


More information about the es-discuss mailing list