Re: bignums

On Sun, Sep 10, 2006 at 05:05:22AM +0200, [e-mail] wrote:
> Hi,
> 
> At Sat, 9 Sep 2006 19:10:04 +0900,
> Ondrej Bilka wrote in [ruby-core:08819]:
> > I thought that assembler has something like MULC which like ADC handles
> > carry but didnt find anything.
Assembler IMUL usualy result in twice large number stored at two registers. But it's not crossplatform. GAS manual doesnt mention amd64 only ia-64. Don't know how with other platforms.

> > I written another patch. 
> > For 32 bits I use long long multiplication which is faster than checking by division.
> > For 64bits I have heuristic that if both are <2**31 is not necessary
> > perform check. But I am not sure if it will cause slowdown or speedup.
> 
> You should use SIGNED_VALUE.
> 
I forgot about  "if (a == 0) return x;"
Its not needed in 32bit case so I moved it.
Originaly I thought that I can do it without division.
Because I dont know how get overflow flag in c it will be there until I
discover how use assembler on 64bits. I dont quite understand ia-64 registers.  GAS seem not support amd64.  Or I have error in this
asm( "imul %%rdx;"/*tried imuld ...too*/
		:"=a"(x),"=d"(y)
		:"a"(x),"d"(y));


Index: numeric.c
===================================================================
RCS file: /src/ruby/numeric.c,v
retrieving revision 1.143
diff -p -U2 -r1.143 numeric.c
--- numeric.c	4 Sep 2006 20:10:45 -0000	1.143
+++ numeric.c	10 Sep 2006 12:15:12 -0000
@@ -1974,18 +1974,34 @@ fix_mul(VALUE x, VALUE y)
         volatile
 #endif
-	long a, b, c;
+	SIGNED_VALUE a, b;
+#if SIZEOF_VALUE * 2 <= SIZEOF_LONG_LONG
+	LONG_LONG d;
+#else
+	SIGNED_VALUE c;
 	VALUE r;
+#endif
 
 	a = FIX2LONG(x);
-	if (a == 0) return x;
-
 	b = FIX2LONG(y);
+
+#if SIZEOF_VALUE * 2 <= SIZEOF_LONG_LONG
+	d = (LONG_LONG)a * b;
+	if (FIXABLE(d)) return LONG2FIX(d);
+	return rb_ll2inum(d);
+#else
+#	define SQRT_LONG_MAX (1<<((SIZEOF_VALUE*CHAR_BIT-1)/2))
+	/*tests if N*N would overflow*/
+#	define FIT_SQRT_LONG(n) (((n)<SQRT_LONG_MAX)&&((N)>=-SQRT_LONG_MAX))
+	if (FIT_SQRT_LONG(a) && FIT_SQRT_LONG(b))
+	    return LONG2FIX(a*b);
 	c = a * b;
 	r = LONG2FIX(c);
 
+	if (a == 0) return x;
 	if (FIX2LONG(r) != c || c/a != b) {
 	    r = rb_big_mul(rb_int2big(a), rb_int2big(b));
 	}
 	return r;
+#endif
     }
     switch (TYPE(y)) {

> 
> -- 
> Nobu Nakada