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?
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.
2. If a modular algorithm runs out of primes,some more are computed.
This is rather unlikely
to happen, at least unless numbers with more than 180 decimal digits
occur in modular polynomial GCD
algorithms.
3. Your number is 32768. It seems that what you want is a number such
that x*x (NOT x+x)
is a fixnum.
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).
...
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.
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.
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.
RJF