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 6 Jul 2010 15:56 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. Since I don't want the page to be indexed, the following link is in ROT- 13; but the only un-guessable part is "base-cnv". Temporary page <HEY:uggc://jjj.zreyla.qrzba.pb.hx/onfr-pai.ugz> demonstrates conversion of a signed fixed-point numeric String from any integer base greater than 1 to any other such base, and back. The number of fractional digits in the result is just such that the LSB of the LSD of the result is worth no more than the LSB of the LSD of the input. At present, the result is truncated rather than rounded, alas. The method of converting between digit character and Number allows easy conversion to any ordered set of digits, the default being as many as are needed of 0-9a-z. So the greatest radix of the algorithm (in JavaScript) is presumably 65536. The length of the strings is unbounded (there is no internal conversion of the whole input to a single Number) but the code assumes (at present) that the LSB of the input is worth no less than the smallest non-zero Number. It is all very greatly under-tested. -- (c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05. Web <URL:http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms PAS EXE etc : <URL:http://www.merlyn.demon.co.uk/programs/> - see 00index.htm Dates - miscdate.htm estrdate.htm js-dates.htm pas-time.htm critdate.htm etc.
From: RobG on 7 Jul 2010 00:06 On Jul 6, 10:54 pm, Richard Cornford <Rich...(a)litotes.demon.co.uk> wrote: > On Jul 6, 3:29 am, Stefan Weiss wrote: [...] > <snip>> I couldn't find a way to try out the "substract 3" suggestion > > without introducing at least one if-statement. > > <snip> > > What is wrong with the - if - statement? Nothing, if it's faster than the alternative (and it is). Using the shift operator is easily the fastest way to divide and round, that was simple to implement. However, your suggestion of adding high bits and subtracting 3 had me tossed for a while but then I realised it's the same as right-shift then add 5. That didn't help (or hinder) IE but did help Firefox. The version below has what seem to be the best optimisations from previous suggestions tested in IE 6 and Firefox. It is nearly the fastest in IE and easily the fastest (so far) in Firefox. It uses a combination of array and string methods, the fastest were selected based on tests in the two browsers mentioned. I'll test more widely later. Optimisations worth mentioning are: 1. IE much prefers storing values to indexed lookups - even removing one lookup had a big effect. 2. Replacing the if statement with a ternary operator is very slow in IE, so more code is faster in this case. 3. Replacing the if statement to see if offset needed incrementing with a type-conversion assignment made not much difference in IE but really helped Firefox, i.e. the line: offset += !bigInt[offset]; Hopefully conversion from Boolean to number is robust (though JRS's comments about the vagaries of number.toString(radix) have me worried). var toBin = function(numStr) { var bigInt = numStr.split(""), len = bigInt.length, result = "", offset = 0, rem, divPart, i, n; do { // Progressively halve number one digit at a time for (rem=0, i=offset; i < len; ++i) { n = bigInt[i]; // If previous digit was odd, halve this number // and round down (trim rh bit) and add 5 if (rem) { bigInt[i] = (n >>> 1) + 5; // Otherwise, just halve (trim rh bit) } else { bigInt[i] = n >>> 1; } // Remember if this digit was odd for next loop rem = n & 1; } // If digit is now zero, move to next offset += !bigInt[offset]; // Prepend 1 to result if number was odd, otherwise 0 result = rem + result; } while (offset < len); return result; }; -- Rob
From: Stefan Weiss on 7 Jul 2010 10:00 On 07/07/10 06:06, RobG wrote: > On Jul 6, 10:54 pm, Richard Cornford <Rich...(a)litotes.demon.co.uk> > wrote: >> On Jul 6, 3:29 am, Stefan Weiss wrote: > [...] >> <snip>> I couldn't find a way to try out the "substract 3" suggestion >> > without introducing at least one if-statement. >> >> <snip> >> >> What is wrong with the - if - statement? > > Nothing, if it's faster than the alternative (and it is). [...] > However, your suggestion of adding high bits and > subtracting 3 had me tossed for a while but then I realised it's the > same as right-shift then add 5. That didn't help (or hinder) IE but > did help Firefox. That would appear to depend on the Firefox version. Avoiding the if-statement actually improved performance in my stand-alone SpiderMonkey versions (tested 1.7.0 and 1.8.0rc1). The JS engine in current Firefox versions may give different results, possibly as a result of JIT compilation. On the other hand, the trunk version of V8 also runs the code (marginally) faster when there is no "if" statement in the "for" loop. > The version below has what seem to be the best optimisations from > previous suggestions tested in IE 6 and Firefox. It is nearly the > fastest in IE and easily the fastest (so far) in Firefox. It uses a > combination of array and string methods, the fastest were selected > based on tests in the two browsers mentioned. I'll test more widely > later. The IE results are interesting, thank you. I didn't bother to run the tests in a browser, but a general implementation should still run fast enough in IE 6/7. > 3. Replacing the if statement to see if offset needed incrementing > with a type-conversion assignment made not much difference in IE but > really helped Firefox, i.e. the line: > > offset += !bigInt[offset]; Interesting. I saw the opposite effect in V8 and SpiderMonkey. > Hopefully conversion from Boolean to number is robust (though JRS's > comments about the vagaries of number.toString(radix) have me > worried). I don't think those problems are related to the toBin() function. > var toBin = function(numStr) { [snip code] I think we're well into the area of engine specific optimizations now. The version I posted still runs fastest for me on the command line, but your tests in IE and Firefox should make your version a better compromise on the web. One positive side effect of this exercise was to finally bring me to update my outdated JavaScript 1.7 interpreter to 1.8.0rc1. That's the latest stand-alone release I could find; I wasn't able to locate non-browser versions of TraceMonkey or JaegerMonkey. I also installed Chrome's V8 engine. It completely outclassed the non-JIT SpiderMonkey, running the toBin() tests about 10x faster. -- stefan
From: Richard Cornford on 7 Jul 2010 19:36 Stefan Weiss wrote: > On 07/07/10 06:06, RobG wrote: >> On Jul 6, 10:54 pm, Richard Cornford wrote: <snip> >> However, your suggestion of adding high bits and >> subtracting 3 had me tossed for a while but then I realised >> it's the same as right-shift then add 5. That didn't help >> (or hinder) IE but did help Firefox. > > That would appear to depend on the Firefox version. Avoiding the > if-statement actually improved performance in my stand-alone > SpiderMonkey versions (tested 1.7.0 and 1.8.0rc1). <snip> There is a possibility that hardware (CPU type, cache size, memory speed, effective memory bus width, etc.) could be having an influence. It was once observed here that, running on the same browser/version and OS, string comparison was faster than the equivalent simple regular expression test running on a PIII, but the regular expression (unexpectedly) proved faster on a P4. This has been attributed to the influence of longer pipeline on the P4. Regardless of the specific explanation in that case, it doe demonstrate that hardware can reverse the outcome of comparative timings when dealing with javascript. Richard.
From: RobG on 7 Jul 2010 22:27
On Jul 8, 12:00 am, Stefan Weiss <krewech...(a)gmail.com> wrote: > On 07/07/10 06:06, RobG wrote: [...] > > However, your suggestion of adding high bits and > > subtracting 3 had me tossed for a while but then I realised it's the > > same as right-shift then add 5. That didn't help (or hinder) IE but > > did help Firefox. > > That would appear to depend on the Firefox version. Avoiding the > if-statement actually improved performance in my stand-alone > SpiderMonkey versions (tested 1.7.0 and 1.8.0rc1). The JS engine in > current Firefox versions may give different results, possibly as a > result of JIT compilation. On the other hand, the trunk version of V8 > also runs the code (marginally) faster when there is no "if" statement > in the "for" loop. [...] > I think we're well into the area of engine specific optimizations now. Yes. I ran several versions in Safari 5.0 and they were all about the same, say +/- 5%. All of them were about 5x faster than the fastest in Firefox 3.5. I also tested against one of the BigInt.js libraries[1] mentioned in another thread. It has a general conversion to any base that takes twice as long as the bespoke version here for conversion to base 2. Unfortunately the one I used is restricted to strings of 16 digits or less, so it's not really suited to the library's goal of being "a bigInt library for arbitrary-precision integers". 1. There appears to be more than one of these, I used this one: <URL: http://www.leemon.com/crypto/BigInt.js > But later I found this one: <URL: http://www.onicos.com/staff/iz/amuse/javascript/expert/BigInt.txt > -- Rob |