Prev: Discount Lacoste Coat
Next: FAQ Topic - How do I make a suggestion? (2010-07-14)
From: Dr J R Stockton on 13 Jul 2010 18:46
Recent threads about errors in implementations of Number.toString(Radix)
and the lack of an ECMA parseFloat(String, Radix) are now probably lost
to most of you among the spam; hence this new one.

I have a new page <URL:http://www.merlyn.demon.co.uk/js-exact.htm>. It
currently contains a list of links to those sections of the site which
deal with Exact Arithmetic and Strings; in time, I intend to move those
parts into the page (page js-maths.htm, at least, is now too long). The
list is currently :-

* JavaScript Maths :-
o Some Exact Conversions :-
+ Fixed-Point Radix String to Number
+ Fixed-Point Radix String to Another Radix
* JavaScript Miscellany 0 :-
o Bit Representations of Number :-
+ Number to Four Bytes as Int32 or Dword
+ Float Conversion and Demonstration Code :-
# This Code
# These Forms
# Number to Four Bytes as IEEE Single and Back
# Number to Four Words as IEEE Double and Back

The code does not use the major ECMA Global Functions, just simple exact
integer operations on Numbers, and so is very probably free of imported
bugs and browser dependencies. It does not consider exponents in the
strings. It is intended to be accurate. It is not intended to be fast.

Fixed-Point Radix String to Number should always give the nearest
Number, with the half-way case being rounded away from zero. It can be
used for testing versions previously presented here in CLJ.

Fixed-Point Radix String to Another Radix keeps adding digits after the
radical point until the least significant bit of the least significant
digit is worth less than the LSB of the LSD of the input.

--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE8 FF3 Op10 Sf4 Cr4
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
From: RobG on 14 Jul 2010 23:11
On Jul 14, 8:46 am, Dr J R Stockton <reply1...(a)merlyn.demon.co.uk>
wrote:
[...]
> I have a new page <URL:http://www.merlyn.demon.co.uk/js-exact.htm>. It
> currently contains a list of links to those sections of the site which
> deal with Exact Arithmetic and Strings; in time, I intend to move those
> parts into the page (page js-maths.htm, at least, is now too long). The
> list is currently :-
>
> * JavaScript Maths :-
> o Some Exact Conversions :-
> + Fixed-Point Radix String to Number
> + Fixed-Point Radix String to Another Radix
> * JavaScript Miscellany 0 :-
> o Bit Representations of Number :-
> + Number to Four Bytes as Int32 or Dword
> + Float Conversion and Demonstration Code :-
> # This Code
> # These Forms
> # Number to Four Bytes as IEEE Single and Back
> # Number to Four Words as IEEE Double and Back
>
> The code does not use the major ECMA Global Functions, just simple exact
> integer operations on Numbers, and so is very probably free of imported
> bugs and browser dependencies. It does not consider exponents in the
> strings. It is intended to be accurate. It is not intended to be fast.

I have discovered and played a bit with a couple of integer arithmetic
libraries. My biggest gripe is that none have any code comments or
documentation of the algorithms used and extremely limited user
documentation.

Onicos BigInt.js:
<URL: http://www.onicos.com/staff/iz/amuse/javascript/expert/BigInt.txt
>
Does limited simple mathematics and has a version of the seemingly
pervasive power modulation function. Limited (almost non-existent)
documentation.

Leemon BigInt.js
<URL: http://www.leemon.com/crypto/BigInt.js >
Does everything the one above does and a bit more. Limited
documentation, it is a bit of a chore trying to work out how to use
it. It's very easy to use incorrectly.

biBigInt.js
<URL: http://code.google.com/p/bi2php/ >
Seems to be a version of the Leemon BigInt.js with wrapper and extra
bits for cryptography. Again, very limited documentation

As for speed, the decimal to binary function developed here is faster
than any of the above. I've developed a simple big integer
multiplication function using a window approach that is as fast or
faster than the above (it gets faster the bigger the number), same for
a power function. I hope to do the same with division when time allows
- I'm currently doing long division by subtraction, it works quite
well but is a little slow.

My goal is to develop a large integer library with fully explained
algorithms, extensive code comments and useful user documentation.

Going through the code of the above libraries, there seems to be many
misconceptions about how ECMAScript works, particularly with regard to
memory allocation and initialising arrays. Some seem to think that
setting an array length before filling it is faster than initialising
a zero length array and just filling it, and that access to global
variables is faster than local (and somehow optimises memory
allocation). I'm not sure that any of these ideas has any credence,
particularly as initialising an array is but one step in a function
that likely has hundreds of loops and therefore is insignificant for
performance.

As an aside, I wanted to create strings of zeros of specific lengths.
I though the following approach would be fast:

function genZeros(n) {
var x = new Array(n + 1);
return x.join('0')'
}

It isn't, it's very much slower than:

function genZeros(n) {
var s = '0000000000';
while (s.length < n) {
s += s;
}
return s.substring(0, n);
}


--
Rob
From: Stefan Weiss on 15 Jul 2010 07:58
On 15/07/10 05:11, RobG wrote:
[bigint libraries]
> Going through the code of the above libraries, there seems to be many
> misconceptions about how ECMAScript works, particularly with regard to
> memory allocation and initialising arrays. Some seem to think that
> setting an array length before filling it is faster than initialising
> a zero length array and just filling it,

