## Interview Question

• 0

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)

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

note that gmp is only needed for testing

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.

### 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.