Multiple Precision in JavaScript: FFT multiplication

Nobody believed it but finally: FFT multiplication for my Little big-integer library. It is quite general and can be used for Tom Wu’s bigint library, too, if the the digit size is not larger than 28 bits (default for Mozilla but check the start of Tom Wu’s file).
I don’t go into the mathematical details, there is more than enough to find online but feel free to ask if you have any questions.
The code-base I used is my own implementation of FFT multiplication for Libtommath, so no license problems. Continue reading

[UPDATE]: bugfix.
The Little programming language is in need of arbitrary precision floating point numbers, too. The necessary basics at least: addition; multiplication; division; roots; logarithm; an exponential function; and the three basic trigonometric function sin, cos, and tan; not to forget the constant $\pi$ computed to the current precision. More to come, of course, but these are the minimum for a comfortable environment.

Well, that’s all fine and dandy but how do we get the numbers in and out? Yes, that’s not that simple, indeed. Continue reading

CtoJS: Handling Pointers

The most complicated thing to port to JavaScript it the pointer-juggling while parsing a string.
You can translate it with the String object and handle it natively, that is, native to JavaScript but you can build it instead, with some ado, with the new typed Arrays. Continue reading

Adventures of a Programmer: Parser Writing Peril XXXIX

Is n a Perfect Power?

That means, is $n = x^y$ with $x,y \in \mathbb{N}$. We don’t have to check all of the possible candidates, we can do a very large amount of argument reduction.
First observe that the greatest exponent $y$ possible comes with smallest base $y$ possible. The smallest base is 2, of course, so the largest possible exponent is $y_{\text{max}} = \lfloor \log_2 x \rfloor$. Continue reading

JavaScript: When a Number is not a Number

And it hit me again: JavaScripts loose typing that isn’t very loose when you think it is.

I wrote some functions, for example

Number.prototype.f = function(){
var k = this;
...
if(k.isInt())
...
};


The function isInt is the polyfill for ECMAScript 6 Number.isInteger as a Number prototype. Inside this prototype is a check for NaN and finiteness. It’s a very simple thing:

Number.prototype.isOk = function(){
return ( !isNaN(this) && Number.isFinite(this) )?true:false;
};


Number.isFinite is a build-in to Firefox now and it is also the culprit here, it returns false even if it gets a good, finite number. There’s also a polyfill over at developers.mmozilla.org, so with a little name changing, I was able to find the problems.
The polyfill:

// Number.isFinite polyfill
// http://people.mozilla.org/~jorendorff/es6-draft.html#sec-number.isfinite
if (typeof Number.isFinite2 !== 'function') {
Number.isFinite2 = function isFinite2(value) {
// 1. If Type(number) is not Number, return false.
if (typeof value !== 'number' ){
return false;
}
// 2. If number is NaN, +β, or ββ, return false.
if ( value !== value || value === Infinity || value === -Infinity) {
return false;
}
// 3. Otherwise, return true.
return true;
};
}


The summary to the function Number.isFinite at MDN states

In comparison to the global isFinite function, this method doesn’t forcibly convert the parameter to a number. This means only values of the type number, that are also finite, return true.

That’s what I wanted, no isFinite("123") returning true, good!

At least that’s what I thought.

You might have guessed it already: the “Number is an Object and not a Literal” train hit me again π

But that’s why I wrote xtypeof. Here in its basic version:

function xtypeof(obj){
var tmp = typeof obj;
if( tmp !== "object"){
return tmp;
}
else{
var toString = Object.prototype.toString;
tmp = toString.call(obj);
if(tmp !== "[object Object]"){
return tmp.slice(8, -1).toLowerCase();
}
return "object";
}
}


So changing to that and all is well and peaceful again?

Nope, of course not. I found out, after some fiddling, that the clever way to test for NaN value !=== value isn’t so clever at all. After exchanging it with the global isNaN() it works as expected. Expected by me, that is π

Number.isFinite2 = function(value) {
// 1. If Type(number) is not Number, return false.
if (xtypeof(value) !== 'number' ){
return false;
}
// 2. If number is NaN, +β, or ββ, return false.
if ( isNaN(value) || value === Infinity || value === -Infinity) {
return false;
}
// 3. Otherwise, return true.
return true;
};


There is also a problem with the global isNaN() (not really a problem, I think) but that get’s caught by the xtypeof check.

A standard conforming check for IEEE-754 NaN would be the following:

// Shamelessly stolen from the SunPro code
/*
* ====================================================
*
* Developed at SunPro, a Sun Microsystems, Inc. business.
* Permission to use, copy, modify, and distribute this
* software is freely granted, provided that this notice
* is preserved.
* ====================================================
*/
function isnan(x){
var hx,lx;
var double_int = new DataView(new ArrayBuffer(8));
// needs nevertheless a check if it is really a number
double_int.setFloat64(0, x);
hx = double_int.getInt32(0);
lx = double_int.getInt32(4);
hx &= 0x7fffffff;
hx |= (lx|(-lx))>>>31;
hx = 0x7ff00000 - hx;
return (hx>>>31)|0;
}
Number.prototype.foo = function(){
var a = this;
return isnan(a);
};


You don’t need a check if you use it this way, because a Number is always a number π
Test:

(Number.NaN).foo()        /* 1 */
(123).foo()               /* 0 */
("123").foo()             /* throws exception: "123".foo is not a function */
Math.sqrt(-1).foo()       /* 1 */ /* IEEE 754 7.2g */
(0/0).foo()               /* 1 */ /* IEEE 754 7.2e */
(Infinity/Infinity).foo() /* 1 */ /* IEEE 754 7.2e */
(1/0).foo()               /* 0 */ /* IEEE 754 7.3  */


Yes, the last one is correct, too. Division by zero returns Infinity with the sign set as if it is an ordinary, finite rational (e.g.: if q/r -Infinity) as ruled by IEEE-754 and ECMAScript says to be in concordance to the standard.

If you watch the blogosphere you will see a lot of rants about ECMAScript’s isNaN but the single problem is the automatic conversion such that isNaN("123") returns false. That is a known problem of the principal design of JavaScript from the early days on and it is hard to get rid off now but with the to-come Number.isNaN you’ll get at least a work-around.