New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

O(y + 1) = O(1) #9192

Closed
j2kun opened this Issue Mar 23, 2015 · 6 comments

Comments

Projects
None yet
5 participants
@j2kun
Copy link

j2kun commented Mar 23, 2015

I'm getting a very silly output from some simple big-O expressions involving O(1). I'm using Sympy 0.7.5, but I don't see anything in the release notes for 0.7.6 that addresses this issue.

    >>> y = Symbol('y')
    >>> O(y + 1)
    O(1)
    >>> x = O(1)
    >>> x * x
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python3.3/site-packages/sympy/core/decorators.py", line 77, in __sympifyit_wrapper
    return func(a, b)
  File "/usr/local/lib/python3.3/site-packages/sympy/core/decorators.py", line 118, in binary_op_wrapper
    return func(self, other)
  File "/usr/local/lib/python3.3/site-packages/sympy/core/expr.py", line 125, in __mul__
    return Mul(self, other)
  File "/usr/local/lib/python3.3/site-packages/sympy/core/cache.py", line 93, in wrapper
    r = func(*args, **kw_args)
  File "/usr/local/lib/python3.3/site-packages/sympy/core/operations.py", line 40, in __new__
    c_part, nc_part, order_symbols = cls.flatten(args)
  File "/usr/local/lib/python3.3/site-packages/sympy/core/mul.py", line 237, in flatten
    o, order_symbols = o.as_expr_variables(order_symbols)
  File "/usr/local/lib/python3.3/site-packages/sympy/series/order.py", line 284, in as_expr_variables
    if order_symbols[0][1] != self.point[0]:
IndexError: tuple index out of range
    >>> O(1) ** O(1) # should be O(1)
    O(1)**O(1) 

However, this one works, which is strange.

    >>> O(1) + y**y
    y**y + O(1)
@debugger22

This comment has been minimized.

Copy link
Member

debugger22 commented Apr 2, 2015

This was supposed to raise NotImplementedError but because of a bad check it fails just above it.

@debugger22

This comment has been minimized.

Copy link
Member

debugger22 commented Apr 2, 2015

No, my bad. This should give a genuine output.

debugger22 added a commit to debugger22/sympy that referenced this issue Apr 2, 2015

debugger22 added a commit to debugger22/sympy that referenced this issue Apr 15, 2015

@jcrist jcrist closed this in #9240 Apr 15, 2015

@hacman

This comment has been minimized.

Copy link
Contributor

hacman commented Apr 18, 2015

It was not addressed here that O(1+y) is expected to be O(1) since the limit is taken as y -> 0 by default. The sympy documentation could be more clear on this point. It does mention that the default limit is taken as the variable approaches 0, but it is the last line of the class doc string (for the Order class). Also, although there are examples, the documentation does not explain that you can substitute your own limit such as O(1+y, (y, oo)), which gives the O(y) that the original creator of this issue probably expected.

@jcrist

This comment has been minimized.

Copy link
Member

jcrist commented Apr 18, 2015

@hacman: if the docs on O are confusing, please open a new issue expressing your concerns.

@j2kun

This comment has been minimized.

Copy link

j2kun commented Apr 19, 2015

@hacman @jcrist I may be of a different mindset, but a big-O shouldn't ever evaluate to anything. Having a big-O "evaluate" to something is not helpful from a mathematical perspective. Nobody ever used a big-O to kill terms, but rather to bound some complicated expression asymptotically while still expressing the existence of that term to the reader. Big-O is not synonymous with taking a limit.

But even if you want big-O's to evaluate to something, the current behavior has consistency issues. If it makes sense for O(y+1) = O(1) (because by default y -> 0), then O(1+y, (y, oo)) should evaluate to oo. At the least, it would be helpful for me as a user if any implicit "limiting value" was expressed symbolically and not used to silently kill a term.

@toolforger

This comment has been minimized.

Copy link
Contributor

toolforger commented Apr 19, 2015

