Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #42357 > unrolled thread

Why does 1**2**3**4**5 raise a MemoryError?

Back to article view | Back to comp.lang.python

Contents

  Why does 1**2**3**4**5 raise a MemoryError? morphex <morphex@gmail.com> - 2013-03-30 23:56 -0700
    Re: Why does 1**2**3**4**5 raise a MemoryError? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-31 07:33 +0000
      Re: Why does 1**2**3**4**5 raise a MemoryError? Dave Angel <davea@davea.name> - 2013-03-31 03:48 -0400
      Re: Why does 1**2**3**4**5 raise a MemoryError? morphex <morphex@gmail.com> - 2013-03-31 05:07 -0700
        Re: Why does 1**2**3**4**5 raise a MemoryError? Dave Angel <d@davea.name> - 2013-03-31 08:43 -0400
          Re: Why does 1**2**3**4**5 raise a MemoryError? Roy Smith <roy@panix.com> - 2013-03-31 09:15 -0400
            Re: Why does 1**2**3**4**5 raise a MemoryError? Jason Swails <jason.swails@gmail.com> - 2013-03-31 10:03 -0400
        Re: Why does 1**2**3**4**5 raise a MemoryError? Roy Smith <roy@panix.com> - 2013-03-31 09:04 -0400
        Re: Why does 1**2**3**4**5 raise a MemoryError? Tim Roberts <timr@probo.com> - 2013-04-01 21:45 -0700
          Re: Why does 1**2**3**4**5 raise a MemoryError? Chris Angelico <rosuav@gmail.com> - 2013-04-02 17:16 +1100
          Re: Why does 1**2**3**4**5 raise a MemoryError? Dan Sommers <dan@tombstonezero.net> - 2013-04-02 12:56 +0000
      Re: Why does 1**2**3**4**5 raise a MemoryError? Roy Smith <roy@panix.com> - 2013-03-31 08:59 -0400
    Re: Why does 1**2**3**4**5 raise a MemoryError? Dave Angel <davea@davea.name> - 2013-03-31 03:34 -0400
      Re: Why does 1**2**3**4**5 raise a MemoryError? "Alex" <foo@email.invalid> - 2013-03-31 22:06 +0000
        Re: Why does 1**2**3**4**5 raise a MemoryError? Chris Angelico <rosuav@gmail.com> - 2013-04-01 09:28 +1100
          Re: Why does 1**2**3**4**5 raise a MemoryError? "Alex" <foo@email.invalid> - 2013-04-01 00:39 +0000
            Re: Why does 1**2**3**4**5 raise a MemoryError? Chris Angelico <rosuav@gmail.com> - 2013-04-01 11:58 +1100
            Re: Why does 1**2**3**4**5 raise a MemoryError? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-01 04:16 +0000
              Re: Why does 1**2**3**4**5 raise a MemoryError? Roy Smith <roy@panix.com> - 2013-04-01 07:48 -0400
            Re: Why does 1**2**3**4**5 raise a MemoryError? Nobody <nobody@nowhere.com> - 2013-04-02 08:40 +0100
        Re: Why does 1**2**3**4**5 raise a MemoryError? Chris Angelico <rosuav@gmail.com> - 2013-04-01 09:32 +1100
        Re: Why does 1**2**3**4**5 raise a MemoryError? Dave Angel <davea@davea.name> - 2013-03-31 18:34 -0400

Page 1 of 2  [1] 2  Next page →

#42357 — Why does 1**2**3**4**5 raise a MemoryError?

Hi.

I was just doodling around with the python interpreter today, and here is the dump from the terminal:

morphex@laptop:~$ python
Python 2.7.3 (default, Sep 26 2012, 21:53:58) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 1**2
1
>>> 1**2**3
1
>>> 1**2**3**4
1L
>>> 1**2**3**4**5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>> 

Does anyone know why this raises a MemoryError?  Doesn't make sense to me.

Happy Easter!

-Morten

[toc] | [next] | [standalone]

#42358

On Sat, 30 Mar 2013 23:56:46 -0700, morphex wrote:

> Hi.
> 
> I was just doodling around with the python interpreter today, and here
> is the dump from the terminal:
> 
> morphex@laptop:~$ python
> Python 2.7.3 (default, Sep 26 2012, 21:53:58) [GCC 4.7.2] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
>>>> 1**2
> 1
>>>> 1**2**3
> 1
>>>> 1**2**3**4
> 1L
>>>> 1**2**3**4**5
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
> MemoryError
>>>> 
>>>> 
> Does anyone know why this raises a MemoryError?  Doesn't make sense to
> me.

Because exponentiation is right-associative, not left.

