Re: [Gcl-devel] Fwd: secret of rat3a/ctimes with gcl ?

[Camm Maguire]

Greetings!  OK, I have a version which is much faster now, but first I'd
like to ask a few questions if I might.

GCL has a legacy C implementation of ctimes and cplus which is entirely
sidestepped when you write generic code, hence the slowdown.  This
implementation seems to make some assumptions which I'd like to make
sure are valid.  The main one is that when modulus is set, the input
arguments to ctimes and cplus are automatically bounded in absolute
value by modulus.  Is this always guaranteed to be true?

The second seems to be the need for a signed representation of the
modular arithmetic.  What depends on this, maxima wise?

Is modulus typically set or unset?

Secondly, can you please unpack for me the polynomial representation as
a list of small integers below?  How do the numbers in the list
correspond to polynomial coefficients 'smaller than 7'?

Volker van Nek <address@hidden> writes:

> Just
> modulus : 7 $
>
> My polynomial '(13 1 12 2 11 3 10 4 0 5) for testing had coefficients smaller 
> than 7.
>
> Greetings
> Volker
>
> 2012/6/14 Camm Maguire <address@hidden>
>
>     Greetings, and thanks!  What are you using for the modulus setting in
>     your timings?
>    
>     Volker van Nek <address@hidden> writes:
>    
>     > Hi Camm,
>     >
>     > I attach a file with my versions psq1 and psq2 and with ptimes1 from 
> rat3a.lisp and some functions from rat3a.lisp and optimize.lisp which
>     are
>     > envolved in running ptimes1 and ctimes.
>     >
>     > Greetings
>     > Volker
>     >
>     > 2012/6/14 Camm Maguire <address@hidden>
>     >
>     >     Greetings!  Could you please post the source to psq1, psq1, and 
> ptimes1?  Thanks!
>     >
>     >     Volker van Nek <address@hidden> writes:
>     >
>     >     > Hi Camm. Greetings!
>     >     >
>     >     > Here at work I have a (damned slow) Computer which runs Maxima on 
> sbcl and I also performed a timing test with psq1, psq2 and rat3a/
>     ptimes1.
>     >     >
>     >     > (%i4) :lisp (time (dotimes (i 100000) (psq1 '(13 1 12 2 11 3 10 4 
> 0 5))))
>     >     >
>     >     > Evaluation took:
>     >     >   0.460 seconds of real time
>     >     >   0.428026 seconds of total run time (0.424026 user, 0.004000 
> system)
>     >     >   [ Run times consist of 0.016 seconds GC time, and 0.413 seconds 
> non-GC time. ]
>     >     >   93.04% CPU
>     >     >   1,103,390,864 processor cycles
>     >     >   35,201,008 bytes consed
>     >     >  
>     >     > NIL
>     >     > (%i4) :lisp (time (dotimes (i 100000) (psq2 '(13 1 12 2 11 3 10 4 
> 0 5))))
>     >     >
>     >     > Evaluation took:
>     >     >   0.301 seconds of real time
>     >     >   0.264016 seconds of total run time (0.264016 user, 0.000000 
> system)
>     >     >   [ Run times consist of 0.012 seconds GC time, and 0.253 seconds 
> non-GC time. ]
>     >     >   87.71% CPU
>     >     >   723,411,304 processor cycles
>     >     >   35,198,904 bytes consed
>     >     >  
>     >     > NIL
>     >     > (%i4) :lisp (time (dotimes (i 100000) (ptimes1 '(13 1 12 2 11 3 
> 10 4 0 5) '(13 1 12 2 11 3 10 4 0 5))))
>     >     >
>     >     > Evaluation took:
>     >     >   1.050 seconds of real time
>     >     >   1.024065 seconds of total run time (1.020064 user, 0.004001 
> system)
>     >     >   [ Run times consist of 0.004 seconds GC time, and 1.021 seconds 
> non-GC time. ]
>     >     >   97.52% CPU
>     >     >   2,520,188,384 processor cycles
>     >     >   21,600,864 bytes consed
>     >     >  
>     >     > NIL
>     >     >
>     >     > Here the number of processor cycles corresponds to the timing 
> results I expected.
>     >     >
>     >     > psq2 uses just (mod (* a b) modulus) where
>     >     >
>     >     > psq1 uses
>     >     >
>     >     > (cond
>     >     >   ((not (null modulus))
>     >     >     (let ((.n. (mod (* a b) modulus)))
>     >     >       (cond
>     >     >         ((<= (* 2 .n.) modulus) .n.)
>     >     >         (t (- .n. modulus)) )))
>     >     >
>     >     > at the same place, which is a lot more!
>     >     >
>     >     > rat3a/ptimes1 even uses rat3a/ptimes instead of rat3a/ctimes 
> which puts a lot of conditionals on top and it uses an algorithm which
>     consists
>     >     of
>     >     > nearly twice the number of multiplications and additions.
>     >     >
>     >     > How can it happen, that doing twice the work is faster in gcl 
> than just doing it once? sbcl shows the timings I expected. What is
>     different
>     >     with
>     >     > gcl?
>     >     >
>     >     > Volker
>     >     >
>     >     > 2012/6/13 Volker van Nek <address@hidden>
>     >     >
>     >     >     Hi Camm. Greetings!
>     >     >
>     >     >     Thank you for taking your time for this.
>     >     >
>     >     >     I don't expect overflowing the fixnum bounds, the numbers are 
> very small. Using e.g. a modulus of 7 the multiplication is of type
>     3*4.
>     >     >
>     >     >     (setq si::*notify-gbc* t)
>     >     >     I do not understand what the answers want to tell me. I hope 
> you know.
>     >     >
>     >     >     I did some experiments with (declare (integer a b c)), but 
> this did not seem to have influence.
>     >     >
>     >     >     I attached the code in two variants and a session introducing 
> the function and some timing results on my computer.
>     >     >
>     >     >     Thanks in advance.
>     >     >
>     >     >     Volker van Nek
>     >     >
>     >     >     2012/6/13 Camm Maguire <address@hidden>
>     >     >
>     >     >         Greetings!
>     >     >
>     >     >         I'd like to actually see your implementation to make 
> sure.  But my guess
>     >     >         is that the unsigned arithmetic is overflowing the fixnum 
> bounds,
>     >     >         i.e. producing bignums.  You might get an idea by (setq 
> si::*notify-gbc*
>     >     >         t).  Is anything known about modulus lisp-type wise?
>     >     >
>     >     >         Volker van Nek <address@hidden> writes:
>     >     >
>     >     >         > Hi Camm,
>     >     >         >
>     >     >         > there was no answer on the Maxima list to my question. 
> Perhaps you might have an idea.
>     >     >         >
>     >     >         > Thanks in advance
>     >     >         > Volker van Nek
>     >     >         >
>     >     >         > ---------- Forwarded message ----------
>     >     >         > From: Volker van Nek <address@hidden>
>     >     >         > Date: 2012/6/9
>     >     >         > Subject: secret of rat3a/ctimes with gcl ?
>     >     >         > To: address@hidden
>     >     >         >
>     >     >         > I have coded a squaring function for polynomials in 
> finite fields. As expected it is roughly 1.8 times faster than
>     multiplying
>     >     poly*poly
>     >     >         with rat3a
>     >     >         > /ptimes, wich is the underlying lisp function for 
> Maxima level fasttimes.
>     >     >         >
>     >     >         > To multiply the coefficients the function ptimes uses 
> ctimes, which multiplies and reduces the result by a balanced modulus.
>     From
>     >     rat3a:
>     >     >         >
>     >     >         >   (defmacro mcmod (n) ;;; gives answers from -modulus/2 
> ...0 1 2 +modulus/2
>     >     >         >     `(let ((.n. (mod ,n modulus)))
>     >     >         >       (cond ((<= (* 2 .n.) modulus) .n.)
>     >     >         >         (t (- .n. modulus)))))
>     >     >         >
>     >     >         >   (defun ctimes (a b)
>     >     >         >     (cond ((null modulus) (* a b))
>     >     >         >       (t (mcmod (* a b)))))
>     >     >         >
>     >     >         > In my squaring function I want to replace each (ctimes 
> a b) by simply (mod (* a b) modulus). I need positive results.
>     >     >         >
>     >     >         > As expected with clisp and sbcl this replacement is 
> faster than ctimes, but with gcl this replacement (which does less!)
>     slows down
>     >     the
>     >     >         whole
>     >     >         > function by a factor 3.
>     >     >         >
>     >     >         > Is there a hidden secret about ctimes with gcl? Any 
> hints are welcome.
>     >     >         >
>     >     >         > Volker van Nek
>     >     >         >
>     >     >
>     >     >         --
>     >     >         Camm Maguire                                       
> address@hidden
>     >     >         
> ==========================================================================
>     >     >         "The earth is but one country, and mankind its citizens." 
>  --  Baha'u'llah
>     >     >
>     >
>     >     --
>     >     Camm Maguire                                       address@hidden
>     >     
> ==========================================================================
>     >     "The earth is but one country, and mankind its citizens."  --  
> Baha'u'llah
>     >
>     >
>    
>     --
>     Camm Maguire                                       address@hidden
>     ==========================================================================
>     "The earth is but one country, and mankind its citizens."  --  Baha'u'llah
>

-- 
Camm Maguire                                        address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah