{"head":"2fc6b58f791a6bc31c7fbab576d4ab4d8a86841f","size":3,"push_id":46709617,"ref":"refs/heads/and","commits":[{"sha":"2499c468b446b81d50bd3e440049120c4b021484","author":{"name":"Chris Smith","email":"b274abc493535ae88cb3a0742f63e38c9241d67c@gmail.com"},"url":"https://api.github.com/repos/smichr/sympy/commits/2499c468b446b81d50bd3e440049120c4b021484","message":"2607: more efficient implementation of Add.as_numer_denom\n\nComputing the numerator and common denominator of an Add\nis significantly speeded up if a binary aproach is taken\nto compute the result.\n\n    1/a + 2/b + 3/c + 4/d\n=   (b+2*a)/(a*b) + (3*d + 4*c)/(c*d)\n=   ((b + 2*a)*(c*d) + (3*d + 4*c)*(a*b))/(a*b*c*d)\n\nThe problem is that this leads to a nesting in proportion to\nthe log(n, 2) of the number of terms, n. And if someone wants\nthe unnested numerator then the costly expansion will make the\nfinal result more costly than if the more naive approach were\ntaken. But sometimes there would be nesting anyway from the\nnaive method:\n\n    1/(a+b) + 1/c + 1/d -> (c*d + (a+b)*d + (a+b)*c)/((a+b)*c*d)\n\nSo in order to make the routine faster a hybrid aproach is taken\nwhere the old method is used if there wouldn't be nesting produced\n(when denominators are not Add or a Add-free Muls).\n\nNo gcd of denominators is computed since deciding whether the overhead\nis worth the benefit should be left with the user. The testing for\nequal denominators here is relatively fast so the overhead for this\nis small but the payoff big.\n\nHere are some examples of the old and new behavior:\n\n    # old and new methods give same result if...\n\n    all denoms are Integers (new method used since the Integer autodistributes\n    and doesn't lead to additional nesting\n    >>> (x/3+y/4+z/7+a/5).as_numer_denom()\n    (84*a + 140*x + 105*y + 60*z, 420)\n\n    there are no Add factors in bases (old method used)\n    >>> (x/3+y/4+z/7+a/b).as_numer_denom()\n    (84*a + 28*b*x + 21*b*y + 12*b*z, 84*b)\n\n    # new method gives faster result if nesting would have resulted anyway\n    # or if there is a common denominator\n\n    >>> (x/(b+1)+y/(b+1)+z/(b+1)+a/(b+1)).as_numer_denom()\n    (a + x + y + z, b+1)\n    # old method gave\n    # (a*(b+1)**3 + x*(b+1)**3 + y*(b+1)**3 + z*(b+1)**3, (b+1)**4)\n\n    >>> (x/(b+1)+y/(b+1)+z/(b+1)+a/b).as_numer_denom()\n    (a*(b+1) + b*(x + y + z), b*(b+1))\n    # old method gave\n    # (a*(b+1)**3 + b*x*(b+1)**2 + b*y*(b+1)**2 + b*z*(b+1)**2, b*(b+1)**3)\n    #\n    # note that common denominators are collected so there are only two terms\n    # in the denominator from the new method"},{"sha":"9d680204ded08fe97d480c1f5532516f10f3dff8","author":{"name":"Chris Smith","email":"b274abc493535ae88cb3a0742f63e38c9241d67c@gmail.com"},"url":"https://api.github.com/repos/smichr/sympy/commits/9d680204ded08fe97d480c1f5532516f10f3dff8","message":"minor edits of mul.py\n\n    The as_power_dict is made more efficient by computing the result\n    once all the terms have been assembled rather than one at a time."},{"sha":"2fc6b58f791a6bc31c7fbab576d4ab4d8a86841f","author":{"name":"Chris Smith","email":"b274abc493535ae88cb3a0742f63e38c9241d67c@gmail.com"},"url":"https://api.github.com/repos/smichr/sympy/commits/2fc6b58f791a6bc31c7fbab576d4ab4d8a86841f","message":"2644: expand_mul will now return flat result\n\n    The terms that are added after being multiplied to see whether\n    a new Add needs to be expanded."}],"legacy":{"head":"2fc6b58f791a6bc31c7fbab576d4ab4d8a86841f","size":3,"push_id":46709617,"shas":[["2499c468b446b81d50bd3e440049120c4b021484","smichr@gmail.com","2607: more efficient implementation of Add.as_numer_denom\n\nComputing the numerator and common denominator of an Add\nis significantly speeded up if a binary aproach is taken\nto compute the result.\n\n    1/a + 2/b + 3/c + 4/d\n=   (b+2*a)/(a*b) + (3*d + 4*c)/(c*d)\n=   ((b + 2*a)*(c*d) + (3*d + 4*c)*(a*b))/(a*b*c*d)\n\nThe problem is that this leads to a nesting in proportion to\nthe log(n, 2) of the number of terms, n. And if someone wants\nthe unnested numerator then the costly expansion will make the\nfinal result more costly than if the more naive approach were\ntaken. But sometimes there would be nesting anyway from the\nnaive method:\n\n    1/(a+b) + 1/c + 1/d -> (c*d + (a+b)*d + (a+b)*c)/((a+b)*c*d)\n\nSo in order to make the routine faster a hybrid aproach is taken\nwhere the old method is used if there wouldn't be nesting produced\n(when denominators are not Add or a Add-free Muls).\n\nNo gcd of denominators is computed since deciding whether the overhead\nis worth the benefit should be left with the user. The testing for\nequal denominators here is relatively fast so the overhead for this\nis small but the payoff big.\n\nHere are some examples of the old and new behavior:\n\n    # old and new methods give same result if...\n\n    all denoms are Integers (new method used since the Integer autodistributes\n    and doesn't lead to additional nesting\n    >>> (x/3+y/4+z/7+a/5).as_numer_denom()\n    (84*a + 140*x + 105*y + 60*z, 420)\n\n    there are no Add factors in bases (old method used)\n    >>> (x/3+y/4+z/7+a/b).as_numer_denom()\n    (84*a + 28*b*x + 21*b*y + 12*b*z, 84*b)\n\n    # new method gives faster result if nesting would have resulted anyway\n    # or if there is a common denominator\n\n    >>> (x/(b+1)+y/(b+1)+z/(b+1)+a/(b+1)).as_numer_denom()\n    (a + x + y + z, b+1)\n    # old method gave\n    # (a*(b+1)**3 + x*(b+1)**3 + y*(b+1)**3 + z*(b+1)**3, (b+1)**4)\n\n    >>> (x/(b+1)+y/(b+1)+z/(b+1)+a/b).as_numer_denom()\n    (a*(b+1) + b*(x + y + z), b*(b+1))\n    # old method gave\n    # (a*(b+1)**3 + b*x*(b+1)**2 + b*y*(b+1)**2 + b*z*(b+1)**2, b*(b+1)**3)\n    #\n    # note that common denominators are collected so there are only two terms\n    # in the denominator from the new method","Chris Smith"],["9d680204ded08fe97d480c1f5532516f10f3dff8","smichr@gmail.com","minor edits of mul.py\n\n    The as_power_dict is made more efficient by computing the result\n    once all the terms have been assembled rather than one at a time.","Chris Smith"],["2fc6b58f791a6bc31c7fbab576d4ab4d8a86841f","smichr@gmail.com","2644: expand_mul will now return flat result\n\n    The terms that are added after being multiplied to see whether\n    a new Add needs to be expanded.","Chris Smith"]],"ref":"refs/heads/and"}}