SequenceProvider::nthFibonacciNumber() - Code Metrics - JordanRL/Fermat - Measure and Improve Code Quality continuously with Scrutinizer

SequenceProvider::nthFibonacciNumber() A
last analyzed 2022-10-22 04:55 UTC

↳ Parent: SequenceProvider

Complexity

Conditions	4
Paths	4

Size

Total Lines	26
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	4

Importance

Changes

Metric	Value
cc	4
dl	0
loc	26
ccs	13
cts	13
cp	1
crap	4
rs	9.7666
c	0
b	0
f	0
eloc	15
nc	4
nop	3

<?php

namespace Samsara\Fermat\Core\Provider;

use Samsara\Exceptions\SystemError\LogicalError\IncompatibleObjectState;
use Samsara\Exceptions\SystemError\PlatformError\MissingPackage;
use Samsara\Exceptions\UsageError\IntegrityConstraint;
use Samsara\Fermat\Core\Enums\CalcMode;
use Samsara\Fermat\Core\Enums\NumberBase;
use Samsara\Fermat\Core\Numbers;
use Samsara\Fermat\Core\Types\Base\Interfaces\Numbers\DecimalInterface;
use Samsara\Fermat\Core\Types\Base\Interfaces\Numbers\NumberInterface;
filter:
    dependency_paths: ["lib/*"]
use Samsara\Fermat\Core\Types\NumberCollection;
use Samsara\Fermat\Core\Values\ImmutableDecimal;

/**
 *
 */
class SequenceProvider
{

    const EULER_ZIGZAG = [
        '1',                                                        // 0
        '1',                                                        // 1
        '1',                                                        // 2
        '2',                                                        // 3
        '5',                                                        // 4
        '16',                                                       // 5
        '61',                                                       // 6
        '272',                                                      // 7
        '1385',                                                     // 8
        '7936',                                                     // 9
        '50521',                                                    // 10
        '353792',                                                   // 11
        '2702765',                                                  // 12
        '22368256',                                                 // 13
        '199360981',                                                // 14
        '1903757312',                                               // 15
        '19391512145',                                              // 16
        '209865342976',                                             // 17
        '2404879675441',                                            // 18
        '29088885112832',                                           // 19
        '370371188237525',                                          // 20
        '4951498053124096',                                         // 21
        '69348874393137901',                                        // 22
        '1015423886506852352',                                      // 23
        '15514534163557086905',                                     // 24
        '246921480190207983616',                                    // 25
        '4087072509293123892361',                                   // 26
        '70251601603943959887872',                                  // 27
        '1252259641403629865468285',                                // 28
        '23119184187809597841473536',                               // 29
        '441543893249023104553682821',                              // 30
        '8713962757125169296170811392',                             // 31
        '177519391579539289436664789665',                           // 32
        '3729407703720529571097509625856',                          // 33
        '80723299235887898062168247453281',                         // 34
        '1798651693450888780071750349094912',                       // 35
        '41222060339517702122347079671259045',                      // 36
        '970982810785059112379399707952152576',                     // 37
        '23489580527043108252017828576198947741',                   // 38
        '583203324917310043943191641625494290432',                  // 39
        '14851150718114980017877156781405826684425',                // 40
        '387635983772083031828014624002175135645696',               // 41
        '10364622733519612119397957304745185976310201',             // 42
        '283727921907431909304183316295787837183229952',            // 43
        '7947579422597592703608040510088070619519273805',           // 44
        '227681379129930886488600284336316164603920777216',         // 45
        '6667537516685544977435028474773748197524107684661',        // 46
        '199500252157859031027160499643195658166340757225472',      // 47
        '6096278645568542158691685742876843153976539044435185',     // 48
        '190169564657928428175235445073924928592047775873499136',   // 49
        '6053285248188621896314383785111649088103498225146815121',  // 50
    ];

