[Maxima] Questions on modular arithmetic functions in rat3a.lisp
macrakis at alum.mit.edu
Thu Jun 21 13:47:34 CDT 2012
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.
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:
>> 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
> 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
> Are they in fact
> They are integers. It is somewhat unlikely that someone comes up with a
> interpretation of non-integer here, that makes good use of the rest of the
> 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
> Maxima mailing list
> Maxima at math.utexas.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Maxima