Binary to decimal conversion.
Author Message
Binary to decimal conversion.

Hello,

I'm writing a function to convert binary numbers to decimal.  I want my
solution to be recursive.  In Scheme, I would simply do:

(define (binary-to-dec number)
(define (btd number counter)
(let ((current-digit (remainder number 10))
(rest-number (truncate (/ number 10))))
(cond ((zero? rest-number) (* number (pow 2 counter)))
(else (+ (* current-digit (pow 2 counter))
(btd rest-number (+ counter 1)))))))
(btd number 0))

Isn't Scheme beautiful?

In C, I tried doing:

int bin_to_dec(int num) {
static int counter=0;
int rest=num/10,curr=num%2;

if (!rest) return curr*pow(2,counter);
counter++;

return curr*bin_to_dec(rest)+curr*bin_to_dec(curr);

Quote:
}

But I get off-by-one errors bin_to_dec(1001), which should be 9, returns
8.  Any ideas on a better and correct way to do this recursively in C?

Thanks,
-- john

Sent via Deja.com http://www.*-*-*.com/

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> I'm writing a function to convert binary numbers to decimal.  I want
my
> solution to be recursive.  In Scheme, I would simply do:

> (define (binary-to-dec number)
>   (define (btd number counter)
>     (let ((current-digit (remainder number 10))
>           (rest-number (truncate (/ number 10))))
>       (cond ((zero? rest-number) (* number (pow 2 counter)))
>             (else (+ (* current-digit (pow 2 counter))
>                      (btd rest-number (+ counter 1)))))))
>   (btd number 0))

> Isn't Scheme beautiful?

Because of or in spite of the seven right parentheses in a row?

If I understand the Scheme correctly, this could be written in C:

int btd(int number, int counter) {
int current_digit = number % 10;
int rest_number = number / 10;
if (rest_number == 0)
return number * pow(2,counter);
else
return current_digit * pow(2,counter)
+ btd(rest_number,counter+1);

Quote:
}

int binary_to_dec(int number) {
return btd(number,0);

Quote:
}

I'm not sure that I would call it a binary to decimal conversion.
It reinterprets a decimal number d0*pow(10,0)+d1*pow(10,1)+...
as d0*pow(2,0)+d1*pow(2,1)+....

Quote:
> In C, I tried doing:

> int bin_to_dec(int num) {
>       static int counter=0;

Yuk.  Even if the code were correct, there's no way to reset this
if you call the function twice.  If you allow two functions in
Scheme, why not in C?  The only drawback is that you can't nest
the second function, but you could make binary_to_dec external
and btd static in their own compilation unit.  Or you could use
an iterative solution.

Quote:
>       int rest=num/10,curr=num%2;

Why isn't this curr=num%10, if you're following the Scheme code?

Quote:
>       if (!rest) return curr*pow(2,counter);
>       counter++;

>       return curr*bin_to_dec(rest)+curr*bin_to_dec(curr);

This is nothing like the Scheme, and counter is going to go
crazy.  Since you don't know which call of bin_to_dec occurs
first, this isn't even well-defined.  You could make it look
more like the Scheme by writing
return ((((((curr*bin_to_dec(rest)+curr*bin_to_dec(curr)))))));
but it's still very wrong.

Quote:
> }

> But I get off-by-one errors bin_to_dec(1001), which should be 9,
returns
> 8.  Any ideas on a better and correct way to do this recursively in C?

If your compiler had only evaluated the last expression right to left,
you would have gotten 2 (the not-so-classic off-by-seven error).

--
MJSR

Sent via Deja.com http://www.deja.com/

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> [...]
>       if (!rest) return curr*pow(2,counter);

This is most likely the source of your problem.  pow()
takes `double' arguments and returns a `double' value, and
floating-point arithmetic is inherently inexact.  It's
likely that `pow(2,3)', for example, is returning not exactly
8.0, but some number like 7.9999999398347976 -- which gets
truncated to 7 upon conversion to `int'.

Quote:
> Any ideas on a better and correct way to do this recursively in C?

Plenty, but since this might be homework I'll just offer
a hint rather than a complete solution.  Two hints, in fact:

-   Look up the `<<' operator.  Alternatively,

-   If you happen to have the (exact, `int') value of
`pow(2,counter)' lying around somewhere, can you
think of an easy way to compute `pow(2,counter+1)'?

