Question 169920 in Javascript Question posted in
A very good W3school tutorial can be found here.

Can Javascript solve for a Math.imul() given a known result?

I know the result of a math.imul statement and would like to find one of the solutions that gives the known result. How would I solve for a value of x that works?

Math.imul( x , 2654435761); // the result of this statement is 1447829970
Tags:

2

Answers


  1. 0

    Basically, you want to find x in (x * 2654435761) % 232 == 1447829970

    There’s an iterative solution for (x * y) % 2n == z with known y and z. It is based on the fact that any odd number is coprime with any 2n, which means there has to be exactly 1 solution for any odd y and arbitrary z and n.

    Calculation therefore starts with modulo 21: ((x % 21) * (y % 21)) % 21 == z % 21

    Only 2 solutions for x % 21 exist: 0 and 1. The algorithm picks the one which works. Then goes up by a power of 2, where the second possible solution will be equal to the last one increased by 21. Again, the valid one is picked, and the process proceeds until modulo 232 is reached.

    However, if y is even, then z must have at least as many low-order zero bits as y has. Otherwise, there’s no solution.

    PS: This works in O(n) time with fixed-width integers. But a variation for arbitrary-width integers (such as BigInt) may explode up to O(n3) depending on how multiplication is implemented.

    // seriously though, I have no idea how to call this function!
function unmultiply (y, z) {
    if (y !== (y >>> 0) || z !== (z >>> 0)) {
        // both numbers have to be Uint32
        return NaN;
    }
    let bits = 1;
    while (bits <= 32 && (y & (1 << (bits - 1))) == 0) {
        if (z & (1 << (bits - 1))) {
            // there's no solution
            return NaN;
        }
        bits++;
    }
    let shift = 1, x1 = 0, x2 = 1;
    while (bits < 32) {
        let mask = 0xffffffff >>> (32 - bits);
        if ((Math.imul(x1, y & mask) & mask) == (z & mask)) {
            x2 = x1 | (1 << shift);
        }
        else {
            x1 = x2;
            x2 = x2 | (1 << shift);
        }
        bits++;
        shift++;
    }
    return ((Math.imul(x1, y) >>> 0) == z)
        ? x1 >>> 0
        : x2 >>> 0;
}

let testsSucceeded = 0;
let testsFailed = 0;

function testYZ (y, z) {
    let x = unmultiply(y, z);
    let checkZ = Math.imul(x, y) >>> 0;
    if (checkZ === z) {
        testsSucceeded++;
    }
    else {
        testsFailed++;
    }
    console.log(`Math.imul(${x}, ${y}) == ${checkZ} ... ${(checkZ === z)? `ok`: `error! z was ${z}`}`);
}

console.log('---------- TEST EVEN Y ----------');
for (let i = 1; i < 32; i++) {
    let y = ((Math.random() * 0x100000000) & (0xffffffff << i) | (1 << i)) >>> 0;
    let z = ((Math.random() * 0x100000000) & (0xffffffff << i)) >>> 0;
    testYZ(y, z);
}
testYZ(0, 0);

console.log('---------- TEST ODD Y ----------');
for (let i = 0; i < 100; i++) {
    let y = ((Math.random() * 0x100000000) | 1) >>> 0; // odd number
    let z = (Math.random() * 0x100000000) >>> 0;
    testYZ(y, z);
}
// the final one is from OP
testYZ(2654435761, 1447829970);

console.log('TESTS SUCCEEDED:', testsSucceeded);
console.log('TESTS FAILED:', testsFailed);
    Login or Signup to reply.
  2. 0

    While blakkwaters answer is good, there is a simpler and more efficient iterative technique to "extend" a solution that is valid for a couple of bits to a solution that is valid for more bits.

    To "unmultiply" by odd numbers, you only need to multiply by the modular multiplicative inverse of that odd number, which you can get like this (using Hensel lifting, which doubles the number of correct bits at every step, instead of adding one more correct bit):

    function inverse(d) {
    // assumes: d is odd
    var x = Math.imul(d, d) + d - 1;
    x = Math.imul(x, 2 - Math.imul(x, d));
    x = Math.imul(x, 2 - Math.imul(x, d));
    x = Math.imul(x, 2 - Math.imul(x, d));
    return x >>> 0;
}

    "Unmultiplying" z by an even number y is only possible if z is at least as even as y (in the sense of having at least as many trailing zeroes), and in that case we can just drop the trailing zeroes of y from both y and z.

    Math.clz32(z & -z) ^ 31 is a trick to count the trailing zeroes. That gives 63 if z = 0, but that’s OK here. If z = 0 the result will still be zero which is correct. If y = 0 then there is only a solution if z = 0 as well, so having the trailing zero count be 63 is OK.

    function unmultiply(y, z) {
    let z_ctz = Math.clz32(z & -z) ^ 31;
    let y_ctz = Math.clz32(y & -y) ^ 31;
    if (y_ctz > z_ctz)
        return NaN;
    
    return Math.imul(z >>> y_ctz, inverse(y >>> y_ctz)) >>> 0;
}

    I didn’t put the tests if y and z are uint32 as a stylistic choice but of course you can put those back.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search