1**2**3**4**5 is calculated like this:

1**2**3**4**5
=> 1**2**3**1024
=> 1**2**373...481  #  489-digit number
=> 1**(something absolutely humongous)
=> 1

except of course you get a MemoryError in calculating the intermediate 
values.

In other words, unlike you or me, Python is not smart enough to realise 
that 1**(...) is automatically 1, it tries to calculate the humongous 
intermediate result, and that's what fails.

For what it's worth, that last intermediate result (two to the power of 
the 489-digit number) has approximately a billion trillion trillion 
trillion trillion trillion trillion trillion trillion trillion trillion 
trillion trillion trillion trillion trillion trillion trillion trillion 
trillion trillion trillion trillion trillion trillion trillion trillion 
trillion trillion trillion trillion trillion trillion trillion trillion 
trillion trillion trillion trillion trillion trillion digits.

(American billion and trillion, 10**9 and 10**12 respectively.)



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#42361

On 03/31/2013 03:33 AM, Steven D'Aprano wrote:
> On Sat, 30 Mar 2013 23:56:46 -0700, morphex wrote:
>
>> Hi.
>>
>> I was just doodling around with the python interpreter today, and here
>> is the dump from the terminal:
>>
>> morphex@laptop:~$ python
>> Python 2.7.3 (default, Sep 26 2012, 21:53:58) [GCC 4.7.2] on linux2
>> Type "help", "copyright", "credits" or "license" for more information.
>>>>> 1**2
>> 1
>>>>> 1**2**3
>> 1
>>>>> 1**2**3**4
>> 1L
>>>>> 1**2**3**4**5
>> Traceback (most recent call last):
>>    File "<stdin>", line 1, in <module>
>> MemoryError
>>>>>
>>>>>
>> Does anyone know why this raises a MemoryError?  Doesn't make sense to
>> me.
>
> Because exponentiation is right-associative, not left.
>
> 1**2**3**4**5 is calculated like this:
>
> 1**2**3**4**5
> => 1**2**3**1024
> => 1**2**373...481  #  489-digit number

Oops, you're right, it's 489.  I figured 488 but was wrong.




-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#42363

Aha, OK.  Thought I found a bug but yeah that makes sense ;)

While we're on the subject, wouldn't it be nice to have some cap there so that it isn't possible to more or less block the system with large exponentiation?

On Sunday, March 31, 2013 9:33:32 AM UTC+2, Steven D'Aprano wrote:
> On Sat, 30 Mar 2013 23:56:46 -0700, morphex wrote:
> 
> 
> 
> > Hi.
> 
> > 
> 
> > I was just doodling around with the python interpreter today, and here
> 
> > is the dump from the terminal:
> 
> > 
> 
> > morphex@laptop:~$ python
> 
> > Python 2.7.3 (default, Sep 26 2012, 21:53:58) [GCC 4.7.2] on linux2
> 
> > Type "help", "copyright", "credits" or "license" for more information.
> 
> >>>> 1**2
> 
> > 1
> 
> >>>> 1**2**3
> 
> > 1
> 
> >>>> 1**2**3**4
> 
> > 1L
> 
> >>>> 1**2**3**4**5
> 
> > Traceback (most recent call last):
> 
> >   File "<stdin>", line 1, in <module>
> 
> > MemoryError
> 
> >>>> 
> 
> >>>> 
> 
> > Does anyone know why this raises a MemoryError?  Doesn't make sense to
> 
> > me.
> 
> 
> 
> Because exponentiation is right-associative, not left.
> 
> 
> 
> 1**2**3**4**5 is calculated like this:
> 
> 
> 
> 1**2**3**4**5
> 
> => 1**2**3**1024
> 
> => 1**2**373...481  #  489-digit number
> 
> => 1**(something absolutely humongous)
> 
> => 1
> 
> 
> 
> except of course you get a MemoryError in calculating the intermediate 
> 
> values.
> 
> 
> 
> In other words, unlike you or me, Python is not smart enough to realise 
> 
> that 1**(...) is automatically 1, it tries to calculate the humongous 
> 
> intermediate result, and that's what fails.
> 
> 
> 
> For what it's worth, that last intermediate result (two to the power of 
> 
> the 489-digit number) has approximately a billion trillion trillion 
> 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> 
> trillion trillion trillion trillion trillion trillion digits.
> 
> 
> 
> (American billion and trillion, 10**9 and 10**12 respectively.)
> 
> 
> 
> 
> 
> 
> 
> -- 
> 
> Steven

[toc] | [prev] | [next] | [standalone]

#42365

