javascriptc++mathmultiplicationinteger-division

Why is there a loop in the JavaScript division as multiplication code?


I got the Js code below from an archive of Hacker's Delight (view the source)

The code takes in a value (such as 7) and spits out a magic number to multiply with. Then you bitshift to get the results. I don't remember assembly or any math so I'm sure I'm wrong but I can't find the reason why I'm wrong

From my understanding you could get a magic number by writing ceil(1/divide * 1<<32) (or <<64 for 64-bit values, but you'd need bigger ints). If you multiply an integer with imul you'd get the result in one register and the remainder in another. The result register is magically the correct result of a division with this magic number from my formula

I wrote some C++ code to show what I mean. However I only tested with the values below. It seems correct

#include <cstdio>
#include <cassert>
int main(int argc, char *argv[])
{
    auto test_divisor = 7;
    auto test_value = 43;
    auto a = test_value*test_divisor;
    auto b = a-1; //One less test

    auto magic = (1ULL<<32)/test_divisor;
    if (((1ULL<<32)%test_divisor) != 0) {
        magic++; //Round up
    }
    auto answer1 = (a*magic) >> 32;
    auto answer2 = (b*magic) >> 32;
    assert(answer1 == test_value);
    assert(answer2 == test_value-1);
    printf("%lld %lld\n", answer1, answer2);
}

The JS code from hackers delight has a loop and more and I was wondering, why? Am I missing something? What values can I use to get an incorrect result that the JS code would get correctly? I'm not very good at math so I didn't understand any of the comments

var two31 = 0x80000000
var two32 = 0x100000000
function magic_signed(d) { with(Math) {
    if (d >= two31) d = d - two32// Treat large positive as short for negative.
    var ad = abs(d)
    var t = two31 + (d >>> 31)
    var anc = t - 1 - t%ad       // Absolute value of nc.
    var p = 31                   // Init p.
    var q1 = floor(two31/anc)    // Init q1 = 2**p/|nc|.
    var r1 = two31 - q1*anc      // Init r1 = rem(2**p, |nc|).
    var q2 = floor(two31/ad)     // Init q2 = 2**p/|d|.
    var r2 = two31 - q2*ad       // Init r2 = rem(2**p, |d|).
    do {
        p = p + 1;
        q1 = 2*q1;                // Update q1 = 2**p/|nc|.
        r1 = 2*r1;                // Update r1 = rem(2**p, |nc|.
        if (r1 >= anc) {          // (Must be an unsigned
            q1 = q1 + 1;           // comparison here).
            r1 = r1 - anc;}
        q2 = 2*q2;                // Update q2 = 2**p/|d|.
        r2 = 2*r2;                // Update r2 = rem(2**p, |d|.
        if (r2 >= ad) {           // (Must be an unsigned
            q2 = q2 + 1;           // comparison here).
            r2 = r2 - ad;}
        var delta = ad - r2;
    } while (q1 < delta || (q1 == delta && r1 == 0))

    var mag = q2 + 1
    if (d < 0) mag = two32 - mag // Magic number and
    shift = p - 32               // shift amount to return.
    return mag
}}

byId('subBtn').onclick = function (e) {
    e.preventDefault();
    inputVal = byId('value').value + 0;
    byId('result').innerText = "" + magic_signed(inputVal);
}

function byId(x) {
    return document.getElementById(x);
}
<h1>Hacker's Delight Magic Number</h1>
<form name="magic_number">Value:
    <input id="value">
    <button id='subBtn'>Calculate</button><br>
    <label id="result"></label>
</form>


Solution

  • In the C code:

    auto magic = (1ULL<<32)/test_divisor;
    

    We get an integer value in magic because both (1ULL<<32) & test_divisor are integers.
    The algorithms requires incrementing magic on certain conditions, which is the next conditional statement.

    Now, multiplication also gives integers:

    auto answer1 = (a*magic) >> 32;
    auto answer2 = (b*magic) >> 32;
    

    C CODE is DONE!

    In the JS code:

    All variables are var; no data types!
    No integer division, no integer multiplication!
    Bitwise operations are not easy and not suitable to use in this algorithm. Numeric data is via number & BigInt which are not like C int or unsigned long long.

    Hence the algorithm is using loops to iteratively add and compare whether "Division & Multiplication" has occurred to within the nearest integer.

    Both versions try to implement the same algorithm. Both "should" give the same answer, but the JS Version is "buggy" & non-standard. While there are many issues with the JS version, I will highlight only 3:

    1. In the loop, while trying to get the best power of 2, we have these two statements:

      p = p + 1;
      q1 = 2*q1;                // Update q1 = 2**p/|nc|.
      

      It is basically incrementing a counter & multiplying a number by 2, which is a left shift in C++. The C++ version will not require this rigmarole.

    2. The while condition has 2 equality comparisons on RHS of ||:

      while (q1 < delta || (q1 == delta && r1 == 0))
      

      But both these will be false in floating-point calculations [[ eg check Math.sqrt(2)*Math.sqrt(0.5) == 1: even though this must be true, it will almost always be false ]] hence the while condition is basically the LHS of ||, because RHS will always be false.

    3. The JS version returns only one variable mag but user is supposed to get (& use) even variable shift which is given by global variable access. Inconsistent & BAD!

    Comparing, we see that the C version is more standard, but the point is to not use auto but use int64_t with known number of bits.