-1
$\begingroup$

Is there any algorithm for the following problems:

  1. Remainder of a binary number when divided by 10

    (1010...0101) mod 10 = ?

  2. Result of dividing a binary number by 10

    (1010...0101) div 10 = ?

I'm looking for algorithms with the smallest calculations possible, mainly working on the bit string, shifting it, removing or manipulating some of its bits.

Suppose the input is "1110110" which is "118" in decimal. What I'm trying to do is, I want to convert this bit string into a decimal string using this algorithm ::

B: Bit String
D: Decimal String
while (B is not empty) {
    Add character to beginning of D: MOD10(B)
    DEVIDEBY10(B)
}

I need the functions MOD10 and DEVIDEBY10 to make this algorithm work. Their argument is a bit string, not a numeric data type.

$\endgroup$
  • 1
    $\begingroup$ Do you mean binary 10 or decimal 10 ??? Are your numbers in binary or character strings ? $\endgroup$ – Yves Daoust Jul 19 '17 at 7:40
  • $\begingroup$ (assuming your $10$ is two in binary) What would your answer be in decimal when dividing by ten? $\endgroup$ – Henry Jul 19 '17 at 7:55
  • $\begingroup$ You can get the remainder modulo ten by finding the remainder modulo two (=the LSB) and module five, and then CRT combining them. To do that modulo five step uses the fact that $16^n\equiv1\pmod5$ for all $n$. So you could split the binary into groups of $4$ bits (starting from LSB), and adding them. Just like the usual business of "casting out nines" from a base ten integer. Now you are "casting out $1111_2$s (or 0xf's)of hexadecimals. Unfortunately I don't see a way to speed up division using the same idea. $\endgroup$ – Jyrki Lahtonen Jul 19 '17 at 8:03
  • $\begingroup$ And the number is stored in a character string. $\endgroup$ – Farahmand Jul 19 '17 at 9:51
  • $\begingroup$ Maybe we can help you with your conversion if you tell us clearly what is the input format and what is the output format that you want. $\endgroup$ – Yves Daoust Jul 19 '17 at 9:57
0
$\begingroup$

There is no much better way than... division and remainder.

q = n / d, r = n % d

Even though it is possible to efficiently compute the quotient and the remainder simultaneously, high-level programming languages do not offer this option. As division and remainder are costly operations, you can trade the latter for a multiply:

q = n / d, r = n - q * d

An alternative is to perform a multiply by 1/10, simulating fixed-point arithmetic.

Take a sufficiently large power of two to scale the numbers and let a:= 2^f/10. Then the quotient is approximated by

q = (a * n) >> f

Due to truncation, the value of q will be underestimated. You can adjust with an additive constant

q = (a * n + b) >> f

in such a way that the estimate is always exact.

Complete treatment depends on the range of values that you need to handle and is out of the scope of this answer.

$\endgroup$
  • $\begingroup$ Today's optimizing compilers are quite capable of noticing that a piece of code is computing the quotient and remainder from the same division and only issue one hardware division. For example GCC compiles int divmul(int a, int b) { return a/b+a%b; } to a single idivl (with some set-up to sign-extend a) followed by adding the two results. $\endgroup$ – Henning Makholm Jul 19 '17 at 8:15
  • $\begingroup$ @HenningMakholm: then a very clever compiler will notice that n - q * d computes the remainder ;-) $\endgroup$ – Yves Daoust Jul 19 '17 at 8:17
  • $\begingroup$ x @Yves: But it is not, in fact, that clever. And code should be optimized for readability anyway (especially when the more readable code also results in more efficient assembly). $\endgroup$ – Henning Makholm Jul 19 '17 at 8:22
  • $\begingroup$ @HenningMakholm: I was thinking of a deep-learning based one, which will also refactor the code for readability. $\endgroup$ – Yves Daoust Jul 19 '17 at 8:25
  • $\begingroup$ As I said before, I can't use such operations. I have to work with a bit string, which means I don't have / ans % operators. Also, the decimal parts are not important (e.g 3/2 = 1) $\endgroup$ – Farahmand Jul 19 '17 at 9:49
0
$\begingroup$

For a binary string stored as a character string, the answer is trivial for division by 2: the remainder is the rightmost digit and the quotient is what you get after dropping the rightmost character. No arithmetic involved.

$\endgroup$
  • $\begingroup$ I had to edit the queston. I was confused, sorry... $\endgroup$ – Farahmand Jul 19 '17 at 10:12
0
$\begingroup$

I recommend the paper from HackersDelight for this. Modern compilers do this internally quite well but this might help to understand what they do.

The basic idea is to multiply the number by 1/10 instead of doing a division using shifts and adds. Due to the repeating pattern of 1/10 in binary form this is rather compact. The inverse isn't exact so this introduces a slight error. The algorithm then computes the remainder using r = n - q * 10 and if the r is > 9 then the result is adjusted by one.

Here is the code for num/10 and num%10 extended to 64bit:

      uint64_t q, r;
      q = (num >> 1) + (num >> 2);
      q = q + (q >> 4);
      q = q + (q >> 8);
      q = q + (q >> 16);
      q = q + (q >> 32);
      q = q >> 3;
      r = num - q * 10;
      if (r > 9) {
        q++;
        r -= 10;
      }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.