logcount bignum negatives optimization

* logcount bignum negatives optimization
@ 2003-05-22  0:39 Kevin Ryde
  2003-05-30  0:21 ` Kevin Ryde
  0 siblings, 1 reply; 2+ messages in thread
From: Kevin Ryde @ 2003-05-22  0:39 UTC (permalink / raw)


[-- Attachment #1: Type: text/plain, Size: 504 bytes --]

The zeros count for logcount on negatives can be done with mpz_hamdist
by passing -1 for the second operand.  This saves initializing and
clearing a temporary mpz_t.

	* numbers.c (z_negative_one): New variable.
	(scm_init_numbers): Initialize it.
	(scm_logcount): Use it and mpz_hamdist to count zeros for negatives.

	* tests/numbers.test (logcount): More tests.

I haven't changed the positive case, except to put it first and to
share the scm_remember_upto, but a few tests of that won't go astray.


[-- Attachment #2: numbers.c.logcount.diff --]
[-- Type: text/plain, Size: 1364 bytes --]

--- numbers.c.~1.188.~	2003-05-13 09:14:53.000000000 +1000
+++ numbers.c	2003-05-15 08:55:23.000000000 +1000
@@ -119,6 +119,7 @@
 \f
 
 static SCM abs_most_negative_fixnum;
+static mpz_t z_negative_one;
 
 \f
 
@@ -1396,20 +1397,11 @@
   else if (SCM_BIGP (n))
     {
       unsigned long count;
-      if (mpz_sgn (SCM_I_BIG_MPZ (n)) < 0)
-        {
-          mpz_t z_n;
-          mpz_init (z_n);
-          mpz_com (z_n, SCM_I_BIG_MPZ (n));
-          scm_remember_upto_here_1 (n);
-          count = mpz_popcount (z_n);
-          mpz_clear (z_n);
-        }
+      if (mpz_sgn (SCM_I_BIG_MPZ (n)) >= 0)
+        count = mpz_popcount (SCM_I_BIG_MPZ (n));
       else
-        {
-          count = mpz_popcount (SCM_I_BIG_MPZ (n));
-          scm_remember_upto_here_1 (n);
-        }
+        count = mpz_hamdist (SCM_I_BIG_MPZ (n), z_negative_one);
+      scm_remember_upto_here_1 (n);
       return SCM_MAKINUM (count);
     }
   else
@@ -4217,6 +4209,8 @@
   abs_most_negative_fixnum = scm_i_long2big (- SCM_MOST_NEGATIVE_FIXNUM);
   scm_permanent_object (abs_most_negative_fixnum);
 
+  mpz_init_set_si (z_negative_one, -1);
+
   /* It may be possible to tune the performance of some algorithms by using
    * the following constants to avoid the creation of bignums.  Please, before
    * using these values, remember the two rules of program optimization:

[-- Attachment #3: numbers.test.logcount.diff --]
[-- Type: text/plain, Size: 533 bytes --]

--- numbers.test.~1.23.~	2003-05-10 13:01:51.000000000 +1000
+++ numbers.test	2003-05-22 10:37:19.000000000 +1000
@@ -1918,6 +1918,20 @@
 
 (with-test-prefix "logcount"
   
+  (with-test-prefix "2^i"
+    (do ((n 1 (ash n 1))
+	 (i 0  (1+ i)))
+	((> i 256))
+      (pass-if n
+	(= 1 (logcount n)))))
+
+  (with-test-prefix "2^i-1"
+    (do ((n 0 (1+ (ash n 1)))
+	 (i 0  (1+ i)))
+	((> i 256))
+      (pass-if n
+	(= i (logcount n)))))
+
   (with-test-prefix "-2^i, meaning ...11100..00"
     (do ((n -1 (ash n 1))
 	 (i 0  (1+ i)))

[-- Attachment #4: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

^ permalink raw reply	[flat|nested] 2+ messages in thread