Sidef/Types/Number/Gauss.pm untested

filter: Statementstmt 0.0% 0 / 327 Branchbran 0.0% 0 / 60 Conditioncond 0.0% 0 / 55 MC/DCmcdc 0.0% 0 / 29 Subroutinesub 0.0% 0 / 61 Podpod 0.0% 0 / 56 totaltotal 0.0% 0 / 588 CC 30 SCAR 23.5
CC
30
Cov
0%
stringify
56.0
new
20.0
factor
20.0
CRAP 10.5
1 package Sidef::Types::Number::Gauss;
2  
3 # Reference:
4 # https://en.wikipedia.org/wiki/Gaussian_integer
5  
6 use utf8;
7 use 5.016;
8  
9 use parent qw(
10 Sidef::Types::Number::Number
11 );
12  
13 use overload
14 q{bool} => sub { (@_) = ($_[0]); goto &__boolify__ },
15 q{""} => sub { (@_) = ($_[0]); goto &__stringify__ },
16 q{0+} => \&to_c,
17 q{${}} => \&to_c;
18  
19 sub new {
20 my (undef, $real, $imag) = @_;
21  
22 # Handle evaluation of polynomials
23 if (ref($_[0]) eq __PACKAGE__) {
24 return $_[0]->eval($real);
25 }
26  
27 $real //= Sidef::Types::Number::Number::ZERO;
28 $imag //= Sidef::Types::Number::Number::ZERO;
29  
30 $real = Sidef::Types::Number::Number->new($real) if !UNIVERSAL::isa($real, 'Sidef::Types::Number::Number');
31 $imag = Sidef::Types::Number::Number->new($imag) if !UNIVERSAL::isa($imag, 'Sidef::Types::Number::Number');
32  
33 bless {a => $real, b => $imag};
34 }
35  
36 *call = \&new;
37  
38 sub with_value {
39 my ($self, $value_1, $value_2) = @_;
40 __PACKAGE__->new($value_1, $value_2);
41 }
42  
43 sub eval {
44 my ($x, $v) = @_;
45 __PACKAGE__->new($x->{a}->eval($v), $x->{b}->eval($v));
46 }
47  
48 sub lift {
49 my ($x) = @_;
50 __PACKAGE__->new($x->{a}->lift, $x->{b}->lift);
51 }
52  
53 sub i {
54 my ($x) = @_;
55  
56 if (ref($x) eq __PACKAGE__) { # (a+bi)*i = -b + a*i
57 return __PACKAGE__->new($x->{b}->neg, $x->{a});
58 }
59  
60 __PACKAGE__->new(Sidef::Types::Number::Number::ZERO, Sidef::Types::Number::Number::ONE);
61 }
62  
63 sub to_c {
64 Sidef::Types::Number::Complex->new($_[0]->{a}, $_[0]->{b});
65 }
66  
67 *to_n = \&to_c;
68  
69 sub re {
70 $_[0]->{a};
71 }
72  
73 *a = \&re;
74 *real = \&re;
75  
76 sub im {
77 $_[0]->{b};
78 }
79  
80 *b = \&im;
81 *imag = \&im;
82  
83 sub reals {
84 ($_[0]->{a}, $_[0]->{b});
85 }
86  
87 sub parts {
88 Sidef::Types::Array::Array->new($_[0]->reals);
89 }
90  
91 sub __boolify__ {
92 $_[0]->{a};
93 }
94  
95 sub __numify__ {
96 $_[0]->{a};
97 }
98  
99 sub __stringify__ {
100 my ($x) = @_;
101 'Gauss(' . join(', ', $x->{a}->dump, $x->{b}->dump) . ')';
102 }
103  
104 sub to_s {
105 my ($x) = @_;
106 Sidef::Types::String::String->new($x->__stringify__);
107 }
108  
109 sub dump {
110 my ($x) = @_;
111 Sidef::Types::String::String->new($x->__stringify__);
112 }
113  
114 sub stringify {
115 my ($x) = @_;
116  
117 if ($x->{b}->is_zero) {
118 return $x->{a}->stringify;
119 }
120  
121 if ($x->{a}->is_zero) {
122  
123 if ($x->{b}->is_one) {
124 return Sidef::Types::String::String->new('1i');
125 }
126 elsif ($x->{b}->is_mone) {
127 return Sidef::Types::String::String->new('-1i');
128 }
129  
130 return Sidef::Types::String::String->new(join('', '(', $x->{b}->stringify, ')*1i'));
131 }
132  
133 if ($x->{b}->is_one) {
134 return Sidef::Types::String::String->new(join(' + ', $x->{a}->stringify, '1i'));
135 }
136  
137 if ($x->{b}->is_mone) {
138 return Sidef::Types::String::String->new(join(' - ', $x->{a}->stringify, '1i'));
139 }
140  
141 Sidef::Types::String::String->new(join(' + ', $x->{a}->stringify, join('', '(', $x->{b}->stringify, ')*1i')));
142 }
143  
144 *pretty = \&stringify;
145  
146 sub abs {
147 my ($x) = @_;
148 $x->{a}->sqr->add($x->{b}->sqr)->sqrt;
149 }
150  
151 sub iabs {
152 my ($x) = @_;
153 $x->{a}->sqr->add($x->{b}->sqr)->isqrt;
154 }
155  
156 sub norm {
157 my ($x) = @_;
158 $x->{a}->sqr->add($x->{b}->sqr);
159 }
160  
161 sub sgn {
162 my ($x) = @_;
163 $x->div($x->abs);
164 }
165  
166 sub neg {
167 my ($x) = @_;
168 __PACKAGE__->new($x->{a}->neg, $x->{b}->neg);
169 }
170  
171 sub conj {
172 my ($x) = @_;
173 __PACKAGE__->new($x->{a}, $x->{b}->neg);
174 }
175  
176 sub add {
177 my ($x, $y) = @_;
178  
179 if (ref($y) eq __PACKAGE__) {
180 return __PACKAGE__->new($x->{a}->add($y->{a}), $x->{b}->add($y->{b}));
181 }
182  
183 __PACKAGE__->new($x->{a}->add($y), $x->{b});
184 }
185  
186 sub sub {
187 my ($x, $y) = @_;
188  
189 if (ref($y) eq __PACKAGE__) {
190 return __PACKAGE__->new($x->{a}->sub($y->{a}), $x->{b}->sub($y->{b}));
191 }
192  
193 __PACKAGE__->new($x->{a}->sub($y), $x->{b});
194 }
195  
196 sub mul {
197 my ($x, $y) = @_;
198  
199 if (ref($y) eq __PACKAGE__) {
200 return __PACKAGE__->new($x->{a}->mul($y->{a})->sub($x->{b}->mul($y->{b})), $x->{a}->mul($y->{b})->add($x->{b}->mul($y->{a})));
201 }
202  
203 __PACKAGE__->new($x->{a}->mul($y), $x->{b}->mul($y));
204 }
205  
206 sub sqr {
207 my ($x) = @_;
208 my $t = $x->{a}->mul($x->{b});
209 __PACKAGE__->new($x->{a}->sqr->sub($x->{b}->sqr), $t->add($t));
210 }
211  
212 sub inv {
213 my ($x) = @_;
214 my $t = $x->{a}->sqr->add($x->{b}->sqr);
215 __PACKAGE__->new($x->{a}->div($t), $x->{b}->neg->div($t));
216 }
217  
218 sub invmod {
219 my ($x, $m) = @_;
220 $x->mod($m);
221 my $t = $x->{a}->sqr->add($x->{b}->sqr)->invmod($m);
222 __PACKAGE__->new($x->{a}->mul($t)->mod($m), $x->{b}->neg->mul($t)->mod($m));
223 }
224  
225 sub div {
226 my ($x, $y) = @_;
227 $x->mul($y->inv);
228 }
229  
230 sub float {
231 my ($x) = @_;
232 __PACKAGE__->new($x->{a}->float, $x->{b}->float);
233 }
234  
235 sub floor {
236 my ($x) = @_;
237 __PACKAGE__->new($x->{a}->floor, $x->{b}->floor);
238 }
239  
240 sub ceil {
241 my ($x) = @_;
242 __PACKAGE__->new($x->{a}->ceil, $x->{b}->ceil);
243 }
244  
245 sub round {
246 my ($x, $r) = @_;
247 __PACKAGE__->new($x->{a}->round($r), $x->{b}->round($r));
248 }
249  
250 sub mod {
251 my ($x, $y) = @_;
252  
253 if (ref($y) eq 'Sidef::Types::Number::Number') {
254 return __PACKAGE__->new($x->{a}->mod($y), $x->{b}->mod($y));
255 }
256  
257 # mod(a, b) = a - b * floor(a/b)
258 $x->sub($y->mul($x->div($y)->floor));
259 }
260  
261 sub is_divisible {
262 my ($x, $y) = @_;
263 $x->mod($y)->is_zero;
264 }
265  
266 *is_div = \&is_divisible;
267  
268 sub is_prime {
269 my ($x) = @_;
270 Sidef::Types::Number::Number::is_gaussian_prime($x->{a}, $x->{b});
271 }
272  
273 sub is_zero {
274 my ($x) = @_;
275 my $bool = $x->{a}->is_zero;
276 $bool || return $bool;
277 $x->{b}->is_zero;
278 }
279  
280 sub is_one {
281 my ($x) = @_;
282 my $bool = $x->{b}->is_zero;
283 $bool || return $bool;
284 $x->{a}->is_one;
285 }
286  
287 sub is_mone {
288 my ($x) = @_;
289 my $bool = $x->{b}->is_zero;
290 $bool || return $bool;
291 $x->{a}->is_mone;
292 }
293  
294 sub is_real {
295 my ($x) = @_;
296 $x->{b}->is_zero;
297 }
298  
299 sub is_imag {
300 my ($x) = @_;
301 my $bool = $x->{b}->is_zero;
302 $bool && return $bool->not;
303 $x->{a}->is_zero;
304 }
305  
306 sub gcd {
307 my ($n, $k) = @_;
308  
309 my $norm_n = $n->norm;
310 my $norm_k = $k->norm;
311  
312 if ($norm_n->gt($norm_k)) {
313 ($n, $k) = ($k, $n);
314 }
315  
316 until ($k->is_zero) {
317  
318 last if ($n->is_nan or $k->is_nan);
319  
320 my $q = $n->div($k)->round;
321 my $r = $n->sub($q->mul($k));
322  
323 ($n, $k) = ($k, $r);
324 }
325  
326 $n;
327 }
328  
329 sub gcd_norm {
330 my ($n, $k) = @_;
331 $n->norm->gcd($k->norm);
332 }
333  
334 sub is_coprime {
335 my ($n, $k) = @_;
336 $n->norm->gcd($k->norm)->is_one;
337 }
338  
339 sub factor {
340 my ($z) = @_;
341  
342 # Reference:
343 # https://www.alpertron.com.ar/GAUSSIAN.HTM
344  
345 my @factors;
346 my $n = $z->norm;
347  
348 state $one_one = __PACKAGE__->new(Sidef::Types::Number::Number::ONE, Sidef::Types::Number::Number::ONE);
349  
350 foreach my $pe (Sidef::Types::Number::Number::_factor_exp($$n)) {
351 my ($p, $e) = @$pe;
352  
353 if ($p eq '2') {
354 while ($z->is_div($one_one)) { # divisible by 1+1i
355 push @factors, $one_one;
356 $z = $z->div($one_one);
357 }
358 }
359 elsif (Math::Prime::Util::GMP::modint($p, 4) == 3) {
360 my $t = __PACKAGE__->new(Sidef::Types::Number::Number::_set_int($p));
361 while ($z->is_div($t)) {
362 push @factors, $t;
363 $z = $z->div($t);
364 }
365 }
366 else { # here we have: p % 4 == 1
367 my $p_obj = Sidef::Types::Number::Number::_set_int($p);
368 foreach my $solution (@{$p_obj->sum_of_squares}) {
369 my ($x, $y) = @$solution;
370  
371 my $t1 = __PACKAGE__->new($x, $y);
372 my $t2 = __PACKAGE__->new($y, $x);
373  
374 while ($z->is_div($t1)) {
375 push @factors, $t1;
376 $z = $z->div($t1);
377 }
378  
379 while ($z->is_div($t2)) {
380 push @factors, $t2;
381 $z = $z->div($t2);
382 }
383 }
384 }
385 }
386  
387 if (!($z->is_one)) {
388 push @factors, $z;
389 }
390  
391 Sidef::Types::Array::Array->new(\@factors)->sort;
392 }
393  
394 *factors = \&factor;
395  
396 sub factor_exp {
397 my ($z) = @_;
398 $z->factor->run_length;
399 }
400  
401 sub divisors {
402 my ($n) = @_;
403  
404 state $one = __PACKAGE__->new(Sidef::Types::Number::Number::ONE);
405 state $mone = __PACKAGE__->new(Sidef::Types::Number::Number::MONE);
406 state $one_i = __PACKAGE__->new(Sidef::Types::Number::Number::ZERO, Sidef::Types::Number::Number::ONE);
407 state $mone_i = __PACKAGE__->new(Sidef::Types::Number::Number::ZERO, Sidef::Types::Number::Number::MONE);
408  
409 my @D = ($one, $mone, $one_i, $mone_i);
410 my @F = @{$n->factor_exp};
411  
412 if ( @F
413 and ($F[0][0]->real->is_zero || $F[0][0]->imag->is_zero)
414 and ($F[0][0]->eq($one) || $F[0][0]->eq($mone) || $F[0][0]->eq($one_i) || $F[0][0]->eq($mone_i))) {
415 shift @F; # remove the unit factor
416 }
417  
418 foreach my $pe (@F) {
419 my ($p, $e) = @$pe;
420  
421 my $r = $one;
422 my @t;
423  
424 for (1 .. CORE::int($e)) {
425 $r = $r->mul($p);
426 foreach my $u (@D) {
427 push @t, $u->mul($r);
428 }
429 }
430 push @D, @t;
431 }
432  
433 return Sidef::Types::Array::Array->new(\@D);
434 }
435  
436 sub inc {
437 my ($x) = @_;
438 __PACKAGE__->new($x->{a}->inc, $x->{b});
439 }
440  
441 sub dec {
442 my ($x) = @_;
443 __PACKAGE__->new($x->{a}->dec, $x->{b});
444 }
445  
446 sub pow {
447 my ($x, $n) = @_;
448  
449 $n->is_int || return $x->to_n->pow($n);
450  
451 my $negative_power = 0;
452  
453 if ($n->is_neg) {
454 $n = $n->abs;
455 $negative_power = 1;
456 }
457  
458 my $c = __PACKAGE__->new(Sidef::Types::Number::Number::ONE);
459  
460 foreach my $bit (reverse split(//, $n->as_bin)) {
461  
462 # c *= x if bit
463 # x *= x
464  
465 $c = $c->mul($x) if $bit;
466 $x = $x->sqr;
467 }
468  
469 if ($negative_power) {
470 $c = $c->inv;
471 }
472  
473 return $c;
474 }
475  
476 sub powmod {
477 my ($x, $n, $m) = @_;
478  
479 $x = $x->mod($m);
480  
481 my $negative_power = 0;
482  
483 if ($n->is_neg) {
484 $n = $n->abs;
485 $negative_power = 1;
486 }
487  
488 my $c = __PACKAGE__->new(Sidef::Types::Number::Number::ONE);
489  
490 foreach my $bit (reverse split(//, $n->as_bin)) {
491  
492 # c = (c*x)%m if bit
493 # x = (x*x)%m
494  
495 $c = $c->mul($x)->mod($m) if $bit;
496 $x = $x->sqr->mod($m);
497 }
498  
499 if ($negative_power) {
500 $c = $c->invmod($m);
501 }
502  
503 return $c;
504 }
505  
506 sub cmp {
507 my ($x, $y) = @_;
508  
509 if (ref($y) eq __PACKAGE__) {
510 my $cmp = $x->{a}->cmp($y->{a}) // return undef;
511 $cmp && return $cmp;
512 return $x->{b}->cmp($y->{b});
513 }
514  
515 my $cmp = $x->{a}->cmp($y) // return undef;
516 $cmp && return $cmp;
517 $x->{b}->cmp(Sidef::Types::Number::Number::ZERO);
518 }
519  
520 sub eq {
521 my ($x, $y) = @_;
522  
523 if (ref($y) eq __PACKAGE__) {
524 my $bool = $x->{a}->eq($y->{a});
525 $bool || return $bool;
526 return $x->{b}->eq($y->{b});
527 }
528  
529 my $bool = $x->{a}->eq($y);
530 $bool || return $bool;
531 $x->{b}->is_zero;
532 }
533  
534 sub ne {
535 my ($x, $y) = @_;
536  
537 if (ref($y) eq __PACKAGE__) {
538 my $bool = $x->{a}->ne($y->{a});
539 $bool && return $bool;
540 return $x->{b}->ne($y->{b});
541 }
542  
543 my $bool = $x->{a}->ne($y);
544 $bool && return $bool;
545 $x->{b}->is_zero->not;
546 }
547  
548 sub shift_left { # x * 2^n
549 my ($x, $n) = @_;
550 $x->mul(Sidef::Types::Number::Number::TWO->pow($n));
551 }
552  
553 *lsft = \&shift_left;
554  
555 sub shift_right { # x / 2^n
556 my ($x, $n) = @_;
557 $x->div(Sidef::Types::Number::Number::TWO->pow($n));
558 }
559  
560 *rsft = \&shift_right;
561  
562 {
563 no strict 'refs';
564  
565 foreach my $method (qw(ge gt lt le)) {
566 *{__PACKAGE__ . '::' . $method} = sub {
567 my ($x, $y) = @_;
568 ($x->cmp($y) // return undef)->$method(Sidef::Types::Number::Number::ZERO);
569 };
570 }
571  
572 foreach my $method (qw(and xor or)) {
573 *{__PACKAGE__ . '::' . $method} = sub {
574 my ($x, $y) = @_;
575  
576 if (ref($y) eq __PACKAGE__) {
577 return __PACKAGE__->new($x->{a}->$method($y->{a}), $x->{b}->$method($y->{b}));
578 }
579  
580 return __PACKAGE__->new($x->{a}->$method($y), $x->{b});
581 };
582 }
583  
584 *{__PACKAGE__ . '::' . '/'} = \÷
585 *{__PACKAGE__ . '::' . '÷'} = \÷
586 *{__PACKAGE__ . '::' . '*'} = \&mul;
587 *{__PACKAGE__ . '::' . '%'} = \&mod;
588 *{__PACKAGE__ . '::' . '+'} = \&add;
589 *{__PACKAGE__ . '::' . '-'} = \⊂
590 *{__PACKAGE__ . '::' . '**'} = \&pow;
591 *{__PACKAGE__ . '::' . '++'} = \&inc;
592 *{__PACKAGE__ . '::' . '--'} = \&dec;
593 *{__PACKAGE__ . '::' . '<'} = \&lt;
594 *{__PACKAGE__ . '::' . '>'} = \&gt;
595 *{__PACKAGE__ . '::' . '&'} = \&and;
596 *{__PACKAGE__ . '::' . '|'} = \&or;
597 *{__PACKAGE__ . '::' . '^'} = \&xor;
598 *{__PACKAGE__ . '::' . '<<'} = \&lsft;
599 *{__PACKAGE__ . '::' . '>>'} = \&rsft;
600 *{__PACKAGE__ . '::' . '<=>'} = \&cmp;
601 *{__PACKAGE__ . '::' . '<='} = \&le;
602 *{__PACKAGE__ . '::' . '≤'} = \&le;
603 *{__PACKAGE__ . '::' . '>='} = \&ge;
604 *{__PACKAGE__ . '::' . '≥'} = \&ge;
605 *{__PACKAGE__ . '::' . '=='} = \&eq;
606 *{__PACKAGE__ . '::' . '!='} = \&ne;
607 }
608  
609 1