Decimal to Binary
in [JavaScript]
|
Prev: FAQ Topic - How do I open a new window with javascript? (2010-06-30)
Next: How to trigger two events with 2 document.locations?
From: RobG on 30 Jun 2010 11:12 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
From: wolfgang zeidler on 30 Jun 2010 15:09 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"> <html><head><title>???</title> <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> </head><body> <script type="text/javascript"> document.write ( test () ) </script> </body></html> regards, wz. -- http://wzwz.de/mail/
From: Ken Snyder on 30 Jun 2010 15:25 Could you just use Number#toString(2)? Or does it mishandle negatives and impose range limits? (5).toString(2); // "101" (16).toString(2); // "10000"
From: wolfgang zeidler on 30 Jun 2010 16:23 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 ) }
From: RobG on 30 Jun 2010 19:37
On Jul 1, 5:25 am, Ken Snyder <kendsny...(a)gmail.com> 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 care about. > (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 |