Faster implementation of perm_sign

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Bonjour,

Preparing a lecture about permutations made me realise that perm_sign
(which I contributed in 2017) could be improved by successively
composing with transpositions instead of computing the cycle
decomposition.  This does require keeping track of the inverse
permutation.  I am attaching a patch.  Empirically, this seems to be at
least 35% faster than the old implementation:

Before:

? forperm(8,p,s=permsign(p));
  ***   last result computed in 15 ms.
? forperm(9,p,s=permsign(p));
  ***   last result computed in 130 ms.
? forperm(10,p,s=permsign(p));
  ***   last result computed in 1,221 ms.
? forperm(11,p,s=permsign(p));
  ***   last result computed in 14,319 ms.

After:

? forperm(8,p,s=permsign(p));
  ***   last result computed in 9 ms.
? forperm(9,p,s=permsign(p));
  ***   last result computed in 83 ms.
? forperm(10,p,s=permsign(p));
  ***   last result computed in 786 ms.
? forperm(11,p,s=permsign(p));
  ***   last result computed in 8,776 ms.

Best wishes,

Peter


>From d7ee63ee461d45c5bdf39ed440e961a229fc94a2 Mon Sep 17 00:00:00 2001
From: Peter Bruin <P.J.Bruin@math.leidenuniv.nl>
Date: Tue, 24 Feb 2026 08:15:59 +0100
Subject: [PATCH] speed up perm_sign

---
 src/basemath/perm.c | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

diff --git a/src/basemath/perm.c b/src/basemath/perm.c
index 7532e621c5..a81b91edae 100644
--- a/src/basemath/perm.c
+++ b/src/basemath/perm.c
@@ -531,10 +531,19 @@ long
 perm_sign(GEN v)
 {
   pari_sp av = avma;
-  GEN c = vecperm_orbits_i(mkvec(v), lg(v)-1);
-  long i, l = lg(c), s = 1;
-  for (i = 1; i < l; i++)
-    if (odd(lg(gel(c, i)))) s = -s;
+  long i, j, l = lg(v), s = 1;
+  GEN w = perm_inv(v);
+  v = vecsmall_copy(v);
+  while (--l > 1)
+  {
+    if ((i = v[l]) != l)
+    {
+      j = w[l];
+      v[j] = i;
+      w[i] = j;
+      s = -s;
+    }
+  }
   return gc_long(av,s);
 }
 
-- 
2.51.0