Why is it so slow to solve "10^(10^10)"?

newer
FFI - how to handle when external...

older
HXT followingSiblingAxis &&...

yi lu

22 Sep 2013 22 Sep '13

4:02 a.m.

Why is it so slow to solve "10^(10^10)" in Haskell? Yi

Attachments:

attachment.html (text/html — 108 bytes)

Show replies by date

KC

22 Sep 22 Sep

4:41 a.m.

Have you compared the solution to other languages? If you are only solving 10^(10^10) why not construct a string with "1" followed by a 100 zeroes? In other words, what is this being used for? On Sat, Sep 21, 2013 at 3:32 PM, yi lu wrote:

...

Why is it so slow to solve "10^(10^10)" in Haskell?

Yi

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- -- Regards, KC

yi lu

7:32 a.m.

I am checking whether a number equals 10^(10^10). Yi On Sun, Sep 22, 2013 at 7:11 AM, KC wrote:

...

Have you compared the solution to other languages?

If you are only solving 10^(10^10) why not construct a string with "1" followed by a 100 zeroes?

In other words, what is this being used for?

On Sat, Sep 21, 2013 at 3:32 PM, yi lu wrote:

...
Why is it so slow to solve "10^(10^10)" in Haskell?

Yi

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- -- Regards, KC

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Graham Gill

10:20 a.m.

10^(10^10) is a 1 followed by ten billion zeros. Naively evaluating that to an integer is going to cause time and memory problems in any software that supports arbitrary size integers - as Bob Ippolito said, it's going to take about 3.86gb just to store such a number in binary. Even math software (Maple) rejects an attempt to evaluate it directly - sensibly, the "arbitrary size" integers in Maple do have a maximum.

...

h> import Data.Number.BigFloat h> ((10 :: BigFloat Eps1)^10)^10 1.e100

and

...

If you are only solving 10^(10^10) why not construct a string with "1" followed by a 100 zeroes?

10^(10^10) isn't the same as (10^10)^10, which is a 1 followed by 100 zeros, easy to evaluate to an integer in Haskell. Evaluating (10 :: BigFloat Eps1)^(10^10) runs into the same problems as 10^(10^10): Prelude> 10^(10^10) <interactive>: out of memory [restart] Prelude> 10.0^(10^10) Infinity Prelude> 10.0**(10.0^10) Infinity Prelude> import Data.Number.BigFloat Prelude Data.Number.BigFloat> (10 :: BigFloat Eps1)^(10^10) <interactive>: out of memory Maple> 10.0^(10^10); Maple> 10^(10^10); Error, operation failed. Integer exponent too large. Graham On 21/09/2013 10:02 PM, yi lu wrote:

...

I am checking whether a number equals 10^(10^10).

Yi

On Sun, Sep 22, 2013 at 7:11 AM, KC mailto:kc1956@gmail.com> wrote:

Have you compared the solution to other languages?

If you are only solving 10^(10^10) why not construct a string with "1" followed by a 100 zeroes?

In other words, what is this being used for?

On Sat, Sep 21, 2013 at 3:32 PM, yi lu mailto:zhiwudazhanjiangshi@gmail.com> wrote:

Why is it so slow to solve "10^(10^10)" in Haskell?

Yi

_______________________________________________ Beginners mailing list Beginners@haskell.org mailto:Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- -- Regards, KC

_______________________________________________ Beginners mailing list Beginners@haskell.org mailto:Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Brandon Allbery

7 p.m.

On Sun, Sep 22, 2013 at 12:50 AM, Graham Gill wrote:

...

10^(10^10) is a 1 followed by ten billion zeros. Naively evaluating that to an integer is going to cause time and memory problems in any software that supports arbitrary size integers - as Bob Ippolito said, it's

I wonder if they were looking for (**) instead of (^). -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

Bob Ippolito

4:41 a.m.

Why wouldn't it be slow? Integers in Haskell are implemented with GMP, and the representation is simply a sign, a magnitude (number of bits) and then all of the bits. http://gmplib.org/manual/Integer-Internals.html 10^(10^10) is a very large number. With the representation that GMP uses, it will take at least 3.86 GB of RAM to represent the bits required by the result! Of course it takes ages to work with numbers of that magnitude. h> ((10^10) * logBase 256 10) * (2**(-30)) 3.8672332825224878 It is possible to encode values like this, but there's nothing that ships with Haskell Platform that'll do it efficiently. You might look at the numbers package though. h> import Data.Number.BigFloat h> ((10 :: BigFloat Eps1)^10)^10 1.e100 Note that the above example is trivial, only one digit of precision, but that's all that's needed to represent this result since BigFloat is base 10. -bob On Sat, Sep 21, 2013 at 3:32 PM, yi lu wrote:

...

Why is it so slow to solve "10^(10^10)" in Haskell?

Yi

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

4497

Age (days ago)

4498

Last active (days ago)

List overview

Download

5 comments

5 participants

participants (5)

Bob Ippolito
Brandon Allbery
Graham Gill
KC
yi lu