divide two binary Long division, Binary division algorithm

Question

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?

I was wrong about editing string as index.

Lex
– Lex

2022-11-12 07:14:46 +00:00
Commented Nov 12, 2022 at 7:14 — Lex
– Lex, Commented Nov 12, 2022 at 7:14

Trentium · Accepted Answer · 2022-11-12 13:50:44Z

1

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.

answered Nov 12, 2022 at 13:50

Trentium

3,7992 gold badges14 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lex Over a year ago

thanks for tips. I used method to copy string and a function to paste zeros at beggining to compare numbers.

Collectives™ on Stack Overflow

divide two binary Long division, Binary division algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related