Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

here the main difficulty is to perform the division of 64-bit number by 32-bit efficiently.
Having this operation, say div2by1(), which returns quotient and remainder, single-word division can be realized just in a single loop as follows:

assume a[n-1..0] - the dividend; c - divisor
r = 0; // residue
for(i = n-1; i >= 0; i--) {
   x = (r << 32) + a[i]; // construct 64-bit number
   div2by1(&q[i], &r, x, c); // divide 'x' by 'c'
  // q[i] - quotient, r - remainder
}

to realize div2by1(x, c) we use floating-point arithmetic to avoid division.
In other words, instead of 'x' dividing by 'c' we multiply x by 1/c using floating-point.
Yet, there is one problem here: namely if the divisor 'c' is small while 'x' is large,
'x/c' might not fit in 53-bit mantissa of floating-point number (resulting in truncation of LSB bits). To avoid this, we first shift 'c' to the left to make sure that its 2 most significant bits
are set. This makes the division only slightly more complicated since, then, we neeed to recover the quotient in two steps. The code is below:

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <math.h>
#include <gmp.h>

// divides a multi-precision integer a[0..n-1] by a single word c
void div_by_limb(const unsigned *a, unsigned n, unsigned c) {
    typedef unsigned long long uint64;
    unsigned c_norm = c, sh = 0;
    while((c_norm & 0xC0000000) == 0) { // make sure the 2 MSB are set
        c_norm <<= 1; sh++;
    }
    // precompute the inverse of 'c'
    double inv1 = 1.0f / (double)c_norm, inv2 = 1.0f / (double)c;
    unsigned i, r = 0;
    printf("\nquotient: "); // quotient is printed in a loop
    for(i = n - 1; (int)i >= 0; i--) { // start from the most significant digit
        unsigned u1 = r, u0 = a[i];
        union {
            struct { unsigned u0, u1; };
            uint64 x;
        } s = {u0, u1}; // treat [u1, u0] as 64-bit int
        // divide a 2-word number [u1, u0] by 'c_norm' using floating-point
        unsigned q = (unsigned)((double)s.x * inv1), q2;
        r = u0 - q * c_norm;
        // divide again: this time by 'c'
        q2 = (unsigned)((double)r * inv2);
        q = (q << sh) + q2; // reconstruct the quotient
        printf("%x", q);
    }
    r %= c; // adjust the residue after normalization
    printf("; residue: %x\n", r);
}

int main() {
    mpz_t z, quo, rem;
    mpz_init(z); // this is a dividend
    mpz_set_str(z, "21321342157645763456234564567856785675234597", 10);
    unsigned div = 234523; // this is a divisor
    div_by_limb((unsigned *)z->_mp_d, mpz_size(z), div);
    mpz_init(quo); mpz_init(rem);
    mpz_tdiv_qr_ui(quo, rem, z, div); // divide 'z' by 'div'
    gmp_printf("compare: Quo: %Zx; Rem %Zx\n", quo, rem);
    mpz_clear(quo);
    mpz_clear(rem);
    mpz_clear(z);
    return 1;
}

in linux compile with: -lgmp -lstdc++ linker flags (gmp library should be installed by default)

- Anonymous December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

note that gmp is only needed for testing

- Anonymous December 28, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More