Velocity Reviews > Decimal to Binary

# Decimal to Binary

RobG
Guest
Posts: n/a

 06-30-2010
I'm working on a function to convert decimal integers to binary. The
version below is an example of my implementation of a halving
algorithm, real code works with integer strings of any length and
handles sign. I've reduced the functionality a bit so I don't have to
post the supporting functions for large ints.

This one only works within the range of values supported by the
ECMAScript implementation it's running in and with unsigned integers
(don't use numbers larger than 9 digits).

Anyhow, I remember working on something similar that used a bitwise
operator (around August 2006?) but I can't find it in the archives.
This one seems a bit long and is likely a bit slow, can anyone suggest
some optimisation tips?

// n must be an unsigned string of digits only
function toBin(n) {
var result = [],
i = 0,
d,
len;

// Trivial cases
if (n == '0' || n == '1') {
return n;
}

while (n != '1') {
len = n.length - 1;

// Get last digit
d = n.substring(len);

// If n is not even (i.e. d is odd)
if (d % 2) {
result.push('1');

// Fast subtract one from n to make it even
// d must be odd and 1 to 9 inclusive
n = n.substring(0, len) + --d;

} else {
result.push('0');
}

// Subtract half of n
n = n - (n/2 | 0) + '';
}

return '1' + result.reverse().join('');
}

Incidentally, I'm working on an unlimited precision integer library.
I've done +, -, *, pow, toBinary and a few others, once it's working
properly I'll post the interesting bits.

The pow function uses fast exponentiation by squares, which is pretty
efficient and why I want a more efficient toBin function (though the
toBin part does not use a large part of the computation time, every
little bit helps). It calculates numbers like 77616237978^123 (which
has a result of 1340 digits and is way beyond the native ECMAScript
capability) almost instantly, but I want to make it quicker. It should
be possible to combine toBin with the pow function to make it faster
again.

--
Rob

wolfgang zeidler
Guest
Posts: n/a

 06-30-2010
RobG wrote:
> I'm working on a function to convert decimal integers to binary. The
> version below is an example of my implementation of a halving
> algorithm, real code works with integer strings of any length and
> handles sign. I've reduced the functionality a bit so I don't have to
> post the supporting functions for large ints.
>
> [...]
>
> The pow function uses fast exponentiation by squares, which is pretty
> efficient and why I want a more efficient toBin function (though the
> toBin part does not use a large part of the computation time, every
> little bit helps). It calculates numbers like 77616237978^123 (which
> has a result of 1340 digits and is way beyond the native ECMAScript
> capability) almost instantly, but I want to make it quicker. It should
> be possible to combine toBin with the pow function to make it faster
> again.
>
> --
> Rob

- There's no need to use only 0 and 1,
you may use digits from 0 to 2^n -1.
( In the example below I chosed n == 4 )
- Like "fast exponentiation by squares"
you may use "fast multiplication by shifting",
e.g. 10 * a == 2 * ( a + 4 * a ).

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/transitional.dtd">
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<script type="text/javascript">

var cS = 4
var cV = 1 << cS
var cM = cV - 1

function toBin ( s ) {
var a = [ 0 ]
for ( var i = 0 ; i < s.length ; i++ ) {
var b = a.concat ( [] )
shl ( a , 2 ) // a := 4 * a
add ( a , b ) // a := 5 * a
shl ( a , 1 ) // a := 10 * a
add ( a , [ '0123456789'.indexOf ( s.charAt ( i ) ) ] )
}
return a
}

function shl ( a , n ) {
var u = 0
for ( var i = 0 ; i < a.length ; i++ ) {
var t = ( a [i] << n ) + u
u = t >> cS
a [i] = t & cM
}
if ( u ) a.push ( u )
}

function add ( a , b ) { // a.length must be greater than b.length
var u = 0
for ( var i = 0 ; i < a.length ; i++ ) {
var t = a [i] + u
if ( i < b.length ) t += b [i]
else if ( ! t ) return
u = t >> cS
a [i] = t & cM
}
if ( u ) a.push ( u )
}

function pic ( n ) { return ( n + cV ) . toString ( 2 ) . substr ( 1 ) }
function toStr ( a ) {
var b = [ a [a.length-1] . toString ( 2 ) ]
for ( var i = a.length - 1 ; i ; ) b.push ( pic ( a [--i] ) )
return b.join ( '' )
}

function test () {
var a = []
for ( var i = 0 ; i < 257 ; i++ ) {
var r = toStr ( toBin ( i.toString () ) )
if ( parseInt ( r , 2 ) != i ) { alert ( i ) ; i = 999 }
a.push ( i + ' :: ' + r )
}
var t = new Date () . getTime ()
var k = toStr ( toBin ( '123456789012345678901234567890' ) )
a.push ( k + ' :: ' + ( new Date () . getTime () - t ) + 'ms' )
return a.join ( '<br>' )
}

</script>

<script type="text/javascript">
document.write ( test () )
</script>

</body></html>

regards, wz.

--
http://wzwz.de/mail/

Ken Snyder
Guest
Posts: n/a

 06-30-2010
Could you just use Number#toString(2)? Or does it mishandle negatives
and impose range limits?

(5).toString(2); // "101"
(16).toString(2); // "10000"

wolfgang zeidler
Guest
Posts: n/a

 06-30-2010
Ken Snyder wrote:
> Could you just use Number#toString(2)? Or does it mishandle negatives
> and impose range limits?
>
> (5).toString(2); // "101"
> (16).toString(2); // "10000"
>

Sorry, I'm very unsure what you mean with "Number#toString(2)".
- There is no point of mishandling negative values,
the OP showed a simplified example with
argument "n must be an unsigned string of digits only",
my example handles only arguments like /\d/+, too.
- Maybe you mean I should use
a [i] --> a [i] . toString ( 2 ) for all array elements,
but this would produce an error:
The number 16 is represented by [ 0 , 1 ],
the result of (1).toString (2) + (0).toString(2)
would be "1" + "0" = "10",
the result of (1).toString ( 2 ) + pic ( 0 )
is "1" + "0000" = "10000", as expected.

:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:-:

BTW:
Now I can see the example I wrote within ~ 1 hour contains an error.
No error which produces wrong results,
but an error which makes the example ineffective.

Old version:
function add ( a , b ) { // a.length must be greater than b.length
var u = 0
for ( var i = 0 ; i < a.length ; i++ ) {
var t = a [i] + u
if ( i < b.length ) t += b [i]
else if ( ! t ) return
//------------- ^ - not very good
u = t >> cS
a [i] = t & cM
}
if ( u ) a.push ( u )
}

New version:
function add ( a , b ) { // a.length must be greater than b.length
var u = 0
for ( var i = 0 ; i < a.length ; i++ ) {
var t = a [i] + u
if ( i < b.length ) t += b [i]
else if ( ! u ) return
//------------- ^ - should be better
u = t >> cS
a [i] = t & cM
}
if ( u ) a.push ( u )
}

RobG
Guest
Posts: n/a

 06-30-2010
On Jul 1, 5:25*am, Ken Snyder <(E-Mail Removed)> wrote:
> Could you just use Number#toString(2)? Or does it mishandle negatives
> and impose range limits?

Negatives aren't an issue, range is. I simplified the posted code as
it's the algorithm and implementation for decimal to binary that I

> (5).toString(2); *// "101"
> (16).toString(2); // "10000"

Math.pow(234, 512).toString(2); // Infinity

When computed fully, the result of the above expression has 4030
digits.

--
Rob

pete
Guest
Posts: n/a

 07-01-2010
On Jun 30, 3:25*pm, Ken Snyder <(E-Mail Removed)> wrote:

I must be missing something. What is that subtle something?

> (5).toString(2); *// "101"
> (16).toString(2); // "10000"

As I read it, the OP wants to go FROM string, not toString( ). Thus:

function toBin(n) {
return + n;
}

straight from the FAQ, should work, should it not?
[ http://www.jibbering.com/faq/notes/t...rsion/#tcParse ]

-- pete

pete
Guest
Posts: n/a

 07-01-2010
On Jul 1, 5:11*am, pete <(E-Mail Removed)> wrote:

> I must be missing something. What is that subtle something?

Answering my own question, that "subtle something" is:

> real code works with integer strings of any length

as the OP specified early, whereas my suggested solution ( binVal = +
stringVal ) only works for strings of max 10 digits, and fewer than
half of those. Sorry for missing the OP's crucial stipulation.

-- pete

Scott Sauyet
Guest
Posts: n/a

 07-01-2010
On Jun 30, 11:12*am, RobG <(E-Mail Removed)> wrote:
> I'm working on a function to convert decimal integers to binary. The
> version below is an example of my implementation of a halving
> algorithm, real code works with integer strings of any length and
> handles sign. I've reduced the functionality a bit so I don't have to
> post the supporting functions for large ints.
>
> This one only works within the range of values supported by the
> ECMAScript implementation it's running in and with unsigned integers
> (don't use numbers larger than 9 digits).

This version works with arbitrary length ints, that is on strings
containing nothing but decimal digits:

var toBin = (function() {
var digitHalves = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4],
remainderHalves = [5, 5, 6, 6, 7, 7, 8, 8, 9, 9];
return function(digits) {
digits = digits.split("");
var binDigits = [];
while (digits.length) {
var ptr = 0, digit = 0;
while (digits[0] == '0') digits.shift();
while (ptr < digits.length) {
var carry = digit
digit = digits[ptr] % 2;
digits[ptr] = carry ? remainderHalves[digits[ptr]]
: digitHalves[digits[ptr]];
ptr++;
}
binDigits.push(digit);
}
binDigits.reverse().shift();
return binDigits.join("");;
};
}());

I have not tested performance. It's performing division digit-by-
digit, via lookups, so I wouldn't be surprised if it's slow. But it
seems to be straightforward. The two lookups, digitHalves and
remainderHalves respectively return half of the current digit and half
of ten more than the current digit, in either case rounded down to the
nearest digit. It does avoid a division...

--
Scott

Dr J R Stockton
Guest
Posts: n/a

 07-01-2010
In comp.lang.javascript message <cc0324be-9889-4ec7-b673-27c06cb50e83@b4
g2000pra.googlegroups.com>, Wed, 30 Jun 2010 08:12:20, RobG
<(E-Mail Removed)> posted:

>I'm working on a function to convert decimal integers to binary. The
>version below is an example of my implementation of a halving
>algorithm, real code works with integer strings of any length and
>handles sign. I've reduced the functionality a bit so I don't have to
>post the supporting functions for large ints.
>
>This one only works within the range of values supported by the
>ECMAScript implementation it's running in and with unsigned integers
>(don't use numbers larger than 9 digits).
>
>Anyhow, I remember working on something similar that used a bitwise
>operator (around August 2006?) but I can't find it in the archives.
>This one seems a bit long and is likely a bit slow, can anyone suggest
>some optimisation tips?

You can probably find it somewhere on my Web site. Try the beginning of
the code at <URL:http://www.merlyn.demon.co.uk/js-maths.htm#BEA>.

Take the de-signed integer string, split into characters, convert each
to a digit Number. Repeatedly halve until it vanishes, pushing each
remainder. Now reverse that array, and add the sign.

I feel that splitting into characters is better than chipping them off
one at a time; untested. But strings are more easily "copied".

> // Trivial cases
> if (n == '0' || n == '1') {
> return n;
> }

Trivial cases should if possible be handled generally in the first
instance, since they are easy to debug.

> // Get last digit
> d = n.substring(len);

or with charAt or charCodeAt ?

>Incidentally, I'm working on an unlimited precision integer library.
>I've done +, -, *, pow, toBinary and a few others, once it's working
>properly I'll post the interesting bits.

Divide?

If you write it compatibly with Windows Script Host, you could automatically
compare your results with those from longcalc.

Look at my longcalc.pas, via sig line 3. Precision is not unlimited, but
65000 or 99999999 digits (base 2 to 16) may be enough.

C:\HOMEPAGE>longcalc 16 bas 0123 fac #ge wrt wrt

LONGCALC: www.merlyn.demon.co.uk >= 2005-07-22
compiled with Borland Delphi.
+4 +9

So Gregorian Easter Sunday of the year 0x123, calculated in Hex, is April
9th. In fact, it is April 9th for any factorial year from factorial 25
upwards.

>The pow function uses fast exponentiation by squares, which is pretty
>efficient

...

Squaring is multiplication. From my longcalc.pas :

function Times(const X, Y : Arr ; var Z : Parr) : boolean ;
{ This is standard manual method; there are faster ones, for large numbers,
in ALGORITHMICS by Brassard & Bratley, ISBN 0-13-023169-X (NML) }

Googling for Brassard & Bratley leads, it seems, to a PDF of the book.

--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk DOS 3.3, 6.20; WinXP.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
PAS EXE TXT ZIP via <URL:http://www.merlyn.demon.co.uk/programs/00index.htm>
My DOS <URL:http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.

RobG
Guest
Posts: n/a

 07-02-2010
On Jul 2, 7:44*am, Dr J R Stockton <(E-Mail Removed)>
wrote:
> In comp.lang.javascript message <cc0324be-9889-4ec7-b673-27c06cb50e83@b4
> g2000pra.googlegroups.com>, Wed, 30 Jun 2010 08:12:20, RobG
> <(E-Mail Removed)> posted:

[...]
> >Anyhow, I remember working on something similar that used a bitwise
> >operator (around August 2006?) but I can't find it in the archives.
> >This one seems a bit long and is likely a bit slow, can anyone suggest
> >some optimisation tips?

>
> You can probably find it somewhere on my Web site. *Try the beginning of
> the code at <URL:http://www.merlyn.demon.co.uk/js-maths.htm#BEA>.

I couldn't find it, but I think it was no more useful than
<number>.toString(2).

> Take the de-signed integer string, split into characters, convert each
> to a digit Number. *Repeatedly halve until it vanishes, pushing each
> remainder. *Now reverse that array, and add the sign.

Yes, that is about the only algorithm that I've found. It's pretty
obvious so I thought there must be a better way. Stefan's
implementation is much more efficient than mine, Scott's is a little
slower (than Stefan's).

I haven't had time to fully digest Wolfgang's post yet.

> I feel that splitting into characters is better than chipping them off
> one at a time; untested. *But strings are more easily "copied".

I'll do some testing of charAt vs splitting.

>
> > * * *// Trivial cases
> > * * *if (n == '0' || n == '1') {
> > * * * *return n;
> > * * *}

>
> Trivial cases should if possible be handled generally in the first
> instance, since they are easy to debug.

Yes, it's a useless optimisation - speed isn't an issue in these
cases.

>
> > * * * *// Get last digit
> > * * * *d = n.substring(len);

>
> or with charAt or charCodeAt ?
>
> >Incidentally, I'm working on an unlimited precision integer library.
> >I've done +, -, *, pow, toBinary and a few others, once it's working
> >properly I'll post the interesting bits.

>
> Divide?

Not yet, time is an issue.

[...]
> >The pow function uses fast exponentiation by squares, which is pretty
> >efficient

>
> *...
>
> Squaring is multiplication. *From my longcalc.pas :
>
> function Times(const X, Y : Arr ; var Z : Parr) : boolean ;
> { This is standard manual method; there are faster ones, for large numbers,
> * in ALGORITHMICS by Brassard & Bratley, ISBN 0-13-023169-X (NML) }
>
> Googling for * Brassard & Bratley * leads, it seems, to a PDF of the book.

Thanks, I'm currently using standard long multiplication which works
fine but is likely slow. I've come across windowing as mentioned by
Wolfgang but again, need time to absorb it all.

--
Rob