Factorial and Memoizing

Just saw this post. Tried to comment there, but it failed.

As I understand it, Perl 6 is supposed to have a memoizer built-in, something like sub fact is cached ($n). But that definitely isn't implemented in Rakudo yet.

There is an interesting way to do this that does work in Rakudo:

> my $fact = gather { take 1; my $a = 1; for 1..* { $a *= $_; take $a + 0 } }; say $fact[3];
6
> say $fact[3]
6
> say $fact[4]
24
> say $fact[10]
3628800
> say $fact.munch(20).perl
(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6.402373705728e+15, 1.21645100408832e+17)

That defines $fact as a lazy list of the factorials, which you can then access as, say, $fact[10] (for 10!). The list will only contain actual values for the factorials you have asked for (and any others needed to compute those).

Edited to add: Just realized there is (almost?) an easier way of doing this.

> my $fact = [\*] 1..*; say $fact[3]
24
> $fact.munch(20).perl
(1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6.402373705728e+15, 1.21645100408832e+17, 2.43290200817664e+18)

As you can see, this is a much cleaner way of generating the list, but the indices are now off by one.

About these ads

6 Responses to “Factorial and Memoizing”

  1. Eddward Says:

    I don’t have perl6 installed at work. Would the following work?

    my $fact = 1, [\*] 1..*;

    • colomon Says:

      I tried that first and it failed. :(

    • Pm Says:

      Note that it would need to be parenthesized, because of item assignment:

      my $fact = (1, [\*] 1..*);

      It still doesn’t work (yet?), because itemizing the Parcel tends to make it eager, so we end up evaluating an infinite list. But the following does work:

      my $fact = (1, [\*] 1..100);

      which at least gets you to 100 factorial, and doesn’t take forever to do it. :-)

      Pm

  2. RobertS Says:

    This works for me:

    my $fact = [\*] 1,1..*;
    say $fact.munch(20).perl;

    (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6.402373705728e+15, 1.21645100408832e+17)

  3. Lanny Ripple Says:

    Also

    my $fact := (1, [\*] 1..*);
    say $fact[0..10].perl;

    (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: