3
$\begingroup$

I am reading this material to understand the basics of number system. I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number. The heading of that part where I am stuck is Decimal to Base The algorithm (may be presented less than faithfully, please refer the link) it mentions there is:

  1. Let $p = \lfloor \sqrt{V} \rfloor$
  2. Let $v = \lfloor \dfrac V {B^p} \rfloor$
    (v is the next digit to the right)
  3. Make $V = V − v * B^p$
  4. Repeat steps 1 through 3 until $p = 0$

It is explaining by taking an example of converting decimal number 236 to binary.

I am not getting how it is calculating the 1st step, i.e. to get the value of p.

It writes that p = int(square root of V)

Now, square root of 236 = 15.36229149573721635154

As per point number 1, p = integer part of 15.36229149573721635154 So, I remove the decimal part and p then becomes 15. But the material there says it is 7.

I can't get what is happening here. I am stuck.

$\endgroup$
  • 1
    $\begingroup$ Please spend some effort to re-type the algorithm in a readable form. Relying on external sources (which may change or go away at any point) is no good for SE. Also, have you checked out other base conversion algorithms? This one seems ... needlessly convoluted. $\endgroup$ – Raphael Jan 13 '16 at 7:41
  • 2
    $\begingroup$ $7 = \text{int} (\log_{2} 236)$. Generally, $p = \text{int} (\log_{B} V)$. $\endgroup$ – hengxin Jan 13 '16 at 7:46
  • $\begingroup$ @hengxin Yes your formula is what is fitting the algorithm completely. So that is a mistake in that material. It mentions square root but it is log. Great! I thank you very much for your valuable assistance. $\endgroup$ – Ravi Jan 13 '16 at 7:53
  • 1
    $\begingroup$ Hi Ravi. The algorithm you posted is too complicated. Binary numbers are powers of two, like having only two digits, divisions/multiplications by 2 should be more than enough for a beginner. I got this page for you. interactivepython.org/runestone/static/pythonds/BasicDS/… For dealing with short number, we also have a simpler strategy. $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 7:55
  • 1
    $\begingroup$ I added the Cisco academy algorithm as a curiosity. It is mostly subtractions once you know the powers of two by heart. $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 8:43
4
$\begingroup$

Just converting the comment into a short answer:

$7 = \text{int}(\log_{2} 236)$. Generally, $p = \text{int}(\log_{B}V)$.


As other people pointed out, this algorithm is needlessly complicated and not practical; it is not easy to calculate $\log_B V$ for large $V$ by pencil and paper. Instead, use the other algorithm which is also mentioned in the article you are reading:

From decimal to binary

  • Step 1: Check if your number is odd or even.
  • Step 2: If it's even, write 0 (proceeding backwards, adding binary digits to the left of the result).
  • Step 3: Otherwise, if it's odd, write 1 (in the same way).
  • Step 4: Divide your number by 2 (dropping any fraction) and go back to step 1. Repeat until your original number is 0.
$\endgroup$
  • $\begingroup$ Yes that algorithm is complicated for large values of V. Thank you for your valuable suggestion and advice. $\endgroup$ – Ravi Jan 13 '16 at 8:04
  • $\begingroup$ I do not have enough points here in this forum to edit the english. "for A human" $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 8:12
  • $\begingroup$ I was describing an alternative algorithm that we use to do it by head when we already now the powers of two by heart in where we just subtract numbers; this one here is easier to undertand. $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 8:15
  • $\begingroup$ (and likewise, inverting the process you are able to look at binary, octal and hexadecimal numbers and tell the value in decimal doing math on your head) $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 8:52
  • 1
    $\begingroup$ @RuiFRibeiro yes for converting from other bases to decimal, it is pretty straight forward and same method for all which can be done mentally. $\endgroup$ – Ravi Jan 13 '16 at 9:02
1
$\begingroup$

In Cisco academy for doing the math by heart we know the powers of two, to allow us to do calculations by head. Note that the algorithm only is efficient once you can do it on your head, as it is mostly subtractions once you are familiar with the procedure.

The algorithm works roughly this way:

  • you pickup the power of two immediately lower to your value
  • do
  • number lower power == 0
  • number greater power == 1 ; and number = number - power
  • go down to next power of 2
  • while number not 0

If the number comes to 0 before the power end, you fill out the others with 0.

So for your value of 236, I know the powers bellow are: 128 64 32 16 8 4 2 1

So, lets see the powers of 2^n

(7) 236>128==1, number=236-128=108
(6) 108>64==1, number=108-64=44
(5) 44>32==1, number=44-32=12
(4) 12>16==0
(3) 12>8==1, number=12-8=4
(2) 4>=4==1, number=4-4=0 number==0 ends calculations
(1) ==0
(0) ==0

So 236 is 11101100 in binary.

$\endgroup$
  • 1
    $\begingroup$ Great method to convert mentally from decimal to binary. Other methods mentioned works in a reverse order, i.e. when one finishes the division by 2, that last remainder is the 1st digit from left side in the binary number (so difficult to do mentally). Rui F Ribeiro you mentioned in a comment that for dealing with short numbers, there is a simpler strategy. Please mention that also here if it is other than this. $\endgroup$ – Ravi Jan 13 '16 at 8:59
  • 1
    $\begingroup$ This is the simple strategy, if some mentions like 96 (32+64) I immediately can answer 1100000 $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 9:01
  • 1
    $\begingroup$ btw, if you change the power of 2 to power of 16, obviously mapping A-F to 10-15, the rationale for hexadecimal, or changing from the power of 2 to 8, for octal, the algorithm work pretty muchs the same. $\endgroup$ – Rui F Ribeiro Jan 13 '16 at 9:27

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.