I'm having similar concerns as @j2kun, though I'm coming from a slightly different schoolbook definition.
By that definition, O is not merely a notational shorthand for an assumption; instead, O(whatever) is the class of functions that behave asymptotically the same as whatever.
By that definition, the shortest form to express an O expression is again an O expression, possibly simplified (i.e. O(x+1) could become O(x)).

What's unintuitive about O as it stands is that by default, it assumes that all symbols are constants.
Which makes O(x + x**2) equivalent to O(x), though readers would expect it to be O(x**2).
I think O as implemented ignores the common convention that if a formula contains just one free variable, it is supposed to be the limit.
I'm not sure that implementing that convention is a good idea; it could lead to unexpected behaviour.
I'd rather expect that to the standard assumptions, e.g. x, y, z, a, b, c, ... could be assumed to be free variables, while C would be assumed to be a constant. Though that would run counter to the conventions in the vector and physics modules, which routinely use A, B, C, ... for matrixes.

I guess the easiest thing to do would be to add a caveat to the docs, in that you must supply the free variable to O.

skirpichev added a commit to diofant/diofant that referenced this issue Jul 3, 2015

skirpichev added a commit to diofant/diofant that referenced this issue Jul 3, 2015

skirpichev added a commit to skirpichev/diofant that referenced this issue Nov 2, 2016

Add regression tests & mention closed issues
    close sympy/sympy#3112 (MrvAsympt was added in diofant#6)
    close sympy/sympy#9173 (test was added in 5a510ac)
    close sympy/sympy#9808 (fixed in 09e539b)
    close sympy/sympy#9341 (fixed in af98a00)
    close sympy/sympy#9908 (fixed in cc3fa8d)
    close sympy/sympy#6171 (test added in d278031)
    close sympy/sympy#9276 (diagnose_imports.py removed in ab8c535)
    close sympy/sympy#10201 (fixed in 0d0fc5f)
    close sympy/sympy#9057 (test was added in 8290a0c)
    close sympy/sympy#11159 (test was added in ffb76cb)
    close sympy/sympy#2839 (new AST transformers are used, see diofant#278 and diofant#167)
    close sympy/sympy#11081 (see ed01e16 and bb92329)
    close sympy/sympy#10974 (see 73fc425)
    close sympy/sympy#10806 (test in 539929a)
    close sympy/sympy#10801 (test in 2fe3da5)
    close sympy/sympy#9549 (test in 88bdefa)
    close sympy/sympy#4231 (test was added in fb411d5)
    close sympy/sympy#8634 (see 2fcbb58)
    close sympy/sympy#8481 (see 1ef20d3)
    close sympy/sympy#9956 (fixed in a34735f)
    close sympy/sympy#9747 (see e117c60)
    close sympy/sympy#7853 (see 3e4fbed)
    close sympy/sympy#9634 (see 2be03f5)
    close sympy/sympy#8500 (fixed in diofant#104 and finally in diofant#316)
    close sympy/sympy#9192 (see 9bf622f)
    close sympy/sympy#7130 (see e068fa3)
    close sympy/sympy#8514 (see b2d543b)
    close sympy/sympy#9334 (see 90de625)
    close sympy/sympy#8229 (see 9755b89)
    close sympy/sympy#8061 (see 7054f06)
    close sympy/sympy#7872 (tested in diofant#6)
    close sympy/sympy#3496 (tested in test_log_symbolic)
    close sympy/sympy#2929 (see da7db7a)
    close sympy/sympy#8203 (oo is not a real, see diofant#36)
    close sympy/sympy#7649 (0 is imaginary since diofant#8)
    close sympy/sympy#7256 (fixed in c0a4549)
    close sympy/sympy#6783 (see cb28d63)
    close sympy/sympy#5662 (is_integer issue fixed in 6bfa9f8, there is no is_bounded anymore)
    close sympy/sympy#5295 (fixed with diofant#354)
    close sympy/sympy#4856 (we now have flake/pep tests)
    close sympy/sympy#4555 (flake8 enabled after diofant#214)
    close sympy/sympy#5773 (cmp_to_key removed after diofant#164 and c9acbf0)
    close sympy/sympy#5484 (see above)

    Added regression tests:
    from https://groups.google.com/forum/#!topic/sympy/LkTMQKC_BOw
    fixes sympy/sympy#8825 (probably via diofant#209)
    fixes sympy/sympy#8635
    fixes sympy/sympy#8157
    fixes sympy/sympy#7872
    fixes sympy/sympy#7599
    fixes sympy/sympy#6179
    fixes sympy/sympy#5415
    fixes sympy/sympy#2865
    fixes sympy/sympy#5907
    fixes sympy/sympy#11722

    Closes diofant#347

