Exact Arithmetic and Strings

D

Dr J R Stockton

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.
 
R

RobG

On Jul 14, 8:46 am, Dr J R Stockton <[email protected]>
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.txtDoes 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);
}
 
R

RobG

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? :)
 
D

Dr J R Stockton

In comp.lang.javascript message <[email protected]
rlyn.invalid>, Tue, 13 Jul 2010 23:46:09, Dr J R Stockton
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.

ISTM time to show this, from
<URL:http://www.merlyn.demon.co.uk/js-exact.htm>, where it is tested.
Essentially, it is parseFloat, but with a second argument for the radix,
and not handling floating-point strings (i.e. 123.456, but not
1.23456e2) (for those, see above on that page) (for algorithm, see
page).

Quicker methods have been presented, but they all seem to include
inexact operations. A single inexact operation may always give the best
available result; but if more than one are used, getting the best
available result probably cannot be guaranteed.

"Completely accurate" means that the Number given will always be the
IEEE Double nearest in value to the number represented by the input,
rounded up if there are two equal nearest.

Note that it can be meaningfully tested in Base 10, since that gets no
special treatment.



function refParseFixed(IN, Rdx) { var Sign = +1, J = 0, Tmp, Scale
// This is slow; it is intended to be completely accurate.
var Digits = "0123456789abcdefghijklmnopqrstuvwxyz"

Tmp = IN.charAt(0) // Handle possible sign
if (Tmp == "-") { J++ ; Sign = -1 } else if (Tmp == "+") J++

// Split IN into 2 arrays, Int & Frc, of 0 <= Number < Rdx
var Num = Int = [], Frc = [], K = IN.length, Cy = true, Bin = []
while (J < K) { Tmp = IN.charAt(J++) // read char from string
if (Tmp == "." && Num == Int) { Num = Frc ; continue }
Tmp = Digits.indexOf(Tmp.toLowerCase()) // char to Number
if (Tmp < 0 || Tmp >= Rdx) break // incorrect digit ends
if (Tmp > 0) Cy = false // so not all zero
Num.push(Tmp) } // arrays now hold digit Numbers

if (Cy) return Sign * 0 // Zero (otherwise loops forever)

// Process integer part; repeatedly halve it to get binary bits :
while (J = Int.length) { // not ==
for (K=0, Cy=0 ; K<J ; K++) { // halving loop
Tmp = Cy * Rdx + Int[K] ; Cy = Tmp % 2 ; Int[K] = (Tmp-Cy)/2 }
Bin.push(Cy)
while (Int[0] == 0) Int.shift() }
Bin.reverse()

while (Bin.length && Bin[0]==0) Bin.shift() // Omit any leading 0s

J = Bin.length - 54 ; Scale = 0.5 ; while (--J >= 0) Scale /= 2

// Do fractional part; repeatedly double it to get binary bits :
while (Bin.length < 54) { Cy = 0 ; K = Frc.length
while (K--) { // doubling loop
Tmp = Frc[K]*2 + Cy ; Cy = +(Tmp>=Rdx) ; Frc[K] = Tmp % Rdx }
if (Bin.length || Cy == 1) Bin.push(Cy)
Scale *= 2 }

Bin[52] += Bin[53] // Rounding: now use Bin[0..52]

// Evaluate Bin[0..52] into Num, scale it, add the Sign :
for (J = 0, Num = 0 ; J < 53 ; J++) { Num *= 2 ; Num += Bin[J] }
return Sign * Num / Scale } // end refParseFixed
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top