From:

Date:

August 8, 2002 11:54Subject:

Re: Factorial and large numbers.Message ID:

3D52E88C.16537.23333D2@localhost> 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. You need to regex last zeroes AND remove extra numbers in the beginning keeping only last 6 (or so) numbers. > What does $`%9e9 do? 9e9 == 9000000000 and 1e6 == 1000000 $` %9e9 gives the remainder when variable $` is divided with 9e9, which in effect returns only last 9 (or so) digits of $` $`%1e6 is better example as it returns exactly last 6 digits of $`. This is used to limit the size of the number so it can't grow too big. 6 digits is enough precision for this problem and 9e9 only gives better tiebreaker score. $` is special 'pre-match' variable which contains string preceding whatever was matched by the last successful pattern match. I can annotate shortly my best solution: #!perl -l $_*=$z%9e9,/0*$/,$z=$`for++$z..pop;print$z%10 for++$z..pop Initialize $z to 1, repeat for 1..pop with variable $_ $_*=$z%9e9 Remove all except last 9 (or so) digits from $z, and then multiply with $_ saving result to $_ /0*$/ This matches zeroes at the end of $_, so everything except the zeroes will be in special 'pre-match' variable $` $z=$` Copy $` to $z, to be ready for next iteration. This must be done because print-command can't use $` variable as it's hidden inside for- loop. (best factorial solution seemed to get over this) print$z%10 And finally print the last digit I can't resist mentioning my other solution which doesn't compute n! at all, but just uses kind-of 3D lookup-table to find the result. It's fast but unfortunately code is far too long :( $z=pop;sub g{vec"\x10\xd7\xa9\x98b\xef",pop,2} print$z<2||(1+g$z%25)*(1,3,2,4)[g 24-$z/25%25]*6*(1+g$z/625)%10,$/ Explanation would be somewhat longer, but if anyone wants I can write it. Has anyone else tried lookup instead of computing n!. I'd like to know shortest possible solution for this sub-problem also. -- Markus Laire 'malaire' <markus.laire@nic.fi>Thread 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