Efficient 64 bit arithmetic

Fabrice Bellard fabrice at bellard.org
Wed Jul 9 03:07:57 PDT 2014


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
>


More information about the es-discuss mailing list