view release on metacpan or  search on metacpan

lib/Math/NumSeq/Factorials.pm  view on Meta::CPAN

=head2 Iterating

=over

=item C<$seq-E<gt>seek_to_i($i)>

Move the current sequence position to C<$i>.  The next call to C<next()>
will return C<$i> and corresponding value.

=back

=head2 Random Access

=over

=item C<$value = $seq-E<gt>ith($i)>

Return C<1*2*...*$i>.  For C<$i==0> this is considered an empty product and
the return is 1.

=item C<$bool = $seq-E<gt>pred($value)>

Return true if C<$value> is a factorial, ie. equal to C<1*2*...*i> for
some i.

=item C<$i = $seq-E<gt>value_to_i($value)>

=item C<$i = $seq-E<gt>value_to_i_floor($value)>

Return the index i of C<$value>.  If C<$value> is not a factorial then
C<value_to_i()> returns C<undef>, or C<value_to_i_floor()> the i of the next
lower value which is or C<undef> if C<$value E<lt> 1>.

=item C<$i = $seq-E<gt>value_to_i_estimate($value)>

Return an estimate of the i corresponding to C<$value>.

=back

=head1 FORMULAS

=head2 Value to i Estimate

The current code uses Stirling's approximation

    log(n!) ~= n*log(n) - n

by seeking an i for which the target factorial "value" has

    i*log(i) - i == log(value)

Newton's method is applied to solve for i,

    target=log(value)
    f(x) = x*log(x) - x - target      wanting f(x)=0
    f'(x) = log(x)

    iterate next_x = x - f(x)/f'(x)
                   = (x+target)/log(x)

Just two iterations is quite close

    target = log(value)
    i0 = target
    i1 = (i0+target)/log(target)
       = 2*target/log(target)
    i2 = (i1+target)/log(i1)

    i ~= int(i2)

=head1 SEE ALSO

L<Math::NumSeq>,
L<Math::NumSeq::Primorials>

L<Math::BigInt> (C<bfac()>),
L<Math::Combinatorics> (C<factorial()>,
L<Math::NumberCruncher> (C<Factorial()>
L<Math::BigApprox> (C<Fact()>

=head1 HOME PAGE

L<http://user42.tuxfamily.org/math-numseq/index.html>

=head1 LICENSE

Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
more details.

You should have received a copy of the GNU General Public License along with
Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.

=cut