Questions on modular arithmetic functions in rat3a.lisp

The current code gives a warning for non-prime moduli, but I believe that
positive integer non-primes behave just fine for addition, subtraction, and
multiplication.  But of course with a non-prime modulus, there are non-zero
zero-divisors, so division is problematic.

I suppose non-integer moduli could be defined in the same way, i.e. a MODOP
b == mod(a OP b,M), but I'm not sure it's terribly useful to have a global
modulus like that.

            -s

On Thu, Jun 21, 2012 at 6:17 PM, Richard Fateman
<fateman at eecs.berkeley.edu>wrote:

> 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
>
>
> ______________________________**_________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/**mailman/listinfo/maxima<http://www.math.utexas.edu/mailman/listinfo/maxima>;
>