Re: [Gcl-devel] gcd proposal

[Camm Maguire]

Greetings!

Andrei Zorine <address@hidden> writes:

> I found the algorithm in Knuth's TAOCP vol.2. Then I decided to find out how 
> Maxima comeputes gcd
> and finally found out that it delegates it to gcl. Then I patched my 
> gcl-2.5.2 (and sent the patch
> to you). Later I found words 'bin-gcd' in grep's output. I think it's ok to 
> have binary gcd in gcl
> instead of Maxima. I haven't seen how exactly the new code is installed, I 
> don't know what to look
> at. I hope you simply replaced the get-gcd's body thith the new one.
> 

OK, I don't know whether gcd is time critical to maxima, but assuming
that it is, there are ways to speed things up apart from accelerating
the inner algorithm like we've been doing.  For heavily used
functions, it is often expensive to pass variables via the lisp stack
(vs_base);  GCL can optimize the call to the function to use the C
stack instead (in non-safe compile mode, usually the default).

For example, here is a call right now in maxima's simp.c, compiled
from simp.lisp:

        base[0]= CMPcaddr((V444));
        base[1]= CMPcaddr((V445));
        vs_top=(vs_base=base+0)+2;
        Lgcd();

This could be optimized in this case to

        get_gcd(CMPcaddr((V444)),CMPcaddr((V445)));

if it were important for performance.  Perhaps you could suggest a
benchmark, and we could see whether this would improve things?


> I have also found that new gcd code works faster for fixnums than clisp's 
> one, but still is second
> with bignums. The next posible step would be either to implement binary gcd 
> for bignums, or to call
> mpn_gcd directly from get-gcd. I don't know which is faster yet. This needs 
> more testing. (and
> reading Knuth as well :))
> 

I like the idea of mpn_gcd.  We have to make sure it does not
introduce bad allocation calls, as we are now using relocatable
bignums by default.  Again, perhaps you could suggest a good
benchmark.  It really would only be worth working on this if it is
determined that gcd is a time critical component of programs such as
maxima. 

Take care,

> 
> Camm Maguire wrote:
> > Greetings!  One other thought on this.  Given that you found it in
> > lisp in maxima, you probably need/want this code inlined in compiled
> > lisp functions calling gcd (with declared fixnum args of course).
> > Please let me know if this is the case, and we can instruct the
> > optimizer to inline this snippet.
> > Take care,
> >
> 
> 
> 
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gcl-devel
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah