Re: bignums

On Wed, Sep 06, 2006 at 12:12:12AM +0200, Mathieu Bouchard wrote:
>   This message is in MIME format.  The first part should be readable text,
>   while the remaining parts are likely unreadable without MIME-aware tools.

> On Tue, 5 Sep 2006, Ondrej Bilka wrote:
> 
> >With GMP benchmark I discovered that multipling 2 fixnums into bignum is 
> >slow because it multiplies 2 temporary bignums. Without heavy magic its 
> >unsolvable.
> 
> What's the heavy magic like? Abstract out multiplication as something that 
> happens between two or three BDIGIT* pointers (depending on whether it's 
> inplace or not). This will allow to use temporary stack-allocated 
> BDIGIT[], which is much faster than VALUE and GC.

I thought that assembler has something like MULC which like ADC handles
carry but didnt find anything.
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.
Can somebody with 64bit try this.
Compare with current HEAD/1.8. I wondered why my code causes slowdown and cause
was that recent commit slowed method dispatching.

> 
> Unless #coerce is currently involved in creating the temporaries?
> 
> BTW, is there any plan to use harmonics in order to speed up very very big 
> multiplications? I mean like, pad the two bignums to the size of the 
> result rounded up to a product of powers of small primes, then apply a 
> forward Fast Fourier Transform on both bignums, then do pointwise complex 
> multiplication, then do an inverse Fast Fourier Transform on the resulting 
> spectrum and perform a carry pass. (here, each digit holder has to be much 
> bigger than the digit it holds, because handling carries can only be done 
> completely at the end)
I could try. Probably I modify libtommath to support fft for extra long
nums. for shorter perform asymptotic worse algorithms better
> 
>  _ _ __ ___ _____ ________ _____________ _____________________ ...
> | Mathieu Bouchard - t駘:+1.514.383.3801 - http://artengine.ca/matju
> | Freelance Digital Arts Engineer, Montr饌l QC Canada
> 
> 


Index: numeric.c
===================================================================
RCS file: /src/ruby/numeric.c,v
retrieving revision 1.143
diff -u -r1.143 numeric.c
--- numeric.c	4 Sep 2006 20:10:45 -0000	1.143
+++ numeric.c	9 Sep 2006 10:04:06 -0000
@@ -1973,13 +1973,26 @@
 /* avoids an optimization bug of HP aC++/ANSI C B3910B A.06.05 [Jul 25 2005] */
         volatile
 #endif
-	long a, b, c;
-	VALUE r;
+	long a, b;
 
 	a = FIX2LONG(x);
-	if (a == 0) return x;
+	/*if (a == 0) return x;*/
 
 	b = FIX2LONG(y);
+
+#if SIZEOF_LONG*2 <= SIZEOF_LONG_LONG
+	LONG_LONG d;
+	d=((LONG_LONG) a)*b;
+	if (FIXABLE(d)) return LONG2FIX(d);
+	return rb_ll2inum(d);
+#else
+	VALUE r;
+ 	long c;
+	#define SQRT_LONG_MAX (1<<(sizeof(long)*4-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);
 
@@ -1987,6 +2000,7 @@
 	    r = rb_big_mul(rb_int2big(a), rb_int2big(b));
 	}
 	return r;
+#endif
     }
     switch (TYPE(y)) {
       case T_BIGNUM: