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

# Monthly Archives: October 2014

# Multi-Precision Floats: Radix Conversion

[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 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

# Javascript: Number (double) to Bigint

Now that my Bigint library is slowly working (you cannot test it before you have implemented the most basic functions, that is, almost all) I can start to implement the needful little things that will make working with that monster a wee bit less unpleasant. Continue reading

# Adventures of a Programmer: Parser Writing Peril XXXIX

## Is *n* a Perfect Power?

That means, is with . 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 possible comes with smallest base possible. The smallest base is 2, of course, so the largest possible exponent is . Continue reading

# Adventures of a Programmer: Parser Writing Peril XXXVIII

Problems with endianess are normally nothing a JavaScript programmer comes closer to than the sun to the earth: not a lot of things happen for the first billion years or so but than, slowly… 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 /* * ==================================================== * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved. * * 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.