Questions on modular arithmetic functions in rat3a.lisp

Greetings, and thanks so much!

Just verified that at least in the testsuite, inputs to cdifference,
cplus, and ctimes are in fact (<= (- (ash modulus -1)) x (ash modulus
-1)) as you state.  That makes for an interesting optimization in which
the type of one variable can be inferred from another.  Bill Schelter
did provide C implementations for these in GCL making use of this
relationship.  At present, equivalent performance can be had in lisp,
with some advantage in cleaning the lines of code dependency.  More also
can be done along these lines.  Whether it is worth it or not is another
question.  It looks like a factor of five to ten is available in some
routines.

bctimes is in fact much slower because it does *not* check modulus :-).  

Is it worth submitting a patch?

Why does cremainder check for float inputs?

Take care,

Richard Fateman <fateman at eecs.berkeley.edu> writes:

> 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
>
>
>
>
>

-- 
Camm Maguire			     		    camm at maguirefamily.org
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah