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

[morphex]

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.Traceback (most recent call last):

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

Happy Easter!

-Morten

 

[Steven D'Aprano]

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.Traceback (most recent call last):
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.)

 

[Dave Angel]

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.Traceback (most recent call last):

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.

1

 

[Dave Angel]

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
1L
1**2**3**4**5

Traceback (most recent call last):
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.

 

[morphex]

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?

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.




Traceback (most recent call last):

File "<stdin>", line 1, in <module>

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.)

 

[Dave Angel]

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.

 

[Roy Smith]

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?

 

[Roy Smith]

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.

 

[Roy Smith]

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

 

[Alex]

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

 

[Chris Angelico]

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

 

[Chris Angelico]

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.)

Though your point about 6.14 is still true. It states the order that
the integers will be evaluated in. Note one of the examples given:

expr1 + expr2 * (expr3 - expr4)

The evaluation of the expression starts with 3 and 4, then picks up 2,
then 1, but the operands themselves are evaluated left to right.

ChrisA

 

[Dave Angel]

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

On the page you reference, in section 6.14, see the 4th entry:

expr1 + expr2 * (expr3 - expr4)

expr1 is evaluated before expr2, but the multiply happens before the add.

Now see the following paragraph (6.15):

"""
The following table summarizes the operator precedences in Python, from
lowest precedence (least binding) to highest precedence (most binding).
Operators in the same box have the same precedence. Unless the syntax is
explicitly given, operators are binary. Operators in the same box group
left to right (except for comparisons, including tests, which all have
the same precedence and chain from left to right — see section
Comparisons — and exponentiation, which groups from right to left).
"""

What this paragraph refers to as "grouping" is commonly called
associativity in other languages.

There are three different concepts here that apply whenever an
expression has more than one term:

1) evaluation order is important for terms lie function calls which have
side effects
2) precedence, lie where multiply will happen before add
3) associativity, where the order of operations for operators with the
same precedence are done either left to right (usually), or right to
left (like exponentiation)

 

[Alex]

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.

 

[Chris Angelico]

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

 

[Steven D'Aprano]

Chris Angelico wrote:



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.

 

[Roy Smith]

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.

 

[Chris Angelico]

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

 

[Nobody]

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.