X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb-perl/blobdiff_plain/f9952aec1cf6c64a5681308eea817b6113a37433..fcd15e0b7a3d0f0ca2f30953573f8d1f6b8e8bd2:/t/mp.t

diff --git a/t/mp.t b/t/mp.t
new file mode 100644
index 0000000..39bbaf2
--- /dev/null
+++ b/t/mp.t
@@ -0,0 +1,208 @@
+# -*-mode: perl; comment-column: 68-*-
+use Test;
+BEGIN { plan tests => 121; }
+use Catacomb qw(:const mp);
+
+# Addition
+ok mp("5") + mp("4") == mp("9");				    #t    1
+ok mp("5") + mp("-4") == mp("1");				    #t    2
+ok mp("-5") + mp("4") == mp("-1");				    #t    3
+ok mp("-5") + mp("-4") == mp("-9");				    #t    4
+ok mp("0xffffffff") + mp("1") == mp("0x100000000");		    #t    5
+
+# Subtraction
+ok mp("5") - mp("4") == mp("1");				    #t    6
+ok mp("5") - mp("-4") == mp("9");				    #t    7
+ok mp("-5") - mp("4") == mp("-9");				    #t    8
+ok mp("-5") - mp("-4") == mp("-1");				    #t    9
+ok mp("4") - mp("5") == mp("-1");				    #t   10
+ok mp("4") - mp("-5") == mp("9");				    #t   11
+ok mp("-4") - mp("5") == mp("-9");				    #t   12
+ok mp("-4") - mp("-5") == mp("1");				    #t   13
+
+# Squaring
+ok mp("5")->sqr() == mp("25");					    #t   14
+ok mp("-5")->sqr() == mp("25");					    #t   15
+ok mp("56309812098453")->sqr()==mp("3170794938563083851364993209"); #t   16
+
+# Multiplication
+ok mp("5") * mp("4") == mp("20");				    #t   17
+ok mp("5") * mp("-4") == mp("-20");				    #t   18
+ok mp("-5") * mp("4") == mp("-20");				    #t   19
+ok mp("-5") * mp("-4") == mp("20");				    #t   20
+ok mp("0x10000") * mp("0x10000") == mp("0x100000000");		    #t   21
+
+# Division
+sub divtest {
+  my ($x, $y, $q, $r) = @_;
+  my ($qq, $rr) = Catacomb::MP::div($x, $y);
+  ok $qq == $q && $rr == $r;
+} 
+divtest "9", "4", "2", "1";					    #t   22
+divtest "-9", "4", "-3", "3";					    #t   23
+divtest "9", "-4", "-3", "-3";					    #t   24
+divtest "-9", "-4", "2", "-1";					    #t   25
+divtest								    #t   26
+  "-3", "6277101735386680763835789423207666416083908700390324961279",
+  "-1", "6277101735386680763835789423207666416083908700390324961276";
+divtest								    #t   27
+  "3131675836296406071791252329528905062261497366991742517193",
+  "1110875761630725856340142297645383444629395595869672555585",
+  "2", "909924313034954359110967734238138173002706175252397406023";
+divtest								    #t   28
+  "3131675836296406071791252329528905062261497366991742517193", "53",
+  "59088223326347284373419855274130284193613157867768726739", "26";
+ok mp("-9") / mp("-4") == mp("2");				    #t   29
+ok mp("-9") % mp("-4") == mp("-1");				    #t   30
+
+# Exponentiation
+ok mp("4") ** mp("0") == mp("1");				    #t   31
+ok mp("4") ** mp("1") == mp("4");				    #t   32
+ok mp("7") ** mp("2") == mp("49");				    #t   33
+ok mp("3") ** mp("64") == mp("3433683820292512484657849089281");    #t   34
+
+# Bit ops tests
+ok ~mp("6") == mp("-7");					    #t   35
+ok ~mp("-7") == mp("6");					    #t   36
+
+ok +(mp("5") & mp("3")) == mp("1");				    #t   37
+ok +(mp("5") | mp("3")) == mp("7");				    #t   38
+ok +(mp("5") ^ mp("3")) == mp("6");				    #t   39
+ok +(mp("45") | mp("-7")) == mp("-3");				    #t   40
+ok +(mp("0x343cd5") ^ mp("-0x6a49c")) == mp("-0x32984f");	    #t   41
+
+ok +(mp("-1") >> 5) == mp("-1");				    #t   42
+ok +(mp("1") >> 5) == mp("0");					    #t   43
+ok +(mp("-6") >> 2) == mp("-2");				    #t   44
+ok +(mp("5") >> 0) == mp("5");					    #t   45
+ok +(mp("-4") >> 0) == mp("-4");				    #t   46
+ok +(mp("7") >> 2) == mp("1");					    #t   47
+ok +(mp("-7") >> 2) == mp("-2");				    #t   48
+ok +(mp("-7") >> 20) == mp("-1");				    #t   49
+
+ok +(mp("-1") << 5) == mp("-32");				    #t   50
+ok +(mp("5") << 0) == mp("5");					    #t   51
+ok +(mp("-4") << 0) == mp("-4");				    #t   52
+ok +(mp("7") << 2) == mp("28");					    #t   53
+ok +(mp("-7") << 2) == mp("-28");				    #t   54
+ok +(mp("0xc0000000") << 1) == mp("0x180000000");		    #t   55
+ok +(mp("-0xc0000000") << 1) == mp("-0x180000000");		    #t   56
+ok +(mp("-1") << 32) == mp("-0x100000000");			    #t   57
+
+ok mp("0")->setbit2c(40) == mp("0x10000000000");		    #t   58
+ok mp("0x87348")->setbit2c(40) == mp("0x10000087348");		    #t   59
+ok mp("5")->setbit2c(1) == mp("7");				    #t   60
+ok mp("7")->setbit2c(1) == mp("7");				    #t   61
+ok mp("-3")->setbit2c(1) == mp("-1");				    #t   62
+
+ok mp("0x10000000000")->clearbit2c(40) == mp("0");		    #t   63
+ok mp("0x87348")->clearbit2c(40) == mp("0x87348");		    #t   64
+ok mp("5")->clearbit2c(1) == mp("5");				    #t   65
+ok mp("7")->clearbit2c(1) == mp("5");				    #t   66
+ok mp("-1")->clearbit2c(1) == mp("-3");				    #t   67
+
+# Negation
+ok -mp("0") == mp("0");						    #t   68
+ok -mp("15") == mp("-15");					    #t   69
+ok -mp("-15") == mp("15");					    #t   70
+
+# Extraction of even powers
+sub oddtest {
+  my ($x, $s, $t) = @_;
+  my ($ss, $tt) = mp($x)->odd();
+  ok $ss == $s && $tt == $t;
+}
+oddtest "1", 0, "1";						    #t   71
+oddtest "2", 1, "1";						    #t   72
+oddtest "4", 2, "1";						    #t   73
+oddtest "12", 2, "3";						    #t   74
+oddtest "0x10000000000000", 52, "1";				    #t   75
+oddtest "0x10000000400000", 22, "0x40000001";			    #t   76
+
+# Integer square root
+ok mp("0")->sqrt() == mp("0");					    #t   77
+ok mp("1")->sqrt() == mp("1");					    #t   78
+ok mp("4")->sqrt() == mp("2");					    #t   79
+ok mp("9")->sqrt() == mp("3");					    #t   80
+ok mp("16")->sqrt() == mp("4");					    #t   81
+ok mp("99")->sqrt() == mp("9");					    #t   82
+ok mp("100")->sqrt() == mp("10");				    #t   83
+ok mp("101")->sqrt() == mp("10");				    #t   84
+ok mp("120")->sqrt() == mp("10");				    #t   85
+ok mp("121")->sqrt() == mp("11");				    #t   86
+ok mp("10106623487257186586")->sqrt() == mp("3179091613");	    #t   87
+ok mp("14565040310136678240")->sqrt() == mp("3816417208");	    #t   88
+
+# Greatest common divisor
+
+ok Catacomb::MP::gcd("16", "12") == mp("4");			    #t   89
+ok mp("90980984098081324")->modinv("4398082908043") ==		    #t   90
+  mp("58497120524729235");
+
+sub gcdtest {
+  my ($u, $v, $g, $x, $y) = @_;
+  my ($gg, $xx, $yy) = Catacomb::MP::gcd($u, $v);
+  ok $g == $gg && $x == $xx && $y == $yy;
+}
+gcdtest "16", "12", "4", "-11", "15";				    #t   91
+gcdtest "12", "16", "4", "-1", "1";				    #t   92
+gcdtest "693", "609", "21", "-7", "8";				    #t   93
+gcdtest								    #t   94
+  "4398082908043", "90980984098081324",
+  "1", "-32483863573352089", "1570292150447";
+
+gcdtest "16", "-12", "4", "-11", "-15";				    #t   95
+gcdtest "-16", "12", "4", "11", "15";				    #t   96
+gcdtest "-12", "-16", "4", "1", "-1";				    #t   97
+gcdtest "-12", "16", "4", "1", "1";				    #t   98
+gcdtest "-693", "609", "21", "7", "8";				    #t   99
+gcdtest "693", "-609", "21", "-7", "-8";			    #t  100
+
+gcdtest "15", "0", "15", "1", "0";				    #t  101
+gcdtest "0", "15", "15", "0", "1";				    #t  102
+gcdtest "-5", "0", "5", "-1", "0";				    #t  103
+gcdtest "0", "-5", "5", "0", "-1";				    #t  104
+gcdtest "0", "0", "0", "0", "0";				    #t  105
+
+gcdtest 							    #t  106
+  "829561629303257626084392170900075",
+  "32498098450983560651904114638965",
+  "5",
+  "-29340810037249902802634060204608",
+  "748967211613630574419802053172497";
+
+# Jacobi symbol
+ok mp("5")->jac("4") == 1;					    #t  107
+ok mp("7")->jac("6") == -1;					    #t  108
+ok mp("27")->jac("15") == 0;					    #t  109
+ok mp("98729378979237498798347932749951")			    #t  110
+  ->jac("2132498039840981") == 1;
+
+# Modular square-root
+sub modsqrttest {
+  my ($p, $x, $r) = @_;
+  my $rr = mp($p)->modsqrt($x);
+  ok $rr == $r || $rr == mp($p) - $r;
+}
+modsqrttest "3", "1", "1";					    #t  111
+modsqrttest "5", "4", "3";					    #t  112
+modsqrttest							    #t  113
+ "13391974640168007623", "9775592058107450692", "3264570455655810730";
+
+# Factorial
+ok +Catacomb::MP->factorial(0) == mp("1");			    #t  114
+ok +Catacomb::MP->factorial(5) == mp("120");			    #t  115
+ok +Catacomb::MP->factorial(30) ==				    #t  116
+  mp("265252859812191058636308480000000");
+
+# Parsing
+sub parsetest {
+  my ($str, $rx, $x, $r) = @_;
+  my ($xx, $rr) = Catacomb::MP->fromstring($str, $rx);
+  ok defined($x) ? ($xx == $x && $rr eq $r) : !defined($xx);
+}
+parsetest "0", 10, mp("0"), "";					    #t  117
+parsetest "0z", 10, mp("0"), "z";				    #t  118
+parsetest "z", 10, undef, "";					    #t  119
+parsetest "8_27785", 0, mp("191"), "85";			    #t  120
+parsetest "8_27785", 10, mp("8"), "_27785";			    #t  121