It's been a while since I tested it, but ~2 years ago, that was actually
true for the major browsers. If you provide a length parameter to "new
Array()", the array object's .length property will not need to be
adjusted for the first (length -1) inserted elements.

This was also also discussed here. IIRC, some engines used different
optimizations when an array is created with "new Array(length)",
depending on the size of the "length" parameter. Make it large enough,
and the engine will prepare for a sparse array. Make it smaller, and the
engine may preallocate some memory for the elements. I don't remember
the numbers, and they're probably out of date now, anyway.

> I'm not sure that any of these ideas has any credence,
> particularly as initialising an array is but one step in a function
> that likely has hundreds of loops and therefore is insignificant for
> performance.

It likely depends on how many elements there are going to be.

> As an aside, I wanted to create strings of zeros of specific lengths.
> I though the following approach would be fast:
>
> function genZeros(n) {
> var x = new Array(n + 1);
> return x.join('0')'
> }
>
> It isn't, it's very much slower than:
>
> function genZeros(n) {
> var s = '0000000000';
> while (s.length < n) {
> s += s;
> }
> return s.substring(0, n);
> }

This can be optimized further. Here's a copy/pasted example of a
repeat() method from my old not-really-a-library:

String.prototype.repeat = function (n) {
// The algorithm below is ~33 bytes longer (minified), but
// a lot more efficient than our previous version:
// return n < 1 ? "" : new Array(n + 1).join(this);
var res = "",
s = this;
while (n > 0) {
if (n % 2) {
res += s;
}
if (n > 1) {
s += s;
}
n = n >> 1;
}
return res;
};


--
stefan
From: RobG on 16 Jul 2010 01:27
On Jul 15, 9:58 pm, Stefan Weiss <krewech...(a)gmail.com> wrote:
> On 15/07/10 05:11, RobG wrote:
> [bigint libraries]
>
> > Going through the code of the above libraries, there seems to be many
> > misconceptions about how ECMAScript works, particularly with regard to
> > memory allocation and initialising arrays. Some seem to think that
> > setting an array length before filling it is faster than initialising
> > a zero length array and just filling it,
>
> It's been a while since I tested it, but ~2 years ago, that was actually
> true for the major browsers. If you provide a length parameter to "new
> Array()", the array object's .length property will not need to be
> adjusted for the first (length -1) inserted elements.
>
> This was also also discussed here. IIRC, some engines used different
> optimizations when an array is created with "new Array(length)",
> depending on the size of the "length" parameter. Make it large enough,
> and the engine will prepare for a sparse array. Make it smaller, and the
> engine may preallocate some memory for the elements. I don't remember
> the numbers, and they're probably out of date now, anyway.
>
> > I'm not sure that any of these ideas has any credence,
> > particularly as initialising an array is but one step in a function
> > that likely has hundreds of loops and therefore is insignificant for
> > performance.
>
> It likely depends on how many elements there are going to be.
>
>
>
> > As an aside, I wanted to create strings of zeros of specific lengths.
> > I though the following approach would be fast:
>
> >   function genZeros(n) {
> >     var x = new Array(n + 1);
> >     return x.join('0')'
> >   }
>
> > It isn't, it's very much slower than:
>
> >   function genZeros(n) {
> >     var s = '0000000000';
> >     while (s.length < n) {
> >       s += s;
> >     }
> >     return s.substring(0, n);
> >   }
>
> This can be optimized further. Here's a copy/pasted example of a
> repeat() method from my old not-really-a-library:
>
>     String.prototype.repeat = function (n) {
>         // The algorithm below is ~33 bytes longer (minified), but
>         // a lot more efficient than our previous version:
>         //    return n < 1 ? "" : new Array(n + 1).join(this);
>         var res = "",
>             s = this;
>         while (n > 0) {
>             if (n % 2) {
>                 res += s;
>             }
>             if (n > 1) {
>                 s += s;
>             }
>             n = n >> 1;
>         }
>         return res;
>     };

It is a bit slower IE 6, and much slower in Firefox, but genZeros only
creates strings of zeros so a bit limited. A general function (i.e.
not limited to zeros) based on the same idea is:

function genChar(c, n) {
var s = c + c + c;
while (s.length < n) {
s += s;
}
return s.substring(0, n);
}

That seems to be about the same speed as repeat() in IE 6, but it's
much faster in Firefox (25% or so). But how often to you need to
generate strings of 10,000 identical characters? :-)


--
Rob
From: Dr J R Stockton on 16 Jul 2010 18:13
In comp.lang.javascript message <b6baa14d-1098-4ca1-b86c-ae6128d4d194(a)x2
4g2000pro.googlegroups.com>, Wed, 14 Jul 2010 20:11:42, RobG
<rgqld(a)iinet.net.au> posted:

>As an aside, I wanted to create strings of zeros of specific lengths.

We discussed something like that a while ago; see
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#MLS>. In FF 3.0.19,
BigCat beats Wombat.

--
(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)
 |  Next  |  Last
Pages: 1 2
Prev: Discount Lacoste Coat
Next: FAQ Topic - How do I make a suggestion? (2010-07-14)