gcl-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gcl-devel] [Maxima] Considering 64bit fixnums on 64bit GCL


From: Camm Maguire
Subject: Re: [Gcl-devel] [Maxima] Considering 64bit fixnums on 64bit GCL
Date: Fri, 24 May 2013 13:15:47 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)

Greetings, and thanks so much for your note!

Richard Fateman <address@hidden> writes:

> On 5/24/2013 7:51 AM, Camm Maguire wrote:
>> Greetings!  I am considering backporting this into the production branch
>> of gcl.   I have a local version which passes all maxima tests.
>>
>> As you know, many of these run using optimized modular arithmetic.  In
>> particular, one cannot do circular modular multiplication in 64bits in
>> registers.
>>
>> maxima defines *bigprimes* as < (ash most-positive-fixnum -1).  My
>> question is, is it not sensible to make this
>>
>> < (ash 1 (ash (integer-length most-positive-fixnum) -1))
>>
>> Take care,
> Huh?

Yes, I meant a list of (largest) primes satisfying the above limits.
They permit a sum to not overflow the fixnum boundaries, but not a
product.

These days on 64bit machines, and even most 32bit machines, two 32bit
numbers can be multiplied in machine registers.  Is 2147483648 large
enough for the algorithm?

> 1. *bigprimes* is a LIST, initially of length 20, of the largest prime
> numbers x such that
> x+x is still a fixnum. At least that appears to be the intention in Maxima.
>
> 3. Your number is 32768.  It seems that what you want is a number such
> that x*x   (NOT x+x)
> is a fixnum.

Yes, currently, but what if this number was 2147483648?  Actually, I
think it is best to take the maximum of (ash 1 (ash (integer-length
most-positive-fixnum) -1)) and (ash 1 31).

>
> 4. I don't know what you mean by circular modular multiplication in
> 64bits in registers. Is this
> some common lisp feature I don't know about?  Or are you using
> something for bignum arithmetic?
> (In which case I suggest you consider using GMP, already used by some
> other lisps. Advantage of GMP
> is you don't have to debug it, and it is likely to be fast on large
> numbers in case you have
> an audience including number theorists).
>

GMP is used already when fixnums overflow.  This is still heavy compared
to a register multiply with no function call.

> ...
> Why x+x rather than x^2 ?
> If you are doing modular arithmetic as part of (say) modular polynomial GCD
> you will be doing  r := a*b mod p.  It would be fast if a,b, r, p and
> a*b are all fixnum.

Yes, exactly.

>
> But you will have to do more of them to build up a result using the
> Chinese Remainder Algorithm, if p is small.
>
> It might be more efficient ultimately if a*b is not necessarily a
> fixnum, but a,b,p and r are fixnums.
> No storage of bignums.  Fewer modular images needed. Indeed, Half.
>

Thank you so much, here is the tradeoff.  My point is that if the
somewhat common bound in current use is (ash 1 30), and this is deemed
acceptable performance wise given the remainder algorithm, can't we cap
the numbers in *bigprimes* at this level even when most-positive-fixnum
gets larger, so that maybe we can do the product in fixnums as well?  Do
you expect big gains from the reduction in iterations needed in the
algorithm as the prime goes from 30 bits to 62?

> That is, I think, the rationale.  If any timing trials were done, they
> were probably done in ancient
> times on PDP-6 or PDP-10 computers in Maclisp.
>

This was my guess too.  While I haven't studied the algorithm, from your
comments I'm gathering that the number of iterations needed is of the
order of the length of *bigprimes*, which has currently been lowered to
~20.  Cutting it in half again by using larger primes doesn't seem worth
it in comparison to getting the product done in fixnums.

Actually, I have a local GCL with 64bit fixnums to test with.  I'll try
to report a few timing results.  If you can suggest a good simple
benchmark, that would be great.

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]