in reply to decimal to binary conversion need help

And, just for fun, here's a very slow pure perl version that does not depend on arithmetic ops. 
#!perl

use warnings;
use strict;

# arithmetic operations on (nonegative) binary numbers
sub addbin0 { 
 my($a,$b) = @_; 
 $a || $b ?
  ( chop($a) ? 
   (chop($b) ? addbin1($a, $b) . "0" : addbin0($a, $b) . "1") : 
   (chop($b) ? addbin0($a, $b) . "1" : addbin0($a, $b) . "0") ) :
  "";
} 
sub addbin1 { 
 my($a,$b) = @_; 
 $a || $b ?
  ( chop($a) ? 
   (chop($b) ? addbin1($a, $b) . "1" : addbin1($a, $b) . "0") : 
   (chop($b) ? addbin1($a, $b) . "0" : addbin0($a, $b) . "1") ) :
  "1";
} 
sub addbin {
 addbin0(@_) || "0";
}

# multiplication algorithm to convert decimal number to binary
our @dec2bin1 = qw(0 1 10 11 100 101 110 111 1000 1001);
sub dec2bin {
        $_[0]=~/^\s*(-?)(\d+)/ or do {
                warn "dec2bin can not interpret its first argument as 
+decimal";
                return "0";
                };
        my($sgn, $dec) = ($1, $2);
        $dec=~/(\d)/g or die "internal error"; # this regexp always ma
+tches
        my $b = $dec2bin1[$1];
        while($dec=~/(\d)/g) {
                $b = addbin($b . "0", $b . "000"); # multiply by 1010b
                $b = addbin($b, $dec2bin1[$1]);
        }
        $sgn . $b;
}

# convert a number 
print dec2bin($ARGV[0]), "\n";

__END__

[download]

Update: changed sub dec2bin above by merlyn's suggestion. Well, it still doesn't check for nonnumeric junk at the end of string, sorry.

Original sub: 

# multiplication algorithm to convert decimal number to binary
our @dec2bin1 = qw(0 1 10 11 100 101 110 111 1000 1001);
sub dec2bin {
        $_[0]=~/^(-?)(\d*)/;
        my($sgn, $dec) = ($1, $2);
        $dec=~/(\d)/g;
        my $b = $dec2bin1[$1];
        while($dec=~/(\d)/g) {
                $b = addbin($b . "0", $b . "000"); # multiply by 1010b
                $b = addbin($b, $dec2bin1[$1]);
        }
        $sgn . $b;
}

[download]

Replies are listed 'Best First'.
•Re^2: decimal to binary conversion need help
by merlyn (Sage) on Jan 06, 2005 at 13:15 UTC 
    sub dec2bin {

    [download]
    I don't see any "decimal" operations in there. That's just "num2bin". Take a number, and create a binary string from it.

    In fact, this whole thread has made that common mistake. You aren't converting any "decimal" anywhere. Just because Perl knows how to take a string of decimal digits during parse to create a number internally doesn't mean your subroutine can deal with "decimal" numbers. It's Perl, not you.

    -- Randal L. Schwartz, Perl hacker
    Be sure to read my standard disclaimer if this is a reply.

    update: Oooh, I missed the "bad use of $1" before as well. Never never never use $1 except in the condition of the previous match.
[reply]
[d/l]
      You aren't converting any "decimal" anywhere.
      Sure we are. He's converting the decimal representation of a number to a binary representation of the same number. Also, since we all deal with representations of numbers to do arithmetic (computers included), I find your pedantery somewhat boring.

      thor

      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

[reply]
        By the time it shows up as an argument to your subroutine, it's not decimal any more. It's just a "number". In fact, internally, it's either a binary integer, or an IEEE floating point value (except on exotic hardware). There's no decimal there.

        Now, if your routine took a string, and then did the "multiply by 10 and add the next digit" trick for the entire string, then you'd be converting "decimal to number to binary".

        And yes, this does make a difference. It helps to understand that Perl is not thinking in decimal, especially when it comes to floating point values (the 10 * 0.1 != 1.0 problem).

        So, even if you wanna sweep it under the rug, my followup is to help inform others that are reading, so that they can be accurate in their understanding and assistance.

        -- Randal L. Schwartz, Perl hacker
        Be sure to read my standard disclaimer if this is a reply.

[reply]

      Hello, merlyn. Basically, you are right here. Numbers are one thing, and representations are an other, so saying "convert a decimal number to a binary one" might not be a very precise phrase. I admit that I may be prone to this kind of error sometimes.

      I, however, have to disagree with your reply in this particular case. Most solutions in this thread, or indeed, most solutions that would come into your mind if someone asks this questions indeed work by first converting the decimal representation of a number to an internal form, than converting that number to binary form. The internal for may be based on binary, or it may be based on decimal, but this is not important to the user. (If I'm not much mistaken, binary representation of bignums are used in ruby and mathematica; decimal ones in perl's Math::BigInt, dc or bc.)

      The paricular node you've replied to, however, is different. I am not using any internal representations, nor do I use readily provided (by the CPU, Perl, a module, or any other software) arithmetic operations on those. If you read my code, you'll see that the numbers here are always in the form of a srting, more precisely either a decimal or a binary representation of it. (You may count the subroutines on the stack as a different representation if you really want.) All I'm doing with these representations is string operations (provided by perl), and a single indexing an array by a digit. Again, I never convert neither the whole number, nor parts of it to numeric forms understood by the cpu or perl or any perl module, I am implementing all numeric operations by hand.

      You also mention that you don't see any decimal operations in this code. This is because they are not needed: to convert from one representation of a number to an other, you can either do divisions on the first representation, or multiplications on the other. I have chosen the second one, so I do only binary operations; the only decimal operation I do is take the decimal number to digits, and index a lookup array with each.

      Note that this decision of using multiplication or division is usually given by what representation of numbers you use internally. With current cpus, you store numbers in (binary) fixnums, and we can do fast arithmetic on those, so we use binary multiplication to convert from decimal to fixnum (see perl-5.8.5/toke.c:8047), and binary division to convert fixnum to decimal (see perl-5.8.5/sv.c:8956). A bignum library with decimal representation would, of course, use decimal division to convert to binary (bc-1.06/lib/number.c:bc_out_long:1521), and decimal multiplication to convert from binary (bc-1.06/bc/execute.c:push_constant:644). (These could be mixed in theory, even a decimal bignum library could include some binary bignum operations or vice versa, if that helped converting numbers faster.)

      If you look at my program like this, this program does arithmetic operations in binary, so its internal form is binary. Thus, if you don't like the name dec2bin, it should really be called dec2num, not num2bin, as it converts from decimal to internal numeric form. I, however, don't think I use either binary or decimal as an internal numeric form, so I think I can call it dec2bin.

      As for the unchecked regexp matches, you are right, I should indeed chack them. I am, however, lazy, and for a quick demonstration such as this, didn't really care about that. If you give a non-numeric argument to dec2bin, the regexp match of $dec=~/(\d)/g will fail, and the value of $1 will be undefined (not undef). This is a bug, and I'll correct it.

      Update: next time, I'll think before I post something.

[reply]
[d/l]

In Section Seekers of Perl Wisdom