Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
38 / 38
100.00% covered (success)
100.00%
5 / 5
 CRAP
100.00% covered (success)
100.00%
1 / 1
Integer
100.00% covered (success)
100.00%
38 / 38
100.00% covered (success)
100.00%
5 / 5
 19
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 isInteger
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 trialFactorization
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
 6
 pollardsRho
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 4
 greatestCommonDivisor
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 3
 fermatFactor
100.00% covered (success)
100.00%
10 / 10
100.00% covered (success)
100.00%
1 / 1
 4
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Math\Number
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Math\Number;
16
17/**
18 * Integer class
19 *
20 * @package phpOMS\Math\Number
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class Integer
26{
27    /**
28     * Constructor.
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * Is integer.
39     *
40     * @param mixed $value Value to test
41     *
42     * @return bool
43     *
44     * @since 1.0.0
45     */
46    public static function isInteger(mixed $value) : bool
47    {
48        return \is_int($value);
49    }
50
51    /**
52     * Trial factorization.
53     *
54     * @param int $value Integer to factorize
55     *
56     * @return array<int|float>
57     *
58     * @since 1.0.0
59     */
60    public static function trialFactorization(int $value) : array
61    {
62        if ($value < 2) {
63            return [];
64        }
65
66        $factors = [];
67        $primes  = Prime::sieveOfEratosthenes((int) $value ** 0.5);
68
69        foreach ($primes as $prime) {
70            if ($prime * $prime > $value) {
71                break;
72            }
73
74            while ($value % $prime === 0) {
75                $factors[] = $prime;
76                $value    /= $prime;
77            }
78        }
79
80        if ($value > 1) {
81            $factors[] = $value;
82        }
83
84        return $factors;
85    }
86
87    /**
88     * Pollard's Rho.
89     *
90     * Integer factorization algorithm
91     *
92     * @param int $n         Integer to factorize
93     * @param int $x         Used for g(x) = (x^2 + 1) mod n
94     * @param int $factor    Period for repetition
95     * @param int $cycleSize Cycle size
96     * @param int $y         Fixed value for g(x) = g(y) mod p
97     *
98     * @return int
99     *
100     * @since 1.0.0
101     */
102    public static function pollardsRho(int $n, int $x = 2, int $factor = 1, int $cycleSize = 2, int $y = 2) : int
103    {
104        while ($factor === 1) {
105            for ($i = 1; $i < $cycleSize && $factor <= 1; ++$i) {
106                $x      = ($x * $x + 1) % $n;
107                $factor = self::greatestCommonDivisor($x - $y, $n);
108            }
109
110            $cycleSize *= 2;
111            $y          = $x;
112        }
113
114        return $factor;
115    }
116
117    /**
118     * Greatest common diviser.
119     *
120     * @param int $n Number one
121     * @param int $m Number two
122     *
123     * @return int
124     *
125     * @since 1.0.0
126     */
127    public static function greatestCommonDivisor(int $n, int $m) : int
128    {
129        $n = \abs($n);
130        $m = \abs($m);
131
132        while ($n !== $m) {
133            if ($n > $m) {
134                $n -= $m;
135            } else {
136                $m -= $n;
137            }
138        }
139
140        return $m;
141    }
142
143    /**
144     * Fermat factorization of odd integers.
145     *
146     * @param int $value Integer to factorize
147     * @param int $limit Max amount of iterations
148     *
149     * @return int[]
150     *
151     * @throws \InvalidArgumentException This exception is thrown if the value is not odd
152     *
153     * @since 1.0.0
154     */
155    public static function fermatFactor(int $value, int $limit = 1000000) : array
156    {
157        if (($value % 2) === 0) {
158            throw new \InvalidArgumentException('Only odd integers are allowed');
159        }
160
161        $a  = (int) \ceil(\sqrt($value));
162        $b2 = ($a * $a - $value);
163        $i  = 1;
164
165        while (!Numbers::isSquare($b2) && $i < $limit) {
166            ++$i;
167            ++$a;
168            $b2 = ($a * $a - $value);
169        }
170
171        return [(int) \round($a - \sqrt($b2)), (int) \round($a + \sqrt($b2))];
172    }
173}