--

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> Hello,

> I'm writing a function to convert binary numbers to decimal.  I want my
> solution to be recursive.  In Scheme, I would simply do:

> (define (binary-to-dec number)
>   (define (btd number counter)
>     (let ((current-digit (remainder number 10))
>           (rest-number (truncate (/ number 10))))
>       (cond ((zero? rest-number) (* number (pow 2 counter)))
>             (else (+ (* current-digit (pow 2 counter))
>                      (btd rest-number (+ counter 1)))))))
>   (btd number 0))

> Isn't Scheme beautiful?

In C, I would simply do:

int bin_to_dec(int num)
{
return num;

Quote:
}

Isn't C beautiful? ;-)

--
Luis Grave

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

>I'm writing a function to convert binary numbers to decimal.  I want my
>solution to be recursive.  In Scheme, I would simply do:

>(define (binary-to-dec number)
>  (define (btd number counter)
>    (let ((current-digit (remainder number 10))
>          (rest-number (truncate (/ number 10))))
>      (cond ((zero? rest-number) (* number (pow 2 counter)))
>            (else (+ (* current-digit (pow 2 counter))
>                     (btd rest-number (+ counter 1)))))))
>  (btd number 0))

>Isn't Scheme beautiful?

Definitely not for this particular job.

Quote:
>In C, I tried doing:

>int bin_to_dec(int num) {
>      static int counter=0;
>      int rest=num/10,curr=num%2;

>      if (!rest) return curr*pow(2,counter);
>      counter++;

>      return curr*bin_to_dec(rest)+curr*bin_to_dec(curr);
>}

>But I get off-by-one errors bin_to_dec(1001), which should be 9, returns
>8.  Any ideas on a better and correct way to do this recursively in C?

Your problem doesn't fit well to a recursive approach.  You could
probably turn this iterative solution into tail recursion, but is it
really worth it?

unsigned bin2dec(unsigned num)
{
unsigned res = 0;
while (num) {
res = (res * 2) + (num % 10);
num /= 10;
}
return res;
}

Dan
--
Dan Pop
CERN, IT Division

Mail:  CERN - IT, Bat. 31 1-014, CH-1211 Geneve 23, Switzerland

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> Your problem doesn't fit well to a recursive approach.  You could
> probably turn this iterative solution into tail recursion, but is it
> really worth it?

For a passing grade in the course, probably so. <g>

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.
In article

Quote:

> > Your problem doesn't fit well to a recursive approach.  You could
> > probably turn this iterative solution into tail recursion, but is it
> > really worth it?

> For a passing grade in the course, probably so. <g>

I have stated my problem and provided the source code of my attempts at
it (which covered a large portion of the solution), in two programming
languages.  I've taken all necessary steps to receive legitimate help
(according to Usenet rules,) so from your one-liner post I conclude that
you are a troll who is not aware of the proper way to ask help on
Usenet.

Thanks,
-- John

Sent via Deja.com http://www.deja.com/

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> > > Your problem doesn't fit well to a recursive approach.  You could
> > > probably turn this iterative solution into tail recursion, but is it
> > > really worth it?

> > For a passing grade in the course, probably so. <g>

> I have stated my problem and provided the source code of my attempts at
> it (which covered a large portion of the solution), in two programming
> languages.  I've taken all necessary steps to receive legitimate help
> (according to Usenet rules,) so from your one-liner post I conclude that
> you are a troll who is not aware of the proper way to ask help on
> Usenet.

Whoa!   I put a <g> after that comment!   There's nothing insincere
about that comment anyway.   If you were directed to package that
in a recursive manner then of course you have to do that.  Dan's
advice may be exactly what you need right now.   Essentially, that
was what I was saying with my last post.

- Larry Weiss

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> Hello,

> I'm writing a function to convert binary numbers to decimal.  I want my
> solution to be recursive.  In Scheme, I would simply do:

> (define (binary-to-dec number)
>   (define (btd number counter)
>     (let ((current-digit (remainder number 10))
>           (rest-number (truncate (/ number 10))))
>       (cond ((zero? rest-number) (* number (pow 2 counter)))
>             (else (+ (* current-digit (pow 2 counter))
>                      (btd rest-number (+ counter 1)))))))
>   (btd number 0))

