develooper Front page | | Postings from August 2002

Re: Factorial and large numbers.

Thread Previous | Thread Next
Markus Laire
August 8, 2002 11:54
Re: Factorial and large numbers.
Message ID:

> 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

Initialize $z to 1, repeat for 1..pop with variable $_

Remove all except last 9 (or so) digits from $z, and then multiply 
with $_ saving result to $_

This matches zeroes at the end of $_, so everything except
the zeroes will be in special 'pre-match' variable  $`

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)

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 

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' <>

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About