Bug #118677 for Math-GMP: [PATCH] add the root extraction methods

I had a need for broot(), so took the opportunity to add all 5 missing methods from <https://gmplib.org/manual/Integer-Roots.html>. These patches are based on the github repo, but I don't know how to build that - the INSTALL instructions don't appear to be relevant - so I have tested only by patching a 2.11 release tarball. Hugo

From 8be8ef5f9534b7a13fee00e008dcd0db6ebda22c Mon Sep 17 00:00:00 2001 From: Hugo van der Sanden <hv@crypt.org> Date: Tue, 8 Nov 2016 15:07:14 +0000 Subject: [PATCH 1/3] Support testing of functions returning a list --- t/01_gmppm.t | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) diff --git a/t/01_gmppm.t b/t/01_gmppm.t index af76416..a179477 100644 --- a/t/01_gmppm.t +++ b/t/01_gmppm.t @@ -7,7 +7,7 @@ use Math::GMP; use Test::More; use Config; -my ($f,$try,$x,$y,$ans,@tests,@data,@args,$ans1,$z,$line); +my ($f,$try,$x,$y,$ans,@tests,@data,@args,$ans1,$z,$line,$expect_list); @data = <DATA>; @tests = grep { ! /^&/ } @data; @@ -22,6 +22,12 @@ while (defined($line = shift @data)) { @args = split(/:/,$line,99); $ans = pop(@args); + $expect_list = 0; + if ($ans =~ s/^L//) { + $ans = [ split /,/, $ans ]; + $expect_list = 1; + } + if ( $args[0] =~ /^i([-+]?\d+)$/ ) { $try = "\$x = $1;"; } @@ -166,8 +172,11 @@ while (defined($line = shift @data)) { } } $ans1 = eval $try; - is( "$ans1", $ans, "Test worked: $try"); - + if ($expect_list) { + is_deeply($ans1, $ans, "Test worked: $try"); + } else { + is("$ans1", $ans, "Test worked: $try"); + } } # Test of bfac as described in the pod -- 2.10.2

From c14519cbc1887b5861056338c8f75fd8c897a800 Mon Sep 17 00:00:00 2001 From: Hugo van der Sanden <hv@crypt.org> Date: Tue, 8 Nov 2016 15:29:21 +0000 Subject: [PATCH 2/3] Support the "Root Extraction Functions" Functions from https://gmplib.org/manual/Integer-Roots.html, exposed as methods broot, brootrem, bsqrtrem, is_perfect_power and is_perfect_square to add to the existing bsqrt. --- GMP.xs | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/Math/GMP.pm | 43 ++++++++++++++++++++++++++++++++++++++ t/01_gmppm.t | 44 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 151 insertions(+) diff --git a/GMP.xs b/GMP.xs index 21f1a04..83ddea8 100644 --- a/GMP.xs +++ b/GMP.xs @@ -578,6 +578,36 @@ gmp_tstbit(m,n) RETVAL mpz_t * +broot(m,n) + mpz_t * m + unsigned long n + + CODE: + RETVAL = malloc (sizeof(mpz_t)); + mpz_init(*RETVAL); + mpz_root(*RETVAL, *m, n); + OUTPUT: + RETVAL + +void +brootrem(m,n) + mpz_t * m + unsigned long n + + PREINIT: + mpz_t * root; + mpz_t * remainder; + PPCODE: + root = malloc (sizeof(mpz_t)); + remainder = malloc (sizeof(mpz_t)); + mpz_init(*root); + mpz_init(*remainder); + mpz_rootrem(*root, *remainder, *m, n); + EXTEND(SP, 2); + PUSHs(sv_setref_pv(sv_newmortal(), "Math::GMP", (void*)root)); + PUSHs(sv_setref_pv(sv_newmortal(), "Math::GMP", (void*)remainder)); + +mpz_t * bsqrt(m) mpz_t * m @@ -588,4 +618,38 @@ bsqrt(m) OUTPUT: RETVAL +void +bsqrtrem(m) + mpz_t * m + + PREINIT: + mpz_t * sqrt; + mpz_t * remainder; + PPCODE: + sqrt = malloc (sizeof(mpz_t)); + remainder = malloc (sizeof(mpz_t)); + mpz_init(*sqrt); + mpz_init(*remainder); + mpz_sqrtrem(*sqrt, *remainder, *m); + EXTEND(SP, 2); + PUSHs(sv_setref_pv(sv_newmortal(), "Math::GMP", (void*)sqrt)); + PUSHs(sv_setref_pv(sv_newmortal(), "Math::GMP", (void*)remainder)); + +int +is_perfect_power(m) + mpz_t * m + + CODE: + RETVAL = mpz_perfect_power_p(*m) ? 1 : 0; + OUTPUT: + RETVAL + +int +is_perfect_square(m) + mpz_t * m + + CODE: + RETVAL = mpz_perfect_square_p(*m) ? 1 : 0; + OUTPUT: + RETVAL diff --git a/lib/Math/GMP.pm b/lib/Math/GMP.pm index 3f2c4ec..ebfe0fd 100644 --- a/lib/Math/GMP.pm +++ b/lib/Math/GMP.pm @@ -269,6 +269,23 @@ Returns the modular inverse of $x (mod $y), if defined. This currently returns 0 if there is no inverse (but that may change in the future). Behaviour is undefined when $y is 0. +=head2 broot + + my $x = Math::GMP->new(100); + my $root = $x->root(3); # int(100 ** (1/3)) => 4 + print $root; + +Returns the integer n'th root of its argument, given a positive integer n. + +=head2 brootrem + + my $x = Math::GMP->new(100); + my($root, $rem) = $x->rootrem(3); # 4 ** 3 + 36 = 100 + print "$x is $rem more than the cube of $root"; + +Returns the integer n'th root of its argument, and the difference such that +C< $root ** $n + $rem == $x >. + =head2 bsqrt my $x = Math::GMP->new(6); @@ -277,6 +294,32 @@ Behaviour is undefined when $y is 0. Returns the integer square root of its argument. +=head2 bsqrtrem + + my $x = Math::GMP->new(7); + my($root, $rem) = $x->sqrtrem(); # 2 ** 2 + 3 = 7 + print "$x is $rem more than the square of $root"; + +Returns the integer square root of its argument, and the difference such that +C< $root ** 2 + $rem == $x >. + +=head2 is_perfect_power + + my $x = Math::GMP->new(100); + my $is_power = $x->is_perfect_power(); + print "$x is " . ($is_power ? "" : "not ") . "a perfect power"; + +Returns C<TRUE> if its argument is a power, ie if there exist integers a +and b with b > 1 such that C< $x == $a ** $b >. + +=head2 is_perfect_square + + my $x = Math::GMP->new(100); + my $is_square = $x->is_perfect_square(); + print "$x is " . ($is_square ? "" : "not ") . "a perfect square"; + +Returns C<TRUE> if its argument is the square of an integer. + =head2 legendre $x = Math::GMP->new(6); diff --git a/t/01_gmppm.t b/t/01_gmppm.t index a179477..09d7e24 100644 --- a/t/01_gmppm.t +++ b/t/01_gmppm.t @@ -56,6 +56,15 @@ while (defined($line = shift @data)) { elsif ($f eq "square_root") { $try .= 'Math::GMP::bsqrt($x);'; } + elsif ($f eq "square_rootrem") { + $try .= '[ Math::GMP::bsqrtrem($x) ];'; + } + elsif ($f eq "perfect_power") { + $try .= '$x->is_perfect_power'; + } + elsif ($f eq "perfect_square") { + $try .= '$x->is_perfect_square'; + } elsif ($f eq 'uintify') { $try .= "Math::GMP::uintify(\$x);"; $ans = pop(@args) if ($Config{longsize} == 4 && scalar @args > 1); @@ -156,6 +165,12 @@ while (defined($line = shift @data)) { elsif ($f eq 'test_bit') { $try .= "Math::GMP::gmp_tstbit(\$x, \$y);"; } + elsif ($f eq 'root') { + $try .= "\$x->broot(\$y)"; + } + elsif ($f eq 'rootrem') { + $try .= "[ \$x->brootrem(\$y) ]"; + } else { if ( $args[2] =~ /^i([-+]?\d+)$/ ) { $try .= "\$z = $1;"; @@ -608,6 +623,15 @@ babcdefgh,36:808334348993 1:0:1 3:1:1 3:2:0 +&root +16:i2:4 +16:i4:2 +999:i3:9 +-1:i3:-1 +&rootrem +16:i2:L4,0 +999:i3:L9,270 +-2:i3:L-1,-1 &square_root 16:4 1:1 @@ -615,6 +639,26 @@ babcdefgh,36:808334348993 100:10 101:10 99:9 +&square_rootrem +16:L4,0 +100:L10,0 +101:L10,1 +99:L9,18 +0:L0,0 +&perfect_power +99:0 +100:1 +101:0 +0:1 +-27:1 +-9:0 +&perfect_square +99:0 +100:1 +101:0 +0:1 +-27:0 +-9:0 &probab_prime 5:10:2 6:10:0 -- 2.10.2

From 6532ccf7a6c043cbf9da943b3d540d8cea01be9a Mon Sep 17 00:00:00 2001 From: Hugo van der Sanden <hv@crypt.org> Date: Tue, 8 Nov 2016 15:36:26 +0000 Subject: [PATCH 3/3] Prepare for 2.12 --- Changes | 4 ++++ lib/Math/GMP.pm | 2 +- 2 files changed, 5 insertions(+), 1 deletion(-) diff --git a/Changes b/Changes index 110758c..6ec00e1 100644 --- a/Changes +++ b/Changes @@ -1,5 +1,9 @@ Revision history for Perl extension Math::GMP. +2.12 2016-11-08 Hugo + - Add support for testing methods that return lists. + - Add broot, brootrem, bsqrtrem, is_perfect_power, is_perfect_square + 2.11 2015-08-16 Shlomif - Got the distribution to have full POD coverage and check all functions for usage. diff --git a/lib/Math/GMP.pm b/lib/Math/GMP.pm index ebfe0fd..58da348 100644 --- a/lib/Math/GMP.pm +++ b/lib/Math/GMP.pm @@ -65,7 +65,7 @@ require AutoLoader; # names by default without a very good reason. Use EXPORT_OK instead. # Do not simply export all your public functions/methods/constants. -our $VERSION = '2.11'; +our $VERSION = '2.12'; =begin Removed -- 2.10.2