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: Dr J R Stockton on 1 Jul 2010 17:44 In comp.lang.javascript message <cc0324be-9889-4ec7-b673-27c06cb50e83(a)b4 g2000pra.googlegroups.com>, Wed, 30 Jun 2010 08:12:20, RobG <rgqld(a)iinet.net.au> 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.
From: RobG on 2 Jul 2010 07:50 On Jul 2, 7:44 am, Dr J R Stockton <reply1...(a)merlyn.demon.co.uk> wrote: > In comp.lang.javascript message <cc0324be-9889-4ec7-b673-27c06cb50e83(a)b4 > g2000pra.googlegroups.com>, Wed, 30 Jun 2010 08:12:20, RobG > <rg...(a)iinet.net.au> 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
From: Richard Cornford on 2 Jul 2010 08:22 On Jul 1, 10:44 pm, Dr J R Stockton wrote: > On Wed, 30 Jun 2010 08:12:20, RobG wrote: >> // Get last digit >> d = n.substring(len); > > or with charAt or charCodeAt ? <snip> If the characters in the string are all decimal digits, and each character is going to have to be type-converted to a number, then I like the sound of - charCodeAt - as that give a number that can simply be modified into the equivalent of the number represented by the digit, by subtracting 48 or masking out all but the lower 4 bits. Richard.
From: Dr J R Stockton on 2 Jul 2010 15:54 In comp.lang.javascript message <8f14b511-0b7d-4df0-a7b5-50b1c9aae810(a)16 g2000prp.googlegroups.com>, Wed, 30 Jun 2010 12:25:43, Ken Snyder <kendsnyder(a)gmail.com> posted: >Could you just use Number#toString(2)? Or does it mishandle negatives >and impose range limits? > >(5).toString(2); // "101" >(16).toString(2); // "10000" In one current browser, Math.random().toString(2) ends, about half of the time, in a "digit" 2. In almost all of the less popular radixes R, about 1/Rth of the time the last digit can be the radix. In Radix 36 it can be { and for radixes over 10 it can be : . Some other browsers return, for some radixes, many more digits than the IEEE Double input justifies. <URL:http://www.merlyn.demon.co.uk/js-maths.htm#TtSR> refers, and provides a tester for your current browser. JavaScript built-in functions and methods should not be trusted to be always right in unusual but legitimate circumstances in all browsers. -- (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME. Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links; Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc. No Encoding. Quotes before replies. Snip well. Write clearly. Don't Mail News.
From: Dr J R Stockton on 2 Jul 2010 16:08
In comp.lang.javascript message <ee4880d1-f362-4d94-8b52-61660e6620cf(a)d3 7g2000yqm.googlegroups.com>, Thu, 1 Jul 2010 09:44:06, Scott Sauyet <scott.sauyet(a)gmail.com> posted: > >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... > On a modern machine, say post-1990, division is fast. Perhaps not quite as fast as multiplication, but still fast. In a JavaScript-like language, where complete compilation is impossible, the engine will, I believe, spend most of its time working out what to do rather than actually doing it. It should be easy to compare your code for speed with an otherwise matching version using only arithmetic operations. ISTM that your "digits" is (mostly) an array of characters '0' to '9' and that those are used repeatedly. If so, a single pass converting them from characters to digits may be worth adding. That step can handle conversion from other radixes. -- (c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton(a)physics.org Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. Correct <= 4-line sig. separator as above, a line precisely "-- " (RFC5536/7) Do not Mail News to me. Before a reply, quote with ">" or "> " (RFC5536/7) |