Extracting the exponent and mantissa of a Javascript Number

Question

Is there a reasonably fast way to extract the exponent and mantissa from a Number in Javascript?

AFAIK there's no way to get at the bits behind a Number in Javascript, which makes it seem to me that I'm looking at a factorization problem: finding m and n such that 2^n * m = k for a given k. Since integer factorization is in NP, I can only assume that this would be a fairly hard problem.

I'm implementing a GHC plugin for generating Javascript and need to implement the decodeFloat_Int# and decodeDouble_2Int# primitive operations; I guess I could just rewrite the parts of the base library that uses the operation to do wahtever they're doing in some other way (which shouldn't be too hard since all numeric types have Number as their representation anyway,) but it'd be nice if I didn't have to.

Is there any way to do this in an even remotely performant way, by some dark Javascript voodoo, clever mathematics or some other means, or should I just buckle down and have at the base library?

EDIT Based on ruakh's and Louis Wasserman's excellent answers, I came up with the following implementation, which seems to work well enough:

function getNumberParts(x) {
    if(isNaN(x)) {
        return {mantissa: -6755399441055744, exponent: 972};
    }
    var sig = x > 0 ? 1 : -1;
    if(!isFinite(x)) {
        return {mantissa: sig * 4503599627370496, exponent: 972};
    }
    x = Math.abs(x);
    var exp = Math.floor(Math.log(x)*Math.LOG2E)-52;
    var man = x/Math.pow(2, exp);
    return {mantissa: sig*man, exponent: exp};
}

Solution 1

ECMAScript doesn't define any straightforward way to do this; but for what it's worth, this isn't a "factorization problem" in the same sense as prime factorization.

What you want can theoretically be done very quickly by first handling the sign, then using a binary-tree approach (or logarithm) to find the exponent, and lastly dividing by the relevant power of two to get the mantissa; but unfortunately, it can be somewhat tricky to implement this in practice (what with special cases such as denormalized numbers). I recommend you read through section 8.5 of the ECMAScript specification to get a sense of what cases you'll have to handle.

Solution 2

Using the new ArrayBuffer access arrays, it is actually possible to retrieve the exact mantissa and exponent, by extracting them from the Uint8Array. If you need more speed, consider reusing the Float64Array.

function getNumberParts(x)
{
    var float = new Float64Array(1),
        bytes = new Uint8Array(float.buffer);

    float[0] = x;

    var sign = bytes[7] >> 7,
        exponent = ((bytes[7] & 0x7f) << 4 | bytes[6] >> 4) - 0x3ff;

    bytes[7] = 0x3f;
    bytes[6] |= 0xf0;

    return {
        sign: sign,
        exponent: exponent,
        mantissa: float[0],
    }
}

I've also created some test cases. 0 fails, since there is another representation for 2^-1023.

var tests = [1, -1, .123, -.123, 1.5, -1.5, 1e100, -1e100, 
                    1e-100, -1e-100, Infinity, -Infinity];

tests.forEach(function(x)
{
    var parts = getNumberParts(x),
        value = Math.pow(-1, parts.sign) *
                    Math.pow(2, parts.exponent) *
                    parts.mantissa;

    console.log("Testing: " + x + " " + value);
    console.assert(x === value);
});

console.log("Tests passed");

Solution 3

Integer factorization is nowhere near necessary for this.

The exponent is basically going to be the floor of the base-2 logarithm, which isn't that hard to compute.

The following code passes QuickCheck tests, as well as tests on infinity and negative infinity:

minNormalizedDouble :: Double
minNormalizedDouble = 2 ^^ (-1022)

powers :: [(Int, Double)]
powers = [(b, 2.0 ^^ fromIntegral b) | i <- [9, 8..0], let b = bit i]

exponentOf :: Double -> Int
exponentOf d
  | d < 0   = exponentOf (-d)
  | d < minNormalizedDouble = -1024
  | d < 1   = 
      let go (dd, accum) (p, twoP)
            | dd * twoP < 1 = (dd * twoP, accum - p)
            | otherwise = (dd, accum)
      in snd $ foldl' go (d, 0) powers
  | otherwise   =
      let go (x, accum) (p, twoP)
            | x * twoP <= d = (x * twoP, accum + p)
            | otherwise = (x, accum)
    in 1 + (snd $ foldl' go (1.0, 0) powers)


decode :: Double -> (Integer, Int)
decode 0.0 = (0, 0)
decode d
  | isInfinite d, d > 0 = (4503599627370496, 972)
  | isInfinite d, d < 0 = (-4503599627370496, 972)
  | isNaN d             = (-6755399441055744, 972)
  | otherwise       =
      let
        e = exponentOf d - 53
        twoE = 2.0 ^^ e
         in (round (d / twoE), e)

I tested it using quickCheck (\ d -> decodeFloat d == decode d), and explicitly tested it separately on positive and negative infinities.

The only primitive operations used here are left-shift, double multiplication, double division, and infinity and NaN testing, which Javascript supports to the best of my knowledge.

Solution 4

While I liked the accepted solution, using it to work on arbitrary base re-introduced all of the errors caused by Math.log and Math.pow. Here is a small implementation for any base: x = mantisse * b^exponent

function numberParts(x, b) {
  var exp = 0
  var sgn = 0
  if (x === 0) return { sign: 0, mantissa: 0, exponent: 0 }
  if (x<0) sgn=1, x=-x
  while (x>b) x/=b, exp++
  while (x<1) x*=b, exp--
  return { sign: sgn, mantissa: x, exponent: exp }
}

The NaN and Infinite cases can easily be added. If the distinction between +0 and -0 is important:

if (1/x === Infinity) return { sign: 0, mantissa: 0, exponent: 0 }
if (1/x === -Infinity) return { sign: 1, mantissa: 0, exponent: 0 }

Solution 5

For base 10 you can get mantissa and exponent in an array with

   var myarray = (number.toExponential() + '').split("e");
   // then ...
   var mantissa = parseFloat(myarray[0]);
   var exponent = parseInt(myarray[1]);

If you don't care if the result parts are text instead of numbers and if there might be a plus sign on the front of the exponent part, then you can skip the parseFloat and parseInt steps and just take the parts directly from the array at [0] and [1].

View more solutions

Comments

[Louis Wasserman]

Factorization is unquestionably in NP, it's just not believed to be NP-hard. You have them mixed up.

[ruakh]

@LouisWasserman: Hmm, I'm finding conflicting information online. I'll just remove that portion of my answer, since it's not really important. Thanks.

[valderman]

Thank you; however, won't this method (at least if the base 2 logarithm is used to obtain the exponent) give a non-integer mantissa for most numbers?

[ruakh]

@valderman: That's a good question. I'm used to thinking of the mantissa as a value in the range [1.0, 2.0) and the exponent as an integer in the range [-1022, +1023], but EMCAScript presents numbers in terms of an integer in the range [2^52, 2^53) and an integer in the range [-1074, +971] (and therefore avoids the terms "mantissa" and "exponent"), and Haskell seems to do the same (though it does use those terms). Even so, this is easily addressed by incorporating an offset of -52 after performing the logarithm.

[Louis Wasserman]

I updated my answer with code that emulates Haskell's built-in decodeFloat operation...but for reference, en.wikipedia.org/wiki/NP_(complexity)#Examples correctly states that factorization is in NP.

[Louis Wasserman]

Yep. I would've had it up sooner if Haskell's decodeFloat operation wasn't so far from what I'd expected! I've been doing a lot of IEEE754 hackery in Java lately, though, which helped.

[hammar]

@ruakh: NP is, to put it simply, the class of problems whose solutions may be checked in polynomial time. Multiplication takes polynomial time, therefore factorization is in NP.

[Daniel Fischer]

Your minNormalizedDouble is actually denormalized, the smallest positive normalized Double is 0.5 ^ 1022. Due to a ^^ b = 1/(a ^ (-b)) for b < 0, the exponentiation overflows for 0 < d < minNormalizedDouble, giving nonsense results (you're rounding Infinity). let e = exponentOf d - 53; twoE | e < 0 = 0.5 ^ (-e) | otherwise = 2 ^ e fixes that. In what way is decodeFloat far from what you expected?

[Louis Wasserman]

Fixed. I guess I feel like I expect Int64 to get involved rather than Integer; in particular, I'd like a way to get the bits of the double directly in an Int64.

[ruakh]

@hammar: Yeah, I'm not so sure. There seem to be multiple opinions about what "factorization" means (does it mean "finding out if there is any factor between 1 and n"? does it mean "finding all prime factors"? etc.), and therefore, multiple statements that are all true, but superficially mutually contradictory, about the complexity of "factorization". (And anyway, it doesn't make sense to describe a problem as "fairly hard" on the basis of its being "in NP", since NP only describes an upper bound on complexity, such that the least-complex algorithms are all in NP.)

[ruakh]

@hammar: Also, I'd challenge the statement that "Multiplication takes polynomial time, therefore factorization is in NP". Even if the conclusion is true, the first does not trivially entail the latter. After all, if a number has n bits, then naively checking all factors would require O(2 ^ n) multiplications, which is not in NP. (We could define "NP" to be in terms of the number itself, rather than its number of bits -- then it would certainly be in NP -- but that doesn't seem to be common practice for this family of problems.)

[hammar]

@ruakh: I think you misunderstood me. We only have to be able to check the solution, e.g. given a factorization n = x1 * ... * xk, we can verify the factorization in polynomial time by multiplying the factors together and checking that the result is equal to n. Of course, finding the factors in the first place is the part which may be difficult, but that's not what the NP class is concerned with.

[ruakh]

@hammar: The OP's goal was not to check that a given mantissa and exponent yield the specified number, but to find a mantissa and exponent that do. I therefore assume that by "integer factorization", (s)he was referring to the process of factorizing an integer.

[hammar]

@ruakh: I was simply trying to clear up the confusion about the NP class. You initially wrote that factorization was not in NP, so I tried to give a simple argument for why it is in fact in NP, though I agree this isn't really related to the original question.

[ruakh]

@hammar: Ah, fair enough. I don't think I was confused, but I can see why you and Louis Wasserman thought that I was, and I appreciate your trying to clear it up. :-)

[4esn0k]

this solution will work event on iPad, where denormalized numbers are not supported

[MaiaVictor]

Oh gosh finally found this. I've seen your answer 10 days ago but used log/pow anyway. Then I started having rounding issues and went looking for your answer. I googled for every relevant keyword I could remember, read all answers in tons of similar questions, then spent half a minute looking through my whole browse history. Never so glad for reading 8 lines of code. Thank you :)

[Girts Strazdins]

Please note that there is an error in case x is zero! You should catch that using an if.

[Hurelu]

@user1703497 thanks, made some edits for the common 0 case and the less common -0 and +0 cases

[MaiaVictor]

... found it again. Damn, how many times I'll need this on my life?

[David Galloway]

If you want the base 10 exponent then why not do this? var exponent = Math.log(number) * Math.LOG10E;

[David Galloway]

Apparently there is now a Math.log10() - can also be combined with a Math.floor()

[Jonathan Wilbur]

This returns a floating-point mantissa for me. Isn't the point to return an integral mantissa?

[L.Trabacchin]

how do you return an integral number in a language that don't have it ? With this very same method you can implement your own number types btw :D

[richardpj]

@JonathanWilbur This algorithm doesn't give you the bits. It gives you what they represent. The mantissa is defined as a number between 1 and 2. Such that mantissa = 1,b51 b50... b0 base 2. en.wikipedia.org/wiki/Double-precision_floating-point_format

[brainbag]

This is the fastest of all the solutions by quite a margin as of 7/28/2021. Comparison: jsbench.me/hokro6nel4/1