On 03/31/2013 08:07 AM, morphex wrote:
> Aha, OK.  Thought I found a bug but yeah that makes sense ;)
>
> While we're on the subject, wouldn't it be nice to have some cap there so that it isn't possible to more or less block the system with large exponentiation?
>

There's an assumption there.  The Operating System should defend itself 
against starvation by any single process.

Besides, there are many ways for a process to run out of memory, and 
exponentiation is probably the least likely of them.  In general, an 
application cannot tell whether a particular memory allocation will 
succeed or not without actually trying the allocation.  If it fails, you 
get the exception.

I'm typing this while a terminal is open doing the particular operation, 
and the system doesn't seem in the least sluggish.

Currently the memory used is at 10gig, and while there are some pauses 
in my typing, the system has not died.  This is on Linux Ubuntu 12.04.

At 15gig, there are some blockages, of maybe 5 secs each.

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#42369

In article <mailman.4012.1364733818.2939.python-list@python.org>,
 Dave Angel <d@davea.name> wrote:

> I'm typing this while a terminal is open doing the particular operation, 
> and the system doesn't seem in the least sluggish.
> 
> Currently the memory used is at 10gig, and while there are some pauses 
> in my typing, the system has not died.  This is on Linux Ubuntu 12.04.
> 
> At 15gig, there are some blockages, of maybe 5 secs each.

15 gig?  Feh.

> $ prtstat 29937
> Process: mongod            State: S (sleeping)
> [...]
> Memory
>   Vsize:       1998285 MB
>   RSS:         5428 MB
>   RSS Limit: 18446744073709 MB

If I counted the digits right, that 1.9 TB.  I love the RSS Limit.  I'll 
be really impressed when somebody builds a machine with enough RAM to 
reach that :-)

[toc] | [prev] | [next] | [standalone]

#42372

[Multipart message — attachments visible in raw view] — view raw

On Sun, Mar 31, 2013 at 9:15 AM, Roy Smith <roy@panix.com> wrote:

>
> > $ prtstat 29937
> > Process: mongod            State: S (sleeping)
> > [...]
> > Memory
> >   Vsize:       1998285 MB
> >   RSS:         5428 MB
> >   RSS Limit: 18446744073709 MB
>
> If I counted the digits right, that 1.9 TB.  I love the RSS Limit.  I'll
> be really impressed when somebody builds a machine with enough RAM to
> reach that :-)
>

http://www.ncsa.illinois.edu/UserInfo/Resources/Hardware/SGIAltix/TechSummary/

Look at co-compute2.  The indicated memory is available as shared memory
across all 512 cores.  And that's nothing---it can be configured with up to
64 TB of global shared memory:
http://www.sgi.com/products/servers/uv/configs.html

Impressed? :)

All the best,
Jason

[toc] | [prev] | [next] | [standalone]

#42368

In article <8276eff6-9e5c-4060-b9e8-94fab606206f@googlegroups.com>,
 morphex <morphex@gmail.com> wrote:

> Aha, OK.  Thought I found a bug but yeah that makes sense ;)
> 
> While we're on the subject, wouldn't it be nice to have some cap there so 
> that it isn't possible to more or less block the system with large 
> exponentiation?

Every time we think we know a good upper bound to something (i.e. 
"nobody will ever need more than 64k of memory"), it turns out that 
limit is wrong.

There's great value in writing code which continues to work until it 
runs out of some external resource (i.e. memory, disk space, whatever).  
Eventually, somebody will want to do some calculation which you 
previously thought was absurd but turns out to be useful.

I don't use Python bugnums very often, but when I do, I'm really happy 
they're there.

[toc] | [prev] | [next] | [standalone]

#42539

morphex <morphex@gmail.com> wrote:
>
>While we're on the subject, wouldn't it be nice to have some cap there so
>that it isn't possible to more or less block the system with large 
>exponentiation?

There IS a cap.  It's called the "MemoryError" exception.

But, seriously, what would you have it do instead?
-- 
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[toc] | [prev] | [next] | [standalone]

#42543

On Tue, Apr 2, 2013 at 3:45 PM, Tim Roberts <timr@probo.com> wrote:
> morphex <morphex@gmail.com> wrote:
>>
>>While we're on the subject, wouldn't it be nice to have some cap there so
>>that it isn't possible to more or less block the system with large
>>exponentiation?
>
> There IS a cap.  It's called the "MemoryError" exception.
>
> But, seriously, what would you have it do instead?

And If you want a lower cap than the one you currently have, check out
ulimit/rlimit - you can trigger MemoryError sooner.

ChrisA

[toc] | [prev] | [next] | [standalone]

#42559

On Mon, 01 Apr 2013 21:45:30 -0700, Tim Roberts wrote:

