{"issue":{"state":"open","pull_request":{"diff_url":"https://github.com/sympy/sympy/pull/669.diff","html_url":"https://github.com/sympy/sympy/pull/669","patch_url":"https://github.com/sympy/sympy/pull/669.patch"},"milestone":null,"user":{"avatar_url":"https://secure.gravatar.com/avatar/61e106a28e171b4407171702b182759f?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","gravatar_id":"61e106a28e171b4407171702b182759f","url":"https://api.github.com/users/smichr","login":"smichr","id":90703},"assignee":null,"updated_at":"2011-11-15T19:47:32Z","labels":[],"closed_at":null,"comments":72,"url":"https://api.github.com/repos/sympy/sympy/issues/669","body":"see\r\n\r\n\r\nhttp://code.google.com/p/sympy/issues/detail?id=2607\r\n\r\n\r\n\r\n","html_url":"https://github.com/sympy/sympy/issues/669","title":"new as_numer_denom","number":669,"id":1992423,"created_at":"2011-10-19T10:15:53Z"},"action":"created","comment":{"user":{"avatar_url":"https://secure.gravatar.com/avatar/06e8f668ca62cbe8a49b53bede84dec1?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","gravatar_id":"06e8f668ca62cbe8a49b53bede84dec1","url":"https://api.github.com/users/pernici","login":"pernici","id":759243},"updated_at":"2011-11-15T19:47:32Z","url":"https://api.github.com/repos/sympy/sympy/issues/comments/2750126","body":"Above I suggested to consider the special case in which all the denominators are one; the proposed\r\nmodification slows down the other cases;  a better code seems to be\r\n\r\n```\r\n        # separate out those that are Integers\r\n        nnum = []\r\n        dnum = []\r\n        b1 = True\r\n        one = S.One\r\n        for d, n in nd.items():\r\n            nd[d] = Add(*nd[d])\r\n            b1 = (b1 and (d is one))\r\n            if d.is_Integer:\r\n                nnum.append(nd.pop(d))\r\n                dnum.append(int(d))\r\n        if b1:\r\n            return (self, one)\r\n```\r\n\r\n```\r\na = Add(*[x**i/factorial(i) for i in xrange(1,500)])\r\nr = a.as_numer_denom()\r\n```\r\n\r\ntakes 0.12s in the former case,  0.08 in the latter case, the same as in the best version.\r\n\r\nI wrote a version in which there is no extra nesting, as in master; however it is a bit slow, e.g. in the above example\r\nit takes 0.11s\r\n\r\n```\r\n    def as_numer_denom(self):\r\n        # collect numerators and denominators of the terms\r\n        fand = [f.as_numer_denom() for f in self.args]\r\n        numers, denoms = zip(*fand)\r\n        one = S.One\r\n        if denoms.count(one) == len(denoms):\r\n            return (self, one)\r\n\r\n        # separate out those that are Integers\r\n        numers1, denoms1, numers2, denoms2 = [], [], [], []\r\n        for ni, di in fand:\r\n            if di.is_Integer:\r\n                numers2.append(ni)\r\n                denoms2.append(int(di))\r\n            else:\r\n                numers1.append(ni)\r\n                denoms1.append(di)\r\n\r\n        # process the Number denominators efficiently\r\n        if numers2:\r\n            den = S(reduce(ilcm, denoms2, 1))\r\n            resid = [den/di for di in denoms2]\r\n\r\n            numers_nd = [resid[i]*ni for i, ni in enumerate(numers2)]\r\n        else:\r\n            den, numers_nd = one, []\r\n\r\n        if len(numers1) + len(numers_nd) == 1:\r\n            if numers1:\r\n               n, d = numers1[0], denoms1[0]\r\n            else:\r\n               n, d = numers_nd[0], den\r\n\r\n        else:\r\n            a1 = [Mul(*(denoms1[:i]+[numers1[i]*den]+denoms1[i+1:]))\r\n                  for i in xrange(len(numers1))]\r\n            den1 = Mul(*denoms1)\r\n            a2 = [x*den1 for x in numers_nd]\r\n            n, d = Add(*(a1 + a2)), den*den1\r\n\r\n        return n, d\r\n```\r\n\r\n@asmeuer \r\n> Have any if your benchmarks looked at the case where the denominators are Adds, or Muls with Adds (i.e., polynomials, or partially factorized polynomials)? It think that real life examples will tend to have that. \r\n\r\nCan you point me out some real life example which needs to be made much faster?  \r\nDifferent algorithms will work better for particular types of expressions.\r\nThe algorithm in this branch has little overhead, so it is nice as a generic algorithm, but it sufficient to change a bit\r\nthe above example and it takes stalls (I stopped it after 150s because it occupied all the memory)\r\n\r\n```\r\na = Add(*[x**i/(y**i*factorial(i)) for i in xrange(1,500)])\r\n```\r\n\r\nIt is easy to make this fast, but the algorithm would be slower in other cases. The algorithm in my `and` branch\r\nworks well when symbolic lcm is needed. \r\n","id":2750126,"created_at":"2011-11-15T19:47:32Z"}}