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 3 Jul 2010 15:38 In comp.lang.javascript message <0cdbd421-8cbe-43fd-8e28-67b1e6f78343(a)b2 9g2000vbl.googlegroups.com>, Fri, 2 Jul 2010 05:22:37, Richard Cornford <Richard(a)litotes.demon.co.uk> posted: >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. But charAt can also be easily used : Digits = "0123456789abcdefghijklmnopqrstuvwxyz" var Num = [], K = IN.length while (J < K) { Tmp = IN.charAt(J++) Tmp = Digits.indexOf(Tmp.toLowerCase()) if (Tmp < 0 || Tmp >= Rdx) break Num.push(Tmp) } // array now holds digit Numbers That looks longer than what you were no doubt thinking of; but it does rather more. A rough test suggests yours is only 3 times quicker for decimal numbers, and it will be slowed if Hex is considered. I suggest that we, the regulars, decide never to use more than 72 characters in an article Subject line here. Those with good newsreaders can then automatically math articles with long Subjects as uninteresting. so that they sink to the bottom or whatever. A glance at the apparent dross will soon spot any that are actually good, including out own routine automated posts.. -- (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05 IE 7. Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. Command-prompt MiniTrue is useful for viewing/searching/altering files. Free, DOS/Win/UNIX now 2.0.6; see <URL:http://www.merlyn.demon.co.uk/pc-links.htm>.
From: Dr J R Stockton on 3 Jul 2010 17:27 In comp.lang.javascript message <8b4584b8-98dc-4a43-8197-08dc32c992de(a)z3 4g2000pro.googlegroups.com>, Fri, 2 Jul 2010 04:50:54, RobG <rgqld(a)iinet.net.au> posted: >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). But <number>.toString(2) is only for those who don't use Opera or don't mind a '2' at the end if <number> is non-integer. This is what I was referring to : // Process integer part : while (J = Int.length) { // not == for (K=0, Cy=0 ; K<J ; K++) { Tmp = Cy * Rdx + Int[K] ; Cy = Tmp % 2 ; Int[K] = (Tmp-Cy) / 2 } Bin.push(Cy) if (Int[0] == 0) Int.shift() } Bin.reverse() >> >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. Additionally: my program longcalc just grew from a simple program to check the alleged factorisation of F9, which is why it handles only integers. I rather regret that. If I were starting again, I'd make it at least fixed-point and maybe floating-point. If you might want to change away from integer, do it as soon as possible. That <URL:http://www.merlyn.demon.co.uk/js-maths.htm#BEA> now appears to be good, and mostly optimised as far as seems reasonable. -- (c) John Stockton, nr London UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME. Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. Proper <= 4-line sig. separator as above, a line exactly "-- " (RFCs 5536/7) Do not Mail News to me. Before a reply, quote with ">" or "> " (RFCs 5536/7)
From: Stefan Weiss on 3 Jul 2010 21:13 On 03/07/10 20:25, Richard Cornford wrote: > RobG wrote: > On Jul 2, 7:44 am, Dr J R Stockton wrote: > <snip> >>>> // Get last digit >>>> d = n.substring(len); >>> >>> or with charAt or charCodeAt ? > > While thinking about the (probably not coincidental) fact that - > (data.charCodeAt(x) & 0xF) - would result in the number corresponding > with the digit (assuming there is a digit at that index), that the > number is the lower four bits of the character code, I was reminded that > Binary Coded Decimal (BCD) uses four bit (nibble) units to store > representations of decimal digits, and then reminded that there was a > well known (so easily looked up) algorithm for converting serialised BCD > input into binary integers. that algorithm is geared towards assembly > langue implementation on relatively simple processors and so uses > shifting, masking and subtraction (avoiding the multiplication and > division that can be a bit expensive/inconvenient if you only have 8 bit > registers and no FPU). Using my test input strings, your version is significantly faster than mine (about 20%). I haven't investigated if that improvement is due to the use of binary operators or the algorithm itself. Possibly both. I suspect (without having anything like a proof) that binary operations on JS numbers are not necessarily as fast as might be expected - at least compared to languages where these operations translate (more or less) directly into processor instructions, like C. It depends very much on the how the script engine handles these operations. The version I posted wasn't optimized in any way. I posted it as soon as it passed my test script. It might be possible to improve its performance by eliminating the split() and one (or even both) of the arrays. Maybe I'll find some time to look into that next week. If anybody else wants to play around with this in the meantime, here are my test scripts: http://foo.at/paste/2010/cljs/binary/inputs.js http://foo.at/paste/2010/cljs/binary/test.js http://foo.at/paste/2010/cljs/binary/bench.js http://foo.at/paste/2010/cljs/binary/$name.js where $name is one of robg, wolfgang, scott, stefan, or richard. They were intended to be used like cat $name.js inputs.js test.js | js cat $name.js inputs.js bench.js | js or similar, depending on your setup. In my case, "js" is a stand-alone SpiderMonkey executable, which has a print() function. You may need to adjust this for other environments. > function toBin(numStr){ > var bt, c, result = []; > var lastIndex, bigInt, off; > if((lastIndex = data.length)){ Should be numStr.length instead of data.length. -- stefan
From: Richard Cornford on 4 Jul 2010 09:03 Stefan Weiss wrote: > On 03/07/10 20:25, Richard Cornford wrote: >> RobG wrote: >> On Jul 2, 7:44 am, Dr J R Stockton wrote: >> <snip> >>>>> // Get last digit >>>>> d = n.substring(len); >>>> >>>> or with charAt or charCodeAt ? >> >> While thinking about the (probably not coincidental) fact that - >> (data.charCodeAt(x) & 0xF) - would result in the number >> corresponding with the digit (assuming there is a digit at that >> index), that the number is the lower four bits of the character >> code, I was reminded that Binary Coded Decimal (BCD) uses four bit >> (nibble) units to store representations of decimal digits, and >> then reminded that there was a well known (so easily looked up) >> algorithm for converting serialised BCD input into binary integers. >> that algorithm is geared towards assembly langue implementation on >> relatively simple processors and so uses shifting, masking and >> subtraction (avoiding the multiplication and division that can be >> a bit expensive/inconvenient if you only have 8 bit registers and >> no FPU). > > Using my test input strings, your version is significantly faster > than mine (about 20%). I haven't investigated if that improvement > is due to the use of binary operators or the algorithm itself. > Possibly both. I was expecting to see more bitwise operators used in the previous examples. For example, - (digit / 2) | 0 -, where the OR zero is being used to truncate the result of the division, could be replaced with - digit >> 1 - or - digit >>> 1 -, which are effectively division by 2 with the result truncated to an integer. Not a universal replacement but what we already known about the possible values of - digit - in this case makes the substitution viable here. I suspect the algorithm itself would help as even if multiplication and subtraction are both applied to double precision floating point values and carried out directly by the FPU the multiplication can be expected to take a few more clock cycles. So correcting by subtracting 3 over multiplying by 10 should have advantages. A potential/possible optimisation that I considered was replacing the - if(x & 0x1){ ... - tests with looking up whether the number had its lowest bit set in an object such as:- var lowBitSet = { "1":true, "3":true, "5":true, "7":true, "9":true, "11":true, "13":true, "15":true }; So with - if( lowBitSet[ x ] ){ ... -. I decided not to bother when I decided that the - results - array would be easier to handle if it were an array of numbers rather than strings (so I could use the numeric result of (x & 0x1) directly rather than to decide which digit string to use). I wouldn't expect to see a big difference, but maybe ... > I suspect (without having anything like a proof) that binary > operations on JS numbers are not necessarily as fast as might > be expected - at least compared to languages where these > operations translate (more or less) directly into processor > instructions, like C. It depends very much on the how the script > engine handles these operations. Yes, and the fact that javascript number are double precision floating point values while bitwise operators act on 32 bit integers implies a translation step that should not be necessary when maths operations are being applied to the number values by a FPU (Floating Point Units usually being designed to take IEEE floating point formats as input directly). On the other hand, in the past when comparing performance when substituting bitwise operations for maths operations (and/or method calls) the bitwise operator version have proved much fester (how much faster has varied with the environment). <snip> >> function toBin(numStr){ >> var bt, c, result = []; >> var lastIndex, bigInt, off; >> if((lastIndex = data.length)){ > > Should be numStr.length instead of data.length. Yes it should. I wrote mine outside a function, and then wrapped it in a - toBin - to render it easy to compare with other's. I should have changed that - data- to - numStt -, and it didn't error because the environment outside the function during testing still contained the original - data - strings (which were by that time being passed as arguments to - toBin -. Richard.
From: Dr J R Stockton on 4 Jul 2010 11:38
In comp.lang.javascript message <18ednU5qxLotHbLRnZ2dnUVZ7oWdnZ2d(a)gigane ws.com>, Sat, 3 Jul 2010 19:25:50, Richard Cornford <Richard(a)litotes.demon.co.uk> posted: > >In a javascript implementation there is no point in attempting to get >the individual digits into consecutive nibbles, but each digit in an >array can be treated as if it was a BCD nibble. It turned out that >charCodeAt was not useful as the application of the bitwise operations >soon turns all the string digits into the corresponding numbers. It would be better than it is if it worked. Replacing a 'data' with 'numStr' may be all that is needed. But how does its speed compare? Binary operations require conversion to 32-bit integer and back, unlike arithmetic ones. -- (c) John Stockton, nr London UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME. Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links. Proper <= 4-line sig. separator as above, a line exactly "-- " (RFCs 5536/7) Do not Mail News to me. Before a reply, quote with ">" or "> " (RFCs 5536/7) |