Front page | perl.golf | Postings from August 2002

## Re: Factorial and large numbers.

From:
Markus Laire
Date:
August 8, 2002 11:54
Subject:
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>

```