skirpichev added a commit to skirpichev/diofant that referenced this issue Nov 2, 2016

Add regression tests & mention closed issues
    close sympy/sympy#3112 (MrvAsympt was added in diofant#6)
    close sympy/sympy#9173 (test was added in 5a510ac)
    close sympy/sympy#9808 (fixed in 09e539b)
    close sympy/sympy#9341 (fixed in af98a00)
    close sympy/sympy#9908 (fixed in cc3fa8d)
    close sympy/sympy#6171 (test added in d278031)
    close sympy/sympy#9276 (diagnose_imports.py removed in ab8c535)
    close sympy/sympy#10201 (fixed in 0d0fc5f)
    close sympy/sympy#9057 (test was added in 8290a0c)
    close sympy/sympy#11159 (test was added in ffb76cb)
    close sympy/sympy#2839 (new AST transformers are used, see diofant#278 and diofant#167)
    close sympy/sympy#11081 (see ed01e16 and bb92329)
    close sympy/sympy#10974 (see 73fc425)
    close sympy/sympy#10806 (test in 539929a)
    close sympy/sympy#10801 (test in 2fe3da5)
    close sympy/sympy#9549 (test in 88bdefa)
    close sympy/sympy#4231 (test was added in fb411d5)
    close sympy/sympy#8634 (see 2fcbb58)
    close sympy/sympy#8481 (see 1ef20d3)
    close sympy/sympy#9956 (fixed in a34735f)
    close sympy/sympy#9747 (see e117c60)
    close sympy/sympy#7853 (see 3e4fbed)
    close sympy/sympy#9634 (see 2be03f5)
    close sympy/sympy#8500 (fixed in diofant#104 and finally in diofant#316)
    close sympy/sympy#9192 (see 9bf622f)
    close sympy/sympy#7130 (see e068fa3)
    close sympy/sympy#8514 (see b2d543b)
    close sympy/sympy#9334 (see 90de625)
    close sympy/sympy#8229 (see 9755b89)
    close sympy/sympy#8061 (see 7054f06)
    close sympy/sympy#7872 (tested in diofant#6)
    close sympy/sympy#3496 (tested in test_log_symbolic)
    close sympy/sympy#2929 (see da7db7a)
    close sympy/sympy#8203 (oo is not a real, see diofant#36)
    close sympy/sympy#7649 (0 is imaginary since diofant#8)
    close sympy/sympy#7256 (fixed in c0a4549)
    close sympy/sympy#6783 (see cb28d63)
    close sympy/sympy#5662 (is_integer issue fixed in 6bfa9f8, there is no is_bounded anymore)
    close sympy/sympy#5295 (fixed with diofant#354)
    close sympy/sympy#4856 (we now have flake/pep tests)
    close sympy/sympy#4555 (flake8 enabled after diofant#214)
    close sympy/sympy#5773 (cmp_to_key removed after diofant#164 and c9acbf0)
    close sympy/sympy#5484 (see above)

    Added regression tests:
    from https://groups.google.com/forum/#!topic/sympy/LkTMQKC_BOw
    fixes sympy/sympy#8825 (probably via diofant#209)
    fixes sympy/sympy#8635
    fixes sympy/sympy#8157
    fixes sympy/sympy#7872
    fixes sympy/sympy#7599
    fixes sympy/sympy#6179
    fixes sympy/sympy#5415
    fixes sympy/sympy#2865
    fixes sympy/sympy#5907
    fixes sympy/sympy#11722

    Closes diofant#347
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment