Re: Factorial and large numbers.

En 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 _/`hakespeare

• 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