math/big: printing is non-linear and very slow for large Floats

[robpike]

The Text method of big.Float produces a textual representation of the floating point number. I have a program that can create very large numbers and they are slow to print. Moreover, the time to print them does not scale sensibly with the size of the number:

% time ivy -e '1e10000' > /dev/null

real 0m0.005s
user 0m0.002s
sys 0m0.003s
% time ivy -e '1e100000' > /dev/null

real 0m0.032s
user 0m0.027s
sys 0m0.004s
% time ivy -e '1e1000000' > /dev/null

real 0m2.729s
user 0m2.702s
sys 0m0.017s
% time ivy -e '1e10000000' > /dev/null

real 7m11.246s
user 7m7.678s
sys 0m1.834s
%

I have investigated to some extent and the time is definitely being spent inside Text.

[griesemer]

Analysis: For large exponents, the decimal conversion creates the exact binary value in "full precision", which is then converted into a decimal string at decimal.go:75 by calling m.decimalString(), and then rounded to the desired number of decimal digits. For large positive exponents, most of the time is spent in this function (natconv.go:240) and eventually in nat.string (natconv.go:253).

Here's a small driver function to call the involved routines and expose the behaviour:

func TestFloatTextLarge(t *testing.T) {
    f := new(Float).SetFloat64(0.5)
    for e := 10; e < 1e9; e *=10 {
        x := new(Float).SetPrec(256).SetMantExp(f, e)
        println(e, x.Text('g', 10))
    }
}

When the number of desired digits is small and exponents large, we should avoid this conversion path.

[griesemer]

From e-mail thread:

here is an idea about how to do the floating point prints more
efficiently. it works but doesn't have enough precision. what it does
is break out the exponent, scales it to a power of 10 that will
display as "e+(exp)", and then multiplies the reside onto the
mantissa. The mantissa is now in range so prints quickly.

this code works but is missing many important properties, such as
handling negative exponents, adjustable precision, and so on, and the
math with the exponent needs to be done with high precision, but the
idea is sound i think.

-rob

// Assumes positive exponent.
var mant big.Float
exp := f.MantExp(&mant)
fexp := newF().SetInt64(int64(exp))
fexp.Mul(fexp, floatLog2)
fexp.Quo(fexp, newF().SetFloat64(2.3025850929940456840179914546843642076011014886287729760333279009675726096773667591101485283253788949))
// log 2 to many digits.
f64exp, _ := fexp.Float64()
// We now have a floating-point base 10 exponent.
// The integer part is what we will show.
i64exp := int64(f64exp)
// Now compute 10**(fractional part).
scale := math.Pow(10, f64exp - float64(i64exp))
// Rescale mantissa.
mant.Mul(&mant, newF().SetFloat64(scale))
return fmt.Sprintf("%ge+%d\n", &mant, i64exp)

[robpike]

A more thorough implementation is now in robpike.io/ivy/value/bigfloat.go in the dev branch. It is fairly well tested and is now used by ivy for any value with huge exponents.

[bradfitz]

What's the status here? Is something happening or should we punt this to Go 1.7?

[griesemer]

Not addressed yet. I think it's a localized fix, but subtle to get right.
Still hoping to address it but perhaps it won't make it.

• gri

On Wed, Dec 9, 2015 at 7:43 AM, Brad Fitzpatrick [email protected]
wrote:

What's the status here? Is something happening or should we punt this to
Go 1.7?

—
Reply to this email directly or view it on GitHub
#11068 (comment).

[griesemer]

Started.

[realityexists]

big.Int.String is also affected (tested on Go 1.8.3 on Windows):

anInt := new(big.Int)
anInt.Exp(big.NewInt(10), big.NewInt(int64(exp)), nil)
anInt.String()

for 1e50000 this takes 3 ms, for 1e500000 - 282 ms and for 1e5000000 - 37 seconds.

(I get the same times if I convert the big.Int to a big.Float and print that.)

[ALTree]

@realityexists not really.

A big.Int that big takes a lot of space, it's normal that it takes a lot of time to convert it to a string: it has megabytes of digits and all of them are there and need to be processed.

The problem with big.Float is different, i.e. the fact that printing huge Floats takes a lot of time even when they have low precision (e.g. 256 bits) and their string representation is like 50 characters long. This can be fixed. 'slow' printing of big.Ints, not really. You need to generate a megabytes-long string with all the digits, after all.

[realityexists]

Yes, 1e5000000 is has 5 MB of zeros, but I would not expect that to take 37 seconds to generate.

Anyway, the times are almost identical for Int and Float, which leads me to believe the cause is probably the same.

[ALTree]

Yes, 1e5000000 is has 5 MB of zeros, but I would not expect that to take 37 seconds to generate.

But you'd expect the times to grow exponentially, right? The size in memory of a y = 10^x big.Int grows exponentially with y.

Anyway, the times are almost identical for Int and Float, which leads me to believe the cause is probably the same.

That's because -as Robert wrote above- we go through decimal conversion with too many digits, and decimal conversion is slow. The proposed fix is to not do that.

I agree that big.Int.String is slow (I just tested gmp and we're about an order of magnitude slower when printing BigInts in the 2MB range). But in that case the exponential slowdown is at least expected.

[realityexists]

The size in memory of a 10^x big.Int grows exponentially with x.

I don't know exactly how big.Int is implemented, but I'd be surprised if was exponential. Generally the size in memory of 10^x would grow linearly with x, as you simply need to store x digits. Therefore I'd expect the time to print them to grow linearly as well.

That's because -as Robert wrote above- we go through decimal conversion with too many digits, and decimal conversion is slow. The proposed fix is to not do that.

Ah, I missed that - thanks for pointing it out. So perhaps big.Int.String is a separate issue then. Still, I think it's an issue.

[ALTree]

yeah sorry, brain fart. You're right.

In any case, you're also right when you say it's slow, I'll open another issue for the slow Int printing.