octave: libinterp/corefcn/sparse-xpow.cc comparison

sparse-xpow.cc: Use faster multiplication technique, this time for complex

author	Arun Giridhar <arungiridhar@gmail.com>
date	Sun, 11 Sep 2022 13:53:38 -0400
parents	45984c799215
children	44cf6bbeeca9

comparison

equal deleted inserted replaced

-:45984c799215
+:3eab70385569
 SparseComplexMatrix result (atmp);
 btmp--;
-while (btmp > 0)
+// Select multiplication sequence based on sparsity of atmp.
-{
+// See the long comment in xpow (const SparseMatrix& a, double b)
-if (btmp & 1)
+// for more details.
+//
+// FIXME: Improve this threshold calculation.
+uint64_t sparsity = atmp.numel() / atmp.nnz(); // reciprocal of density
+int threshold = (sparsity >= 10000) ? 40
+: (sparsity >=  1000) ? 30
+: (sparsity >=   100) ? 20
+: 3;
+if (btmp > threshold) // use squaring technique
+{
+while (btmp > 0)
+{
+if (btmp & 1)
+result = result * atmp;
+btmp >>= 1;
+if (btmp > 0)
+atmp = atmp * atmp;
+}
+}
+else // use linear multiplication
+{
+for (int i = 0; i < btmp; i++)
 result = result * atmp;
-btmp >>= 1;
-if (btmp > 0)
-atmp = atmp * atmp;
 }
 retval = result;
 }

Mercurial > octave