How can I optimize my implementation of the “toExponential” algorithm to improve precision?

Question

I feel like my implementation is a bit naive. Take notice of the variables min in max which have a rather small precision of +/- 0.0001. If I raise the precision any further the code is just too slow.

Algorithm

alt text http://img35.imageshack.us/img35/2060/toexponential.jpg

Code

private IDynamic ToExponential(Engine engine, Args args)
{
    var x = engine.Context.ThisBinding.ToNumberPrimitive().Value;

    if (double.IsNaN(x))
    {
        return new StringPrimitive("NaN");
    }

    var s = "";

    if (x < 0)
    {
        s = "-";
        x = -x;
    }

    if (double.IsPositiveInfinity(x))
    {
        return new StringPrimitive(s + "Infinity");
    }

    var f = args[0].ToNumberPrimitive().Value;
    if (f < 0D || f > 20D)
    {
        throw new Exception("RangeError");
    }

    var m = "";
    var c = "";
    var d = "";
    var e = 0D;
    var n = 0D;

    if (x == 0D)
    {
        f = 0D;
        m = m.PadLeft((int)(f + 1D), '0');
        e = 0;
    }
    else
    {
        if (!args[0].IsUndefined) // fractionDigits is supplied
        {
            var lower = (int)Math.Pow(10, f);
            var upper = (int)Math.Pow(10, f + 1D);
            var min = 0 - 0.0001;
            var max = 0 + 0.0001;

            for (int i = lower; i < upper; i++)
            {
                for (int j = (int)f; ; --j)
                {
                    var result = i * Math.Pow(10, j - f) - x;
                    if (result > min && result < max)
                    {
                        n = i;
                        e = j;
                        goto Complete;
                    }
                    if (result <= 0)
                    {
                        break;
                    }
                }

                for (int j = (int)f + 1; ; j++)
                {
                    var result = i * Math.Pow(10, j - f) - x;
                    if (result > min && result < max)
                    {
                        n = i;
                        e = j;
                        goto Complete;
                    }
                    if (result >= 0)
                    {
                        break;
                    }
                }
            }
        }
        else
        {
            var min = x - 0.0001;
            var max = x + 0.0001;

            // Scan for f where f >= 0
            for (int i = 0; ; i++)
            {
                // 10 ^ f <= n < 10 ^ (f + 1)
                var lower = (int)Math.Pow(10, i);
                var upper = (int)Math.Pow(10, i + 1D);
                for (int j = lower; j < upper; j++)
                {
                    // n is not divisible by 10
                    if (j % 10 == 0)
                    {
                        continue;
                    }

                    // n must have f + 1 digits
                    var digits = 0;
                    var state = j;
                    while (state > 0)
                    {
                        state /= 10;
                        digits++;
                    }
                    if (digits != i + 1)
                    {
                        continue;
                    }

                    // Scan for e in both directions
                    for (int k = (int)i; ; --k)
                    {
                        var result = j * Math.Pow(10, k - i);
                        if (result > min && result < max)
                        {
                            f = i;
                            n = j;
                            e = k;
                            goto Complete;
                        }
                        if (result <= i)
                        {
                            break;
                        }
                    }
                    for (int k = (int)i + 1; ; k++)
                    {
                        var result = i * Math.Pow(10, k - i);
                        if (result > min && result < max)
                        {
                            f = i;
                            n = j;
                            e = k;
                            goto Complete;
                        }
                        if (result >= i)
                        {
                            break;
                        }
                    }
                }
            }
        }

    Complete:

        m = n.ToString("G");
    }

    if (f != 0D)
    {
        m = m[0] + "." + m.Substring(1);
    }

    if (e == 0D)
    {
        c = "+";
        d = "0";
    }
    else
    {
        if (e > 0D)
        {
            c = "+";
        }
        else
        {
            c = "-";
            e = -e;
        }
        d = e.ToString("G");
    }

    m = m + "e" + c + d;
    return new StringPrimitive(s + m);
}

Final Version

I swear someone must have hit me with a particularly large hammer back when I originally wrote this...

private IDynamic ToExponential(Engine engine, Args args)
{
    var x = engine.Context.ThisBinding.ToNumberPrimitive().Value;

    if (args[0].IsUndefined)
    {
        return new StringPrimitive(x.ToString("0.####################e+0"));
    }

    var f = args[0].ToNumberPrimitive().Value;

    if (f < 0D || f > 20D)
    {
        RuntimeError.RangeError("The parameter fractionDigits must be between 0 and 20.");
    }

    return new StringPrimitive(x.ToString("0." + string.Empty.PadRight((int)f, '0') + "e+0"));            
}

Answer 1

When you compute result = i * Math.Pow(10, j - f) - x you're trying to find where result is 0. Since j, f, and x are know, you just need to solve for i. Rather than writing a loop to find i, you can just say

i * Math.Pow(10, j - f) = x => i = x / Math.Pow(10, j - f)

The value you need should be either floor(i) or ceil(i).

Just out of curiosity, have you checked to see if ToString("e") gives you the correct answer?

Answer 2

I'd start by using Math.Log10, rather than a loop, to find the exponent.