> Isn't Scheme beautiful?

I guess it is if you like ))))))).  Why do you want your solution to be
recursive?  I've heard that some of these "functional" languages use a lot
of recursion, so maybe that's why you like it.  Many implementations of C,
however, limit stack size, making recursive solutions less preferable.  C
programmers usually won't reach for a recursive solution unless there is
some really compelling reason.

Assuming your binary number is stored as a string, and is 32 characters or
less, an iterative solution should be a piece-o-cake.  Use strlen, <<, and
repetitive addition.  If it's more than 32 characters, you'll have to hack
up some bignums, or get a bignum library from somewhere.

--Steve

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

following:

Quote:
>Hello,

>I'm writing a function to convert binary numbers to decimal.  I want my
>solution to be recursive.  In Scheme, I would simply do:

>(define (binary-to-dec number)
>  (define (btd number counter)
>    (let ((current-digit (remainder number 10))
>          (rest-number (truncate (/ number 10))))
>      (cond ((zero? rest-number) (* number (pow 2 counter)))
>            (else (+ (* current-digit (pow 2 counter))
>                     (btd rest-number (+ counter 1)))))))
>  (btd number 0))

>Isn't Scheme beautiful?

That Scheme isn't that great, since Scheme does not support nested
defines.  The first define should be changed to a named letrec.

-Chris (OT)
--
http://www.math.grinnell.edu/~kern/index.html

Tue, 18 Mar 2003 03:00:00 GMT
Binary to decimal conversion.

Quote:

> Hello,

> I'm writing a function to convert binary numbers to decimal.  I want my
> solution to be recursive.  In Scheme, I would simply do:

> (define (binary-to-dec number)
>   (define (btd number counter)
>     (let ((current-digit (remainder number 10))
>           (rest-number (truncate (/ number 10))))
>       (cond ((zero? rest-number) (* number (pow 2 counter)))
>             (else (+ (* current-digit (pow 2 counter))
>                      (btd rest-number (+ counter 1)))))))
>   (btd number 0))

> Isn't Scheme beautiful?

Yeah, but that code isn't.

(define (btd n)
(if (< n 10)
n
(+ (remainder n 10)  (* 2 (btd (quotient n 10))))))

or, rearranged tail recursively,

(define (btd n)
(define (btd-aux n r c)
(if (< n 10)
(+ r (* c n))
(btd-aux (quotient n 10) (+ r (* c (remainder n 10))) (* c 2))))
(btd-aux n 0 1))

Quote:
> In C, I tried doing:

> int bin_to_dec(int num) {
>       static int counter=0;
>       int rest=num/10,curr=num%2;

>       if (!rest) return curr*pow(2,counter);
>       counter++;

>       return curr*bin_to_dec(rest)+curr*bin_to_dec(curr);
> }

c isn't scheme. But if you transliterate your program from scheme, you'd
stand a fighting chance. The last line looks particularly dumb. The
static variable counter runs a close second - why do you need it at all?

Wed, 19 Mar 2003 09:03:50 GMT
Binary to decimal conversion.

Quote:

> following:
> >(define (binary-to-dec number)
> >  (define (btd number counter)
[...]
> >Isn't Scheme beautiful?

> That Scheme isn't that great, since Scheme does not support nested
> defines.  The first define should be changed to a named letrec.

It isn't, but not for that reason. Scheme has "internal definitions" in
r5rs.

Wed, 19 Mar 2003 09:09:40 GMT
Binary to decimal conversion.
On Sat, 30 Sep 2000 01:09:40 GMT, "Bruce G. Stewart"

Quote:

>> following:
>> >(define (binary-to-dec number)
>> >  (define (btd number counter)
>[...]
>> >Isn't Scheme beautiful?

>> That Scheme isn't that great, since Scheme does not support nested
>> defines.  The first define should be changed to a named letrec.

>It isn't, but not for that reason. Scheme has "internal definitions" in
>r5rs.

Bah, it shouldn't :-)  OK, fine, I was spoon-fed Scheme by
instructors.  Sue me :)

-Chris (i still prefer a named letrec)
--
http://www.math.grinnell.edu/~kern/index.html

Wed, 19 Mar 2003 03:00:00 GMT

 Page 1 of 1 [ 13 post ]

Relevant Pages