Right, balancing the multiplication tree can be a win, for the reasons you give.
But, I don't think your code snippet is doing any of that. If I run a version (attached) that prints out the multiplies it evaluates, (fact 100) gives: (2 . 1) (3 . 2) (4 . 6) (5 . 24) (6 . 120) (7 . 720) (8 . 5040) . . . (100 . 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000) On Thursday, May 15, 2014 9:22:07 AM UTC-7, Richard Fateman wrote: > > > Gee, this is getting long. > > Here's the deal on the improved factorial. Perhaps you just haven't > gotten large enough, or your multiplications are too slow, even for small > numbers. > Or there is something else odd about your program that I don't see. > Certainly n=20 is way too small > to be interesting. You haven't even gotten to get to places where "fast" > methods of integer multiplication > are better than naive methods. > > If you read the post by Peter L. it will explain more, and you might > find it interesting > that to get much better in computing fact(n), his best method ends up > factoring the integer n, first. At least > that's what I recall. > > So the question is, if that 2-argument factorial still does linear > recursion, what's the payoff? > > Here's the payoff. > multiplying a (small) integer j by a (long, multi-word) arbitrary > precision integer k takes time > essentially O(size(k)). It gets to your goal faster if the small integer > is as large as possible > and still a small integer. > > Do you want to do > > big2= 12* small > big3= 13* big2 > big4 =14* big3 > big 100 = 110* big99 at a cost of 100 small X big multiplies? > > or do you want to do > small2= 12* 13 > small3 = small2*14 > small4= small3* 14 > .... mostly small arithmetic for a while... > > and then do big ones for a while. at a cost of N small multiplies, > and fewer big multiplies. > > > > > ..... etc > > Have fun. > > RJF > > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/0f084bf7-af04-4e7a-adb3-a7109184ebc7%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
fateman_fact.l
Description: Binary data
