Mysterious 2 arising in the output of my JavaScript decimal to binary converter?

Question

I am trying to implement a fairly simple Decimal to Binary converter using the following recursive function:

function dectobin(d) {
            if (0 >= d) { return 0; }
            else if (1 == d) { return 1; }
            else {
                return 10 * dectobin(Math.floor(d / 2)) + (d % 2);
            }
        }

Now the problem is that when I test it with 70007, there seems to be some overflow of 1 at the last recursion when the last entry is pop off the stack. So once dectobin(35003) returns with 100010001011101, it is scaled by 10 to 1000100010111010, and a 1 is suppose to be added. Except, instead of adding 1, it adds a 2 so the answer becomes: 1000100010111012. Now I have checked my logic and math and found not mistake in that, so I have a feeling this is an internal structure of the language that is causing this error. So if anyone can help me out here and explain to me what's the issue that would be most gratifying. Thanks in advance.

...or you could simply use: `70007..toString(2)` – zzzzBov Mar 06 '12 at 05:37 — zzzzBov, Mar 06 '12 at 05:37

KooiInc · Answer 1 · 2012-03-06T07:53:16.850

2

For the record: you can convert a decimal to binary (string) using:

(70007).toString(2)

There's no need to multiply by 10. Furthermore 0 >= d will never be met.

Rewriting your function to:

function dectobin(d) {
  function recurse(dd) {
    return dd > 1 ? recurse(Math.floor(dd/2))+''+dd%2 : dd;
  }
  return recurse(d);
}

Should deliver the right result

edited Mar 06 '12 at 07:53

answered Mar 06 '12 at 05:39

KooiInc

119,216
31
141
177

Yes, but now that the question is raised, what is wrong with my code? – user1251380 Mar 06 '12 at 05:50

score 1 · Answer 2 · answered Mar 06 '12 at 06:19

Numbers more than 15 digits long are not reliable in JavaScript due to the internal representation of numbers as IEEE doubles.

E.g.

10001000101110110+1 == 10001000101110112
10001000101110110+2 == 10001000101110112
10001000101110110+3 == 10001000101110112
10001000101110110+4 == 10001000101110114
10001000101110110+5 == 10001000101110116

They're all true; so you might wanna check out some of the BigNumber libraries to make your code work.

score 0 · Answer 3 · edited May 23 '17 at 12:12

I could be wrong about this, but this could be a precision error arising from the fact that JS numbers are represented as IEEE doubles, and the number that you're describing is so large that it might actually be out of the range of integer values representable exactly with IEEE doubles. If that's the case, you should probably consider having your function return a string representation of the binary representation rather than a numerical representation of the 1s and 0s.

According to this earlier answer, the largest integer representable exactly by an IEEE double (with no gaps in the representable integers) is 2^53, which is about 10^14. The number you're describing the error with has more than 14 digits, so I would suspect that this is the problem.

Hope this helps!

Mysterious 2 arising in the output of my JavaScript decimal to binary converter?

3 Answers3