"Pascal's Triangle" generator using "Binomial Theorem"
Author 
Message 
randint

Posted: Sun Nov 18, 2012 11:45 am Post subject: "Pascal's Triangle" generator using "Binomial Theorem" 


One extension of my factorial program, using the formula (n choose k) = n! / ((n  k)! k!) [combinations]
Generated by iteration as opposed to recursion due to reasons of "bad" computational complexity.
Description: 
Pascal's Triangle generated by the Binomial Theorem 

Download 
Filename: 
Pascals_Triangle.java 
Filesize: 
1.47 KB 
Downloaded: 
489 Time(s) 






Sponsor Sponsor



DemonWasp

Posted: Sun Nov 18, 2012 1:03 pm Post subject: RE:"Pascal\'s Triangle" generator using "Binomial Theorem" 


This solution isn't any better than the recursive method. You're still recalculating 5! when you calculate 6!, even when you've previously calculated 5!.
To truly do better, you need to add some storage: an array of BigIntegers. Then, when you compute factorial(n), if array(n) isn't null, then you can just return array(n). If it is null, then you can recursively compute factorial(n1), multiply it by n, and store it in array(n).
Then when you ask for 6!, it also calculates 5!, 4!, 3!, 2! and stores them in the array (note: you should put 1! in the array before you do any computation; that's your base case). When you ask for 5!, you already know the value.