    /**
     * OEIS: A005408
     *
     * @param int $n
     * @param bool $asCollection
     * @param int $collectionSize
     *
     * @return ImmutableDecimal|NumberCollection
     * @throws IntegrityConstraint
     * @throws MissingPackage
     */
    public static function nthOddNumber(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal|NumberCollection
    {
        if ($asCollection) {
            $sequence = new NumberCollection();

            for ($i = 0;$i < $collectionSize;$i++) {
                $sequence->push(self::nthOddNumber($n + $i));
            }

            return $sequence;
        }

        if ($n >= (PHP_INT_MAX/2)) {
            $n = new ImmutableDecimal($n, 100);

            return $n->multiply(2)->add(1);
        } else {
            return new ImmutableDecimal(($n*2)+1, 100);
        }

    }

    /**
     * OEIS: A005843
     *
     * @param int $n
     * @param int|null $scale
     * @param bool $asCollection
     * @param int $collectionSize
     *
     * @return ImmutableDecimal|NumberCollection
     * @throws IntegrityConstraint
     */
    public static function nthEvenNumber(int $n, int $scale = null, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal|NumberCollection
    {

        if ($asCollection) {
            $sequence = new NumberCollection();

            for ($i = 0;$i < $collectionSize;$i++) {
                $sequence->push(self::nthEvenNumber($n + $i));
            }

            return $sequence;
        }
        if ($n > (PHP_INT_MAX/2)) {
            $n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n, $scale);

            return $n->multiply(2);
        } else {
            return new ImmutableDecimal(($n*2), $scale);
        }

    }

    /**
     * OEIS: A033999
     *
     * @param int $n
     * @param bool $asCollection
     * @param int $collectionSize
     *
     * @return ImmutableDecimal|NumberCollection
     * @throws IntegrityConstraint
     */
    public static function nthPowerNegativeOne(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal|NumberCollection
    {

        if ($asCollection) {
            $sequence = new NumberCollection();

            for ($i = 0;$i < $collectionSize;$i++) {
                $sequence->push(self::nthPowerNegativeOne($n + $i));
            }

            return $sequence;
        }

        return ($n % 2 ? new ImmutableDecimal(-1) : new ImmutableDecimal(1));

    }

    /**
     * OEIS: A000111
     *
     * @param int $n
     * @param bool $asCollection
     * @param int $collectionSize
     *
     * @return ImmutableDecimal|NumberCollection
     * @throws IntegrityConstraint
     */
    public static function nthEulerZigzag(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal|NumberCollection
    {

        if ($asCollection) {
            $sequence = new NumberCollection();

            for ($i = 0;$i < $collectionSize;$i++) {
                $sequence->push(self::nthEulerZigzag($n + $i));
            }

            return $sequence;
        }

        if ($n > 50) {
            throw new IntegrityConstraint(
                '$n cannot be larger than 50',
                'Limit your use of the Euler Zigzag Sequence to the 50th index',
                'This library does not support the Euler Zigzag Sequence (OEIS: A000111) beyond E(50)'
            );
        }

        return Numbers::make(Numbers::IMMUTABLE, static::EULER_ZIGZAG[$n], 100);

    }

    /**
     * Returns the nth Bernoulli Number, where odd indexes return zero, and B1() is -1/2.
     *
     * This function gets very slow if you demand large precision.
     *
     * @param $n
     * @param int|null $scale
     * @return ImmutableDecimal
     * @throws IncompatibleObjectState
     * @throws IntegrityConstraint
     * @throws MissingPackage
     */
    public static function nthBernoulliNumber($n, ?int $scale = null): ImmutableDecimal
    {

        $scale = $scale ?? 5;

        $internalScale = (int)ceil($scale*(log10($scale)+1));

        $n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n, $internalScale)->setMode(CalcMode::Precision);

        if (!$n->isWhole()) {
            throw new IntegrityConstraint(
                'Only integers may be indexes for Bernoulli numbers',
                'Ensure only integers are provided as indexes',
                'An attempt was made to get a Bernoulli number with a non-integer index'
            );
        }

        if ($n->isLessThan(0)) {
            throw new IntegrityConstraint(
                'Index must be non-negative',
                'Provide only non-negative indexes for Bernoulli number generation',
                'An attempt was made to get a Bernoulli number with a negative index'
            );
        }

        if ($n->isEqual(0)) {
            return Numbers::makeOne($scale);
        }

        if ($n->isEqual(1)) {
            return Numbers::make(Numbers::IMMUTABLE, '-0.5', $scale);
        }

        if ($n->modulo(2)->isEqual(1)) {
            return Numbers::makeZero($scale);
        }

        $tau = Numbers::makeTau($internalScale)->setMode(CalcMode::Precision);

        $d = Numbers::make(Numbers::IMMUTABLE, 4, $internalScale)->setMode(CalcMode::Precision)->add(
            $n->factorial()->ln($internalScale)->subtract(
                $n->multiply($tau->log10($internalScale))
            )->truncate()
        )->add(
            $n->numberOfIntDigits()
        );
        $s = $d->multiply(
            Numbers::makeNaturalLog10($internalScale)
        )->multiply(
            '0.5'
        )->divide($n, $internalScale)->exp($internalScale)->truncate()->add(1);
        $internalScale = ($d->isGreaterThan($internalScale)) ? $d->asInt() : $internalScale;

        $s = $s->truncateToScale($internalScale);
        $n = $n->truncateToScale($internalScale);
        $tau = Numbers::make2Pi($internalScale)->setMode(CalcMode::Precision);
        $p = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);
        $t1 = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);
        $t2 = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);

