Questions on modular arithmetic functions in rat3a.lisp

On 6/21/2012 6:35 AM, Camm Maguire wrote:
> Greetings!
>
> 1) The comments indicate that modulus is nil or positive.  Is it always
> an integer?
All uses of modular arithmetic in the existing code assume that the 
modulus is
a prime positive integer.  The system refuses to allow  modulus:2.5;   
it also
gives a warning for modulus:20,  a non-prime.  It goes into an infinite 
loop for modulus:-45.  (a bug...)

> 2) The comments indicate that if modulus is non-nil, the arguments to
> ctimes (et.al. ?) are numberp and less than modulus.
proper elements should be less than  modulus/2  in abs val.  except if 
modulus = 2, then the
two proper elements are 0,1.
e.g. modulo 5, the numbers are -2,-1,0,1,2.

If ctimes is given numbers outside that range the result should be in 
that range.

>   Are they in fact
> integers?

They are integers.  It is somewhat unlikely that someone comes up with a 
meaningful
interpretation of non-integer here, that makes good use of the rest of 
the mechanisms.
>   Are they bounded from below?
the result is bounded from below by half the modulus.
> 3) GCL has a C implementation of ctimes which balances modular
> arithmetic between -modulus/2 and modulus/2.  The generic lisp version
> seems only to implement the upper bound.
That then is a mistake.
>   Is there a reason for this?
Probably it is an error if SBCL does not use a balanced representation..
> Is the modular balancing necessary?
It is possible to use any sequential set of numbers, e.g.   0,1,2,3,4   
instead of -2,-1,0,1,2  for
modulus=5, and build a system around that choice.  The balanced choice 
has a few conveniences
such as some calculations over the integers mod <some huge prime>  look 
exactly like the
calculations over the integers.

> 4) Why is bctimes/rem used in cbexpt instead of ctimes/mod?

  bctimes is faster because it doesn't need to check to see if modulus = 
nil .  It is called repeatedly
from within the expt program.


If there is an interest in making these programs run fast, it may be 
worthwhile to separate
out the case of
modulus <=  2*(most-positive-fixnum)

where the arithmetic can be done in registers etc.

This is in fact the most common case and is presumably slowed down by 
the prospect of
ever encountering a bignum modulus.

See  the code in the reciprocal  in rat3a, as an example.  But if you 
want to code other stuff in C
as was done by Bill Schelter for GCL, that would make some things 
faster. Whether one would
notice it depends on how much rational polynomial arithmetic was being used.

RJF