> morphex <morphex@gmail.com> wrote:
>>
>>While we're on the subject, wouldn't it be nice to have some cap there
>>so that it isn't possible to more or less block the system with large
>>exponentiation?
> 
> There IS a cap.  It's called the "MemoryError" exception.
> 
> But, seriously, what would you have it do instead?

One day late:

http://developers.slashdot.org/story/13/04/01/2230220/erlang-getting-too-
big-to-fail-process-flag

[toc] | [prev] | [next] | [standalone]

#42367

In article <5157e6cc$0$29974$c3e8da3$5496439d@news.astraweb.com>,
 Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:

> For what it's worth, that last intermediate result (two to the power of 
> the 489-digit number) has approximately a billion trillion trillion 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> trillion trillion trillion trillion trillion trillion trillion trillion 
> trillion trillion trillion trillion trillion trillion digits.
> 
> (American billion and trillion, 10**9 and 10**12 respectively.)

What's that in crore?

[toc] | [prev] | [next] | [standalone]

#42359

On 03/31/2013 02:56 AM, morphex wrote:
> Hi.
>
> I was just doodling around with the python interpreter today, and here is the dump from the terminal:
>
> morphex@laptop:~$ python
> Python 2.7.3 (default, Sep 26 2012, 21:53:58)
> [GCC 4.7.2] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
>>>> 1**2
> 1
>>>> 1**2**3
> 1
>>>> 1**2**3**4
> 1L
>>>> 1**2**3**4**5
> Traceback (most recent call last):
>    File "<stdin>", line 1, in <module>
> MemoryError
>>>>
>
> Does anyone know why this raises a MemoryError?  Doesn't make sense to me.
>
>

Perhaps you didn't realize that the expression will be done from right 
to left.  So first it calculates 4**5 which is 1024

Then it calculates 3**1024, which has 488 digits.  then it calculates 2 
to that power, which is a number large enough to boggle the mind.  That 
number's storage needs makes a few gigabytes seem like a molecule in the 
ocean.

Anyway, it never gets around to doing the 1**  part.

On the other hand, perhaps you wanted to do a different calculation:

 >>> ((((1**2)**3)**4)**5)
1






-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#42424

Dave Angel wrote:

> On 03/31/2013 02:56 AM, morphex wrote:
> > > > > 1**2
> > 1
> > > > > 1**2**3
> > 1
> > > > > 1**2**3**4
> > 1L
> > > > > 1**2**3**4**5
> > Traceback (most recent call last):
> >   File "<stdin>", line 1, in <module>
> > MemoryError
> > > > > 
> > 
> > Does anyone know why this raises a MemoryError?  Doesn't make sense
> > to me.
> 
> Perhaps you didn't realize that the expression will be done from
> right to left.  

Really? 

The Python 3 documentation
(http://docs.python.org/3/reference/expressions.html) says in section
6.14 (Evaluation order) that "Python evaluates expressions from left to
right" (an exception being when evaluating assignments, in which case
the RHS of the assignment is calculated first, in left-to-right order).

Section 6.4 discusses the power operator specifically and does not
contradict 6.14 except that the power operator uses right-to-left
evaluation in the presence of unparenthesized unary operators.

Neither of these two exception cases appear to apply here, so I think
the OP is reasonable in expecting Python to do the operation
left-to-right.

Am I missing something written somewhere else in the docs? Are the docs
I quoted wrong? Please help me understand the discrepancy I am
perceiving here.

Alex

[toc] | [prev] | [next] | [standalone]

#42429

On Mon, Apr 1, 2013 at 9:06 AM, Alex <foo@email.invalid> wrote:
> Dave Angel wrote:
>
>> On 03/31/2013 02:56 AM, morphex wrote:
>> > > > > 1**2
>> > 1
>> > > > > 1**2**3
>> > 1
>> > > > > 1**2**3**4
>> > 1L
>> > > > > 1**2**3**4**5
>> > Traceback (most recent call last):
>> >   File "<stdin>", line 1, in <module>
>> > MemoryError
>> > > > >
>> >
>> > Does anyone know why this raises a MemoryError?  Doesn't make sense
>> > to me.
>>
>> Perhaps you didn't realize that the expression will be done from
>> right to left.
>
> Really?
>
> The Python 3 documentation
> (http://docs.python.org/3/reference/expressions.html) says in section
> 6.14 (Evaluation order) that "Python evaluates expressions from left to
> right" (an exception being when evaluating assignments, in which case
> the RHS of the assignment is calculated first, in left-to-right order).
>
> Section 6.4 discusses the power operator specifically and does not
> contradict 6.14 except that the power operator uses right-to-left
> evaluation in the presence of unparenthesized unary operators.

