From:

Date:

August 8, 2002 11:33Subject:

Re: Factorial and large numbers.Message ID:

20020808183241.GA23751@ruunat.phys.uu.nlEn op 08 augustus 2002 sprak Tor Hildrum: > Could someone annotate some of the various working solutions, emphasizing > how they work around the problem with large numbers? > > I was able to make solutions that worked for n! where n < 25. > But, at 25! the numbers got to large. I tried regex'ing the last zeroes, > without success. I was still loosing digits. Let's print out the complete factorials: #!perl -l $a=1;$a=$a*$_,print"$_\t$a"for 1..26 1 1 2 2 3 6 .... 15 1307674368000 16 20922789888000 17 355687428096000 18 6.402373705728e+15 19 1.21645100408832e+17 20 2.43290200817664e+18 21 5.10909421717094e+19 22 1.12400072777761e+21 23 2.5852016738885e+22 24 6.20448401733239e+23 25 1.5511210043331e+25 26 4.03291461126606e+26 As you can see, the main problem is not the 0's at the end. It's the number of initial digits that gets to large. The number of significant digits grows, and for 22! perl can't store all of them anymore. Fortunately, you dont need the most significant digits to calculate the next factorials, so it's safe to throw them away, using the modulus operator, %. '$a%$b' returns the remainder of $a diveded by $b, for example: 5%2 => 1 (5/2 equals 2, with a remainder 1) 20%3 => 2 (20/3 equals 6, remainder 2) 12345%100 => 45 (12345/100 = 123, remainder 45) So $a%1000000000 removes all but the last 9 digits of $a. And the number 1000000000 can be written as 1e9. This removes both the 0's and the superfluous most significant digits, #!perl -l $a=1;$a=$a*$_%1e9,$a=~s/0*$//,print"$_\t$a"for 1..26 > -p $v=$_;for($_=1;$v>0;){$_*=$v--}s/0//g;$_=chop."\n" The substitution needs to be done *inside* the loop, and you can't just delete all 0's. (Try replacing the 's/0*$//' in my program with 's/0//g' to see why it fails for large N.) Also, you can only use -p if your script takes the input on STDIN. In this case, the input was given as an argument on the command line, which is why you have to use 'pop' to get it. > I also hate $_=chop."\n", but couldn't figure out anything else. -l. Always try -l when you have to print newlines.. > Couldn't even get a working solution on my virgin hole :) I wonder how many spam filters you set off with this mail... (-ugene -- Brevity is the soul of wit. -- \\/illiam _/`hakespeareThread Previous | Thread Next

- Factorial and large numbers. by Tor Hildrum
- Re: Factorial and large numbers. by Markus Laire
- Re: Factorial and large numbers. by perl-golf
- Re: Factorial and large numbers. by Markus Laire
- Re: Factorial and large numbers. by Stephen Turner
**Re: Factorial and large numbers.**by Eugene van der Pijll- Re: Factorial and large numbers. by Tor Hildrum

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About