Hi all, I figures out that the maximum number for which MATLAB can give an answer to factorial is 170. This triggered a thought in my mind I want to share with you guys. What if I take number in character string form as input to factorial, extract the number sequence as number array use convolution to do multiplication and then given the answer back in character? In this way the max range can be increased many fold! I've two questions concerning the above problem, 1. Would such implementation be useful/beneficial to anyone? 2. Has it been done before? If yes what is it called?
multiplication of large numbers using convolution
Started by ●January 30, 2012
Reply by ●January 30, 20122012-01-30
On Jan 30, 1:22�pm, mobi <mob...@gmail.com> wrote:> Hi all, > I figures out that the maximum number for which MATLAB can give an answer to factorial is 170. This triggered a thought in my mind I want to share with you guys. > What if I take number in character string form as input to factorial, extract the number sequence as number array use convolution to do multiplication and then given the answer back in character? In this way the max range can be increased many fold! > I've two questions concerning the above problem, > 1. Would such implementation be useful/beneficial to anyone? > 2. Has it been done before? If yes what is it called?Please describe how that would be more efficient or easier than performing n*(n-1)*(n-2)...*2 ?
Reply by ●January 30, 20122012-01-30
On Jan 30, 8:22�am, mobi <mob...@gmail.com> wrote:> Hi all, > I figures out that the maximum number for which MATLAB can give an answer to factorial is 170. This triggered a thought in my mind I want to share with you guys. > What if I take number in character string form as input to factorial, extract the number sequence as number array use convolution to do multiplication and then given the answer back in character? In this way the max range can be increased many fold! > I've two questions concerning the above problem, > 1. Would such implementation be useful/beneficial to anyone? > 2. Has it been done before? If yes what is it called?Certainly convolution may be used for mutliplying large numbers. Typically when one needs very large factorials, they may work with log(n!) or use Stirling's approximation. How often do you really need more than 170 digits of precision? Some cryptographic schemes are based on modular arithmetic and RSA for example works with modular exponentiation. The modular muliplication is often sped up via Montgomery reduction. These large number cryptographic schemes rely on the "trap door" aspect that factoring a large number that is the product of two unknown primes is much harder than simply multiplying two primes together. These schemes often work with 256 to 4096 digit numbers. Clay
Reply by ●January 30, 20122012-01-30
Certainly less efficient and more difficult, but imagine someone using MATLAB can go till only 170 factorial, however using the above mentioned method he might easily go till even 300. So its a matter of making something available that is not there.
Reply by ●January 30, 20122012-01-30
On Jan 30, 8:22�am, mobi <mob...@gmail.com> asked:> 1. Would such implementation be useful/beneficial to anyone?YES, and several people have done such implementations. Whether a **MATLAB** implementation would be useful is another question, to which the answer may well be NO.> 2. Has it been done before? If yes what is it called?YES, Search for multiple-precision arithmetic on the Internet. See what the high-precision calculator utility bc on a UNIX system does. Read the subchapter titled something like "How Fast Can We Multiply?" in D. E. Knuth's "The Art of Computer Programming, vol. 2, Semi-Numerical Algorithms" Dilip Sarwate
Reply by ●January 30, 20122012-01-30
Clay <clay@claysturner.com> wrote: (snip)> Certainly convolution may be used for mutliplying large numbers. > Typically when one needs very large factorials, they may work with > log(n!) or use Stirling's approximation. How often do you really need > more than 170 digits of precision?Possibly interesting to this group, there is an FFT based algorithm commonly used when multiplying really large numbers. The multiply algorithm we learned in 3rd grade is O(n**2) for multplying two n digit numbers. I believe the FFT based algorithm, like most things with FFT, is O(n log n). It seems that pi has now been calculated to 10 trillion (1e13 for those in some other countries). If you google for it, you should find some explanation on how they do it. A fair amount of the time is the binary to decimal conversion, which uses a lot of multiplication. Interestingly, there is an algorithm that will give specific base 16 digits of pi without computing all the digits in between. That is used to help verify the calculation done using other methods. -- glen
Reply by ●January 30, 20122012-01-30
On 1/30/2012 10:16 AM, dvsarwate wrote:> On Jan 30, 8:22 am, mobi<mob...@gmail.com> asked: > >> 1. Would such implementation be useful/beneficial to anyone? > > YES, and several people have done such implementations. > Whether a **MATLAB** implementation would be useful is > another question, to which the answer may well be NO. > >> 2. Has it been done before? If yes what is it called? > > YES, Search for multiple-precision arithmetic on the Internet. > See what the high-precision calculator utility bc on a UNIX > system does. Read the subchapter titled something like > "How Fast Can We Multiply?" in D. E. Knuth's "The Art > of Computer Programming, vol. 2, Semi-Numerical Algorithms"Also, recognize that Matlab's limit arises not from an inability to calculate, but from not being able to represent the result in their standard format. How would _you_ represent 200! ? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●January 30, 20122012-01-30
On Jan 30, 12:18�pm, Jerry Avins <j...@ieee.org> demanded:> How would _you_ represent 200! ?I have never thought about the question, but I do see the becessity of being able to compute 200! and similar large numbers so that I can calculate, for example, the probability of one Head when a fair coin is tossed 200 times. From the formula in my book, I know that I have to calculate [200!/199!1!]2^{-200} but I am having difficulty doing this in MATLAB which will not evaluate 200! and 199! for me. So, I cannot get the answer given in the back of the book which says the probability is 25*2^{-203}. Can you help? :-)
Reply by ●January 30, 20122012-01-30
On 1/30/2012 12:57 PM, dvsarwate wrote:> On Jan 30, 12:18 pm, Jerry Avins<j...@ieee.org> demanded: > >> How would _you_ represent 200! ? > > I have never thought about the question, but I do see the > becessity of being able to compute 200! and similar large > numbers so that I can calculate, for example, the probability > of one Head when a fair coin is tossed 200 times. From the > formula in my book, I know that I have to calculate > [200!/199!1!]2^{-200} but I am having difficulty doing this > in MATLAB which will not evaluate 200! and 199! for me. So, > I cannot get the answer given in the back of the book which > says the probability is 25*2^{-203}. Can you help? :-)I think I can help. My handy-dandy bignum package gives 200!/199! as 200, surprisingly enough. Computers are great! Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●January 30, 20122012-01-30
On Jan 30, 11:38�am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> Clay <c...@claysturner.com> wrote: > > (snip) > > > Certainly convolution may be used for mutliplying large numbers. > > Typically when one needs very large factorials, they may work with > > log(n!) or use Stirling's approximation. How often do you really need > > more than 170 digits of precision? > > Possibly interesting to this group, there is an FFT based algorithm > commonly used when multiplying really large numbers. > > The multiply algorithm we learned in 3rd grade is O(n**2) for > multplying two n digit numbers. I believe the FFT based algorithm, > like most things with FFT, is O(n log n). > > It seems that pi has now been calculated to 10 trillion (1e13 for > those in some other countries). �If you google for it, you should > find some explanation on how they do it. A fair amount of the time > is the binary to decimal conversion, which uses a lot of multiplication. > > Interestingly, there is an algorithm that will give specific base 16 > digits of pi without computing all the digits in between. That is used > to help verify the calculation done using other methods. > > -- glenI recall Borwein's formula that picks out digits of pi in base 16. I don't think they (Borwein and Borwein) have found a base 10 version of the digit selector formula. Clay