http://docs.python.org/3/reference/expressions.html#operator-precedence

Opening paragraph, "... exponentiation, which groups from right to
left". It follows the obvious expectation from mathematics. (The OP is
using Python 2, but the same applies.)

ChrisA

[toc] | [prev] | [next] | [standalone]

#42436

Chris Angelico wrote:

> 
> Opening paragraph, "... exponentiation, which groups from right to
> left". It follows the obvious expectation from mathematics. (The OP is
> using Python 2, but the same applies.)

Thanks. I did miss that parenthetical comment in para 6.15, and that
would have been the correct place to look, since it appears that
operators are not parts of expressions, but rather separate them. Is
that the "obvious expectation from mathematics," though? Given that

  3
 5
4

(i.e.: 4**5**3) is transitive, I would have expected Python to exhibit
more consistency with the other operators. I guess that is one of the
foolish consistencies that comprise the hobgoblins of my little mind,
though.

[toc] | [prev] | [next] | [standalone]

#42437

On Mon, Apr 1, 2013 at 11:39 AM, Alex <foo@email.invalid> wrote:
> Given that
>
>   3
>  5
> 4
>
> (i.e.: 4**5**3) is transitive, I would have expected Python to exhibit
> more consistency with the other operators. I guess that is one of the
> foolish consistencies that comprise the hobgoblins of my little mind,
> though.

Not sure what you mean by transitive here. Certainly (4**5)**3 and
4**(5**3) are not the same value.

ChrisA

[toc] | [prev] | [next] | [standalone]

#42439

On Mon, 01 Apr 2013 00:39:56 +0000, Alex wrote:

> Chris Angelico wrote:
> 
> 
>> Opening paragraph, "... exponentiation, which groups from right to
>> left". It follows the obvious expectation from mathematics. (The OP is
>> using Python 2, but the same applies.)
> 
> Thanks. I did miss that parenthetical comment in para 6.15, and that
> would have been the correct place to look, since it appears that
> operators are not parts of expressions, but rather separate them. Is
> that the "obvious expectation from mathematics," though? Given that
> 
>   3
>  5
> 4
> 
> (i.e.: 4**5**3) is transitive, I would have expected Python to exhibit
> more consistency with the other operators. I guess that is one of the
> foolish consistencies that comprise the hobgoblins of my little mind,
> though.

I don't think you mean "transitive" here. Transitivity refers to 
relations, not arbitrary operators. If ≎ is some relation, then it is 
transitive if and only if:

x ≎ y and y ≎ z implies that x ≎ y.

http://en.wikipedia.org/wiki/Transitive_relation

Concrete examples of transitive relations: greater than, equal to, less 
than and equal to.

On the other hand, "unequal to" is not a transitive relation. Nor is 
"approximately equal to". Suppose we say that two values are 
approximately equal if their difference is less than 0.5:

2.1 ≈ 2.4 and 2.4 ≈ 2.7
but 2.1 ≉ 2.7


Exponentiation is not commutative:

2**3 != 3**2

nor is it associative:

2**(3**2) != (2**3)**2


so I'm not really sure what you are trying to say here.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#42457

In article <51590a2b$0$30000$c3e8da3$5496439d@news.astraweb.com>,
 Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:

> Concrete examples of transitive relations: greater than, equal to, less 
> than and equal to.

Will Python 4 implement "less than and equal to"? :-)

[Warning: topic creep]

Well, they are transitive over certain domains.  Or, perhaps, a better 
way to say it is they are transitive according to their traditional 
mathematical definitions.  But, computer languages don't always follow 
those.

I used to work with a guy who was originally a math major.  He used to 
always complain about things like:

s = "foo" + "bar"

because addition is supposed to be commutative.

But, yeah, I know what you're saying that "transitive" applies to 
relations, not to operators.

Although, of course, in some languages, relations *are* operators.  
There's that pesky math vs. programming language dichotomy again.

[toc] | [prev] | [next] | [standalone]

#42546

On Mon, 01 Apr 2013 00:39:56 +0000, Alex wrote:

> Given that
> 
>   3
>  5
> 4
> 
> (i.e.: 4**5**3) is transitive,

I think you meant "associative", and exponentiation isn't associative,
i.e. (x**y)**z is not, in general, equal to x**(y**z). In fact, (x**y)**z
is equal to x**(y*z).

Conventional mathematical notation interprets the above example as
4**(5**3). (4**5)**3 would be written with 4**5 parenthesised. Python
follows that convention, as do most languages which have an infix
exponentiation operator.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web