        while ($p->isLessThanOrEqualTo($s)) {
            $p = self::_nextprime($p);
            $pn = $p->pow($n);
            $pn1 = $pn->subtract(1);
            $t1 = $pn->multiply($t1);
            $t2 = $pn1->multiply($t2);
        }

        $z = $t1->divide($t2, $internalScale);
        $oz = Numbers::makeZero($internalScale)->setMode(CalcMode::Precision);

        while (!$oz->isEqual($z)) {
            $oz = $z;
            $p = self::_nextprime($p);
            $pn = $p->pow($n);
            $pn1 = $z->divide($pn, $internalScale);
            $z = $z->add($pn1);
        }

        $f = $n->factorial();
        $taun = $tau->pow($n);

        $z = $z->multiply(2)->multiply($f)->divide($taun, $internalScale);

        if ($n->modulo(4)->isEqual(0)) {
            $z = $z->multiply(-1);
        }

        return $z->round($scale);

    }

    /**
     * @param int $n
     * @return NumberCollection
     * @throws IntegrityConstraint
     * @throws MissingPackage
     */
    public static function nthPrimeNumbers(int $n): NumberCollection
    {
        $collection = new NumberCollection();

        $collection->push(Numbers::make(Numbers::IMMUTABLE, 2));

        $currentPrime = Numbers::make(Numbers::IMMUTABLE, 3);

        for ($i = 1;$i < $n;$i++) {
            while (!$currentPrime->isPrime()) {
                $currentPrime = $currentPrime->add(2);
            }

            $collection->push($currentPrime);
            $currentPrime = $currentPrime->add(2);
        }

        return $collection;
    }

    /**
     * OEIS: A000045
     *
     * This uses an implementation of the fast-doubling Karatsuba multiplication algorithm as described by 'Nayuki':
     *
     * https://www.nayuki.io/page/fast-fibonacci-algorithms
     *
     * @param int $n
     * @param bool $asCollection
     * @param int $collectionSize
     *
     * @return ImmutableDecimal|NumberCollection
     * @throws IntegrityConstraint
     */
    public static function nthFibonacciNumber(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal|NumberCollection
    {
        $n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n);

        if ($n->isLessThan(0)) {
            throw new IntegrityConstraint(
                'Negative term numbers not valid for Fibonacci Sequence',
                'Provide a positive term number',
                'A negative term number for the Fibonacci sequence was requested; provide a positive term number'
            );
        }

        $fastFib = static::_fib($n);

        if ($asCollection) {
            $sequence = new NumberCollection();
            $sequence->push($fastFib[0]);
            $sequence->push($fastFib[1]);
            for ($i = 0;$i < ($collectionSize-2);$i++) {
                $sequence->push($sequence->get($i)->add($sequence[$i+1]));
            }

            return $sequence;
        }

        return $fastFib[0];
    }

    /**
     * OEIS: A000045
     *
     * This uses an implementation of the fast-doubling Karatsuba multiplication algorithm as described by 'Nayuki':
     *
     * https://www.nayuki.io/page/fast-fibonacci-algorithms
     *
     * @param int $n
     * @return ImmutableDecimal[]
     * @throws IntegrityConstraint
     */
    public static function nthFibonacciPair(int $n): array
    {
        $n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n);

        if ($n->isLessThan(0)) {
            throw new IntegrityConstraint(
                'Negative term numbers not valid for Fibonacci Sequence',
                'Provide a positive term number',
                'A negative term number for the Fibonacci sequence was requested; provide a positive term number'
            );
        }

        return static::_fib($n);
    }

    /**
     * OEIS: A000032
     *
     * @param int $n
     * @return ImmutableDecimal
     */
    public static function nthLucasNumber(int $n): ImmutableDecimal
    {

        if ($n == 0) {
            return Numbers::make(Numbers::IMMUTABLE, 2);
        } elseif ($n == 1) {
            return Numbers::make(Numbers::IMMUTABLE, 1);
        } elseif ($n < 0) {
            throw new IntegrityConstraint(
                'Negative term numbers not valid for Lucas Numbers',
                'Provide a positive term number',
                'A negative term number for the Lucas sequence was requested; provide a positive term number'
            );
        }

        [$F1, $fib] = static::_fib(Numbers::make(Numbers::IMMUTABLE, $n-1));
        [$fib, $F2] = static::_fib($fib);

        return $F1->add($F2);

    }

    /**
     * OEIS: A000217
     *
     * @param int $n
     * @return ImmutableDecimal
     * @throws IntegrityConstraint
     */
    public static function nthTriangularNumber(int $n): ImmutableDecimal
    {

        if ($n < 1) {
            throw new IntegrityConstraint(
                'Negative term numbers not valid for Triangular Numbers',
                'Provide a positive term number',
                'A negative term number for the Triangular Number sequence was requested; provide a positive term number'
            );
        }

        $n = new ImmutableDecimal($n);

        return $n->multiply($n->add(1))->divide(2);

    }

    /**
     * @param ImmutableDecimal $number
     * @return ImmutableDecimal[]
     * @throws IntegrityConstraint
     */
    private static function _fib(ImmutableDecimal $number): array
    {
        if ($number->isEqual(0)) {
            return [Numbers::makeZero(), Numbers::makeOne()];
        }

        /**
         * @var ImmutableDecimal $a
         * @var ImmutableDecimal $b
         * @var ImmutableDecimal $prevCall
         */
        $prevCall = $number->divide(2)->floor();
        [$a, $b] = static::_fib($prevCall);
        $c = $a->multiply($b->multiply(2)->subtract($a));
        $d = $a->multiply($a)->add($b->multiply($b));

        if ($number->modulo(2)->isEqual(0)) {
            return [$c, $d];
        }

        return [$d, $c->add($d)];
    }

    private static function _nextprime(ImmutableDecimal $number): ImmutableDecimal
    {
        return Numbers::make(Numbers::IMMUTABLE, gmp_strval(gmp_nextprime($number->getValue(NumberBase::Ten))));
    }

}

1		<?php
2
3		namespace Samsara\Fermat\Core\Provider;
4
5		use Samsara\Exceptions\SystemError\LogicalError\IncompatibleObjectState;
6		use Samsara\Exceptions\SystemError\PlatformError\MissingPackage;
7		use Samsara\Exceptions\UsageError\IntegrityConstraint;
8		use Samsara\Fermat\Core\Enums\CalcMode;
9		use Samsara\Fermat\Core\Enums\NumberBase;
10		use Samsara\Fermat\Core\Numbers;
11		use Samsara\Fermat\Core\Types\Base\Interfaces\Numbers\DecimalInterface;
12		use Samsara\Fermat\Core\Types\Base\Interfaces\Numbers\NumberInterface;
		0 ignored issues – show Bug introduced 2022-10-22 02:34 UTC by Report Bug Copy Issue Report The type `Samsara\Fermat\Core\Type...Numbers\NumberInterface` was not found. Maybe you did not declare it correctly or list all dependencies? The issue could also be caused by a filter entry in the build configuration. If the path has been excluded in your configuration, e.g. `excluded_paths: ["lib/"]`, you can move it to the dependency path list as follows: filter: dependency_paths: ["lib/"] For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths Loading history...
13		use Samsara\Fermat\Core\Types\NumberCollection;
14		use Samsara\Fermat\Core\Values\ImmutableDecimal;
15
16		/**
17		*
18		*/
19		class SequenceProvider
20		{
21
22		const EULER_ZIGZAG = [
23		'1', // 0
24		'1', // 1
25		'1', // 2
26		'2', // 3
27		'5', // 4
28		'16', // 5
29		'61', // 6
30		'272', // 7
31		'1385', // 8
32		'7936', // 9
33		'50521', // 10
34		'353792', // 11
35		'2702765', // 12
36		'22368256', // 13
37		'199360981', // 14
38		'1903757312', // 15
39		'19391512145', // 16
40		'209865342976', // 17
41		'2404879675441', // 18
42		'29088885112832', // 19
43		'370371188237525', // 20
44		'4951498053124096', // 21
45		'69348874393137901', // 22
46		'1015423886506852352', // 23
47		'15514534163557086905', // 24
48		'246921480190207983616', // 25
49		'4087072509293123892361', // 26
50		'70251601603943959887872', // 27
51		'1252259641403629865468285', // 28
52		'23119184187809597841473536', // 29
53		'441543893249023104553682821', // 30
54		'8713962757125169296170811392', // 31
55		'177519391579539289436664789665', // 32
56		'3729407703720529571097509625856', // 33
57		'80723299235887898062168247453281', // 34
58		'1798651693450888780071750349094912', // 35
59		'41222060339517702122347079671259045', // 36
60		'970982810785059112379399707952152576', // 37
61		'23489580527043108252017828576198947741', // 38
62		'583203324917310043943191641625494290432', // 39
63		'14851150718114980017877156781405826684425', // 40
64		'387635983772083031828014624002175135645696', // 41
65		'10364622733519612119397957304745185976310201', // 42
66		'283727921907431909304183316295787837183229952', // 43
67		'7947579422597592703608040510088070619519273805', // 44
68		'227681379129930886488600284336316164603920777216', // 45
69		'6667537516685544977435028474773748197524107684661', // 46
70		'199500252157859031027160499643195658166340757225472', // 47
71		'6096278645568542158691685742876843153976539044435185', // 48
72		'190169564657928428175235445073924928592047775873499136', // 49
73		'6053285248188621896314383785111649088103498225146815121', // 50
74		];
75
76		/**
77		* OEIS: A005408
78		*
79		* @param int $n
80		* @param bool $asCollection
81		* @param int $collectionSize
82		*
83		* @return ImmutableDecimal\|NumberCollection
84		* @throws IntegrityConstraint
85		* @throws MissingPackage
86		*/
87	878	public static function nthOddNumber(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal\|NumberCollection
88		{
89	878	if ($asCollection) {
90	2	$sequence = new NumberCollection();
91
92	2	for ($i = 0;$i < $collectionSize;$i++) {
93	2	$sequence->push(self::nthOddNumber($n + $i));
94		}
95
96	2	return $sequence;
97		}
98
99	878	if ($n >= (PHP_INT_MAX/2)) {
100		$n = new ImmutableDecimal($n, 100);
101
102		return $n->multiply(2)->add(1);
103		} else {
104	878	return new ImmutableDecimal(($n*2)+1, 100);
105		}
106
107		}
108
109		/**
110		* OEIS: A005843
111		*
112		* @param int $n
113		* @param int\|null $scale
114		* @param bool $asCollection
115		* @param int $collectionSize
116		*
117		* @return ImmutableDecimal\|NumberCollection
118		* @throws IntegrityConstraint
119		*/
120	188	public static function nthEvenNumber(int $n, int $scale = null, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal\|NumberCollection
121		{
122
123	188	if ($asCollection) {
124	2	$sequence = new NumberCollection();
125
126	2	for ($i = 0;$i < $collectionSize;$i++) {
127	2	$sequence->push(self::nthEvenNumber($n + $i));
128		}
129
130	2	return $sequence;
131		}
132	188	if ($n > (PHP_INT_MAX/2)) {
133		$n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n, $scale);
134
135		return $n->multiply(2);
136		} else {
137	188	return new ImmutableDecimal(($n*2), $scale);
138		}
139
140		}
141
142		/**
143		* OEIS: A033999
144		*
145		* @param int $n
146		* @param bool $asCollection
147		* @param int $collectionSize
148		*
149		* @return ImmutableDecimal\|NumberCollection
150		* @throws IntegrityConstraint
151		*/
152	6	public static function nthPowerNegativeOne(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal\|NumberCollection
153		{
154
155	6	if ($asCollection) {
156	4	$sequence = new NumberCollection();
157
158	4	for ($i = 0;$i < $collectionSize;$i++) {
159	4	$sequence->push(self::nthPowerNegativeOne($n + $i));
160		}
161
162	4	return $sequence;
163		}
164
165	6	return ($n % 2 ? new ImmutableDecimal(-1) : new ImmutableDecimal(1));
166
167		}
168
169		/**
170		* OEIS: A000111
171		*
172		* @param int $n
173		* @param bool $asCollection
174		* @param int $collectionSize
175		*
176		* @return ImmutableDecimal\|NumberCollection
177		* @throws IntegrityConstraint
178		*/
179	2	public static function nthEulerZigzag(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal\|NumberCollection
180		{
181
182	2	if ($asCollection) {
183	2	$sequence = new NumberCollection();
184
185	2	for ($i = 0;$i < $collectionSize;$i++) {
186	2	$sequence->push(self::nthEulerZigzag($n + $i));
187		}
188
189	2	return $sequence;
190		}
191
192	2	if ($n > 50) {
193	2	throw new IntegrityConstraint(
194		'$n cannot be larger than 50',
195		'Limit your use of the Euler Zigzag Sequence to the 50th index',
196		'This library does not support the Euler Zigzag Sequence (OEIS: A000111) beyond E(50)'
197		);
198		}
199
200	2	return Numbers::make(Numbers::IMMUTABLE, static::EULER_ZIGZAG[$n], 100);
201
202		}
203
204		/**
205		* Returns the nth Bernoulli Number, where odd indexes return zero, and B1() is -1/2.
206		*
207		* This function gets very slow if you demand large precision.
208		*
209		* @param $n
210		* @param int\|null $scale
211		* @return ImmutableDecimal
212		* @throws IncompatibleObjectState
213		* @throws IntegrityConstraint
214		* @throws MissingPackage
215		*/
216	2	public static function nthBernoulliNumber($n, ?int $scale = null): ImmutableDecimal
217		{
218
219	2	$scale = $scale ?? 5;
220
221	2	$internalScale = (int)ceil($scale*(log10($scale)+1));
222
223	2	$n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n, $internalScale)->setMode(CalcMode::Precision);
224
225	2	if (!$n->isWhole()) {
226		throw new IntegrityConstraint(
227		'Only integers may be indexes for Bernoulli numbers',
228		'Ensure only integers are provided as indexes',
229		'An attempt was made to get a Bernoulli number with a non-integer index'
230		);
231		}
232
233	2	if ($n->isLessThan(0)) {
234		throw new IntegrityConstraint(
235		'Index must be non-negative',
236		'Provide only non-negative indexes for Bernoulli number generation',
237		'An attempt was made to get a Bernoulli number with a negative index'
238		);
239		}
240
241	2	if ($n->isEqual(0)) {
242	2	return Numbers::makeOne($scale);
243		}
244
245	2	if ($n->isEqual(1)) {
246	2	return Numbers::make(Numbers::IMMUTABLE, '-0.5', $scale);
247		}
248
249	2	if ($n->modulo(2)->isEqual(1)) {
250	2	return Numbers::makeZero($scale);
251		}
252
253	2	$tau = Numbers::makeTau($internalScale)->setMode(CalcMode::Precision);
254
255	2	$d = Numbers::make(Numbers::IMMUTABLE, 4, $internalScale)->setMode(CalcMode::Precision)->add(
256	2	$n->factorial()->ln($internalScale)->subtract(
257	2	$n->multiply($tau->log10($internalScale))
258	2	)->truncate()
259	2	)->add(
260	2	$n->numberOfIntDigits()
261		);
262	2	$s = $d->multiply(
263	2	Numbers::makeNaturalLog10($internalScale)
264	2	)->multiply(
265		'0.5'
266	2	)->divide($n, $internalScale)->exp($internalScale)->truncate()->add(1);
267	2	$internalScale = ($d->isGreaterThan($internalScale)) ? $d->asInt() : $internalScale;
268
269	2	$s = $s->truncateToScale($internalScale);
270	2	$n = $n->truncateToScale($internalScale);
271	2	$tau = Numbers::make2Pi($internalScale)->setMode(CalcMode::Precision);
272	2	$p = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);
273	2	$t1 = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);
274	2	$t2 = Numbers::makeOne($internalScale)->setMode(CalcMode::Precision);
275
276	2	while ($p->isLessThanOrEqualTo($s)) {
277	2	$p = self::_nextprime($p);
278	2	$pn = $p->pow($n);
279	2	$pn1 = $pn->subtract(1);
280	2	$t1 = $pn->multiply($t1);
281	2	$t2 = $pn1->multiply($t2);
282		}
283
284	2	$z = $t1->divide($t2, $internalScale);
285	2	$oz = Numbers::makeZero($internalScale)->setMode(CalcMode::Precision);
286
287	2	while (!$oz->isEqual($z)) {
288	2	$oz = $z;
289	2	$p = self::_nextprime($p);
290	2	$pn = $p->pow($n);
291	2	$pn1 = $z->divide($pn, $internalScale);
292	2	$z = $z->add($pn1);
293		}
294
295	2	$f = $n->factorial();
296	2	$taun = $tau->pow($n);
297
298	2	$z = $z->multiply(2)->multiply($f)->divide($taun, $internalScale);
299
300	2	if ($n->modulo(4)->isEqual(0)) {
301	2	$z = $z->multiply(-1);
302		}
303
304	2	return $z->round($scale);
305
306		}
307
308		/**
309		* @param int $n
310		* @return NumberCollection
311		* @throws IntegrityConstraint
312		* @throws MissingPackage
313		*/
314		public static function nthPrimeNumbers(int $n): NumberCollection
315		{
316		$collection = new NumberCollection();
317
318		$collection->push(Numbers::make(Numbers::IMMUTABLE, 2));
319
320		$currentPrime = Numbers::make(Numbers::IMMUTABLE, 3);
321
322		for ($i = 1;$i < $n;$i++) {
323		while (!$currentPrime->isPrime()) {
324		$currentPrime = $currentPrime->add(2);
325		}
326
327		$collection->push($currentPrime);
328		$currentPrime = $currentPrime->add(2);
329		}
330
331		return $collection;
332		}
333
334		/**
335		* OEIS: A000045
336		*
337		* This uses an implementation of the fast-doubling Karatsuba multiplication algorithm as described by 'Nayuki':
338		*
339		* https://www.nayuki.io/page/fast-fibonacci-algorithms
340		*
341		* @param int $n
342		* @param bool $asCollection
343		* @param int $collectionSize
344		*
345		* @return ImmutableDecimal\|NumberCollection
346		* @throws IntegrityConstraint
347		*/
348	4	public static function nthFibonacciNumber(int $n, bool $asCollection = false, int $collectionSize = 10): ImmutableDecimal\|NumberCollection
349		{
350	4	$n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n);
351
352	4	if ($n->isLessThan(0)) {
353	2	throw new IntegrityConstraint(
354		'Negative term numbers not valid for Fibonacci Sequence',
355		'Provide a positive term number',
356		'A negative term number for the Fibonacci sequence was requested; provide a positive term number'
357		);
358		}
359
360	2	$fastFib = static::_fib($n);
361
362	2	if ($asCollection) {
363	2	$sequence = new NumberCollection();
364	2	$sequence->push($fastFib[0]);
365	2	$sequence->push($fastFib[1]);
366	2	for ($i = 0;$i < ($collectionSize-2);$i++) {
367	2	$sequence->push($sequence->get($i)->add($sequence[$i+1]));
368		}
369
370	2	return $sequence;
371		}
372
373	2	return $fastFib[0];
374		}
375
376		/**
377		* OEIS: A000045
378		*
379		* This uses an implementation of the fast-doubling Karatsuba multiplication algorithm as described by 'Nayuki':
380		*
381		* https://www.nayuki.io/page/fast-fibonacci-algorithms
382		*
383		* @param int $n
384		* @return ImmutableDecimal[]
385		* @throws IntegrityConstraint
386		*/
387	2	public static function nthFibonacciPair(int $n): array
388		{
389	2	$n = Numbers::makeOrDont(Numbers::IMMUTABLE, $n);
390
391	2	if ($n->isLessThan(0)) {
392		throw new IntegrityConstraint(
393		'Negative term numbers not valid for Fibonacci Sequence',
394		'Provide a positive term number',
395		'A negative term number for the Fibonacci sequence was requested; provide a positive term number'
396		);
397		}
398
399	2	return static::_fib($n);
400		}
401
402		/**
403		* OEIS: A000032
404		*
405		* @param int $n
406		* @return ImmutableDecimal
407		*/
408		public static function nthLucasNumber(int $n): ImmutableDecimal
409		{
410
411		if ($n == 0) {
412		return Numbers::make(Numbers::IMMUTABLE, 2);
413		} elseif ($n == 1) {
414		return Numbers::make(Numbers::IMMUTABLE, 1);
415		} elseif ($n < 0) {
416		throw new IntegrityConstraint(
417		'Negative term numbers not valid for Lucas Numbers',
418		'Provide a positive term number',
419		'A negative term number for the Lucas sequence was requested; provide a positive term number'
420		);
421		}
422
423		[$F1, $fib] = static::_fib(Numbers::make(Numbers::IMMUTABLE, $n-1));
424		[$fib, $F2] = static::_fib($fib);
425
426		return $F1->add($F2);
427
428		}
429
430		/**
431		* OEIS: A000217
432		*
433		* @param int $n
434		* @return ImmutableDecimal
435		* @throws IntegrityConstraint
436		*/
437		public static function nthTriangularNumber(int $n): ImmutableDecimal
438		{
439
440		if ($n < 1) {
441		throw new IntegrityConstraint(
442		'Negative term numbers not valid for Triangular Numbers',
443		'Provide a positive term number',
444		'A negative term number for the Triangular Number sequence was requested; provide a positive term number'
445		);
446		}
447
448		$n = new ImmutableDecimal($n);
449
450		return $n->multiply($n->add(1))->divide(2);
451
452		}
453
454		/**
455		* @param ImmutableDecimal $number
456		* @return ImmutableDecimal[]
457		* @throws IntegrityConstraint
458		*/
459	4	private static function _fib(ImmutableDecimal $number): array
460		{
461	4	if ($number->isEqual(0)) {
462	4	return [Numbers::makeZero(), Numbers::makeOne()];
463		}
464
465		/**
466		* @var ImmutableDecimal $a
467		* @var ImmutableDecimal $b
468		* @var ImmutableDecimal $prevCall
469		*/
470	4	$prevCall = $number->divide(2)->floor();
471	4	[$a, $b] = static::_fib($prevCall);
472	4	$c = $a->multiply($b->multiply(2)->subtract($a));
473	4	$d = $a->multiply($a)->add($b->multiply($b));
474
475	4	if ($number->modulo(2)->isEqual(0)) {
476	4	return [$c, $d];
477		}
478
479	4	return [$d, $c->add($d)];
480		}
481
482	2	private static function _nextprime(ImmutableDecimal $number): ImmutableDecimal
483		{
484	2	return Numbers::make(Numbers::IMMUTABLE, gmp_strval(gmp_nextprime($number->getValue(NumberBase::Ten))));
485		}
486
487		}

JordanRL / Fermat

SequenceProvider::nthFibonacciNumber() A last analyzed 2022-10-22 04:55 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

SequenceProvider::nthFibonacciNumber() A
last analyzed 2022-10-22 04:55 UTC