CODEWITHSUNDEEP
javascriptbinary
Lex
Lex

Reputation: 159

divide two binary Long division, Binary division algorithm

I am trying to implement Long division algorithm. But I faced some problems. enter image description here

If we take N=1100 and D=100

Step 1: Set R=0 and Q=0 Step 2: Take i=3 (one less than the number of bits in N) Step 3: R=00 (left shifted by 1) Step 4: R=01 (setting R(0) to N(i))

how did we get '01' on fourth step, if n[3] = 0 from N = 1100

I tried to code program, but I can't understand the fourth step.

        n = "1100";
        d = "0100";

        let q = "0";
        let r = "0";

        for (let i = 3; i >= 0; i--) {
          r = r + "0"; //0 + 0 = "00"
          r[0] = n[i];

          if (r >= d) {
            r = String(r - d);
            q[i] = 1;
          }
        }

        console.log(q);
        console.log(r);

We use Q as result of '1' but if result of division is '101' where did we take '0' from r?

Upvotes: 1

Views: 484

Answers (1)

Trentium
Trentium

Reputation: 3719

There are numerous data type issues with the way you've written the algorithm. The following are some helpful tips to assist you in your endeavor...

  • All the binary values are written in Big Endian, whereas the for loop is written expecting Little Endian.

  • The line r[0] = n[i] is not doing what you think. Try a simple experiment as follows, and you will see that x does not change as expected... 

    x = "abcd"
x[3] = "e"
console.log( x )    // x is still "abcd"

  • The line if (r >= d) is performing a string comparison rather than numeric comparison. This will lead to erroneous results. For example, consider... 

    console.log( "11" >= "01111" )
console.log( parseInt( "11", 2 ) >= parseInt( "01111", 2 ) )

  • The line r = String(r - d) is attempting to substract 2 strings which Javascript will attempt to coerce to decimal Numbers, unless the strings are preceded by "0b" in which case the coercion will interpret the strings as binary numbers. 

    console.log( 'abcd' - 'efghi' )       // NaN
console.log( '1100' - '0100' )        // Decimal result of one thousand.
console.log( '0b1100' - '0b0100' )    // Proper binary result of 8 (0b1000).

  • The line q[i] = 1 suffers the same issue as noted in the second bullet.

Upvotes: 1

Related Questions