experiments with maxima



Greetings, Here are some experiments that may be interesting. The
code is at:
https://sourceforge.net/projects/ribot/files/

These are the same thing:
  maxima-expt.zip
  maxima-expt.tar.gz

This is a 3.2MB data file for one function
  prime_pi_tables.lisp

1) Documentation: Modified the command-line interface to the maxima
manual to allow other documents to be displayed with ? and ??  and to
allow other systems to make queries. The documentation system is
divided into three parts: a) databases.  b) querying and organizing
component. c) front ends.  Databases are registered with the querying
component by sending a struct. The original describe command line
interface calls the querying component. Not much was done here, just
separating the code. There are four examples of
databases:

 a) the maxima info database.

 b) simple-doc. This is available immediately. (I later saw this is
    similar to L. Butler's code.)

   (%i3) simple_doc_add("new_function", "The new description.");

   (%o3) "new_function"
   (%i4) ? new_function

      The new description.

   (%o4) true

 c) max-doc, a more capable documentation database than simple-doc,
  but not coherent.  It would be nice if there were a lisp parser of
  gnu texinfo code. The idea is to make it easy to convert
  to normal maxima doc.

 d) developer or internal documentation. Eg, there is a macro
    ddefun that expands to defun but also captures the doc
    string to a database along with the name of the source
    file, and lambda list. This is then also available via ? and ??.

 There is a variable controlling sending the output to a pager, as
 well, that only works with some lisp/platfrom combinations.

2) Options or keyword arguments to maxima functions: One
   could use a new infix notation, or just pass a form:
   func(x, a -> b) or  func(x, opt(a=b))
  I am using the former.

3) defmfun1 macro for writing maxima functions: (no support now for
   writing directly in maxima language). The syntax tries to follow
   defun as much as possible with &optional, &aux, &rest, with some
   additions.

  a) There is a new parameter type &opt rather than &key for the
     keyword args, mentioned above.

  b) Directives for argument checking and preprocessing of args.

  c) Automatic entry in the max-doc database. Actually, we require a
    directive :doc to create a documentation entry.

   An example:    (defmfun1 $f (x)  x).

   Another example (that still does not use &opt)

   (defmfun1 ($f4 :doc) ( (x :string) (y :non-neg-int) &optional (z :string "dog") )
   "f4 ignores the string and integer arguments and returns 'dog' by default."
    z)

    then ....

   (%i2) ? f4

    -- Function: f4: f4(<x>, <y> :optional <z>)
    Section: Example functions

    f4 ignores the string and integer arguments and returns 'dog' by default.
    f4 requires either two or three arguments.
     The first argument <x> must be a string.
     The second argument <y> must be a non-negative integer.
     The third argument <z> must be a string.

   (%i3) f4();

    f4: f4 called with no arguments; either two or three arguments are expected.

   (%i4) f4(1);

    f4: Argument '1' is not a string in f4(1).

   (%i5) f4("cat",1);

   (%o5) "dog"

   Some other examples of definitions:
   (defmfun1 $f8 (x  &rest (m :list) ) ...) ; Each of the &rest arguments must be a maxima list.
   (defmfun1 $f9 ( (x (:int-range 1 10) )) ...)  ; eg f9(5)
   (defmfun1 $f10 ( x &opt ($y (:int-range 1 3))) ; eg f10(1, y->2)

4) array representation of expressions. Instead of a list, represent an
   expression by a struct with a list for the op  and a lisp array for the
   arguments. This allows more efficient random access of elements in the
   expression. These cannot be used universally, of course.
   Some of the functions to manipulate them   are.
   a) aex(e), lex(e) shallow conversion between array and list representation.
   b) faex(e), flex(e), raex(e,i,j...) convert at all levels or levels given by
    a specification.
   c) e falls through aex(e) if e is a symbol, number, bigfloat, string, etc.
   d) ipart(e,...). Like inpart but expression can be mixed list and array representation
    at different levels. ipart_set(e,v,....) destructive assignment.
   Some other modifications are done, eg. the alike function understands array expressions.
   In general, the idea is to allow algorithms that are not efficient for singly-linked
   lists. What output representation to choose if none is specificied is problematic.

   Display of aex is badly hacked via msize at the moment. It looks slightly better in 5.25.1 than
   5.26.0 I don't understand the maxima display  code.

   Many functions take the option ot.  ot->ar means output array representation
    ot->ml means output lisp list representation.

5) A number of functions, mostly using the above. Eg.
  a) lrange (called lrange because 'range' is already taken)
     lrange(3) => [1,2,3]
     lrange(3,ot->ar)  => ~[1,2,3]  (ask for array representation output, marked by '~')
     lrange(x,x+4,2) => [x,x+2,x+4]

     For generating a single list large enough to measure the time, lrange is
     a few hundred times faster than the more general 'makelist', and about 3 times
     faster than  Z. Lenaric's, also more general, table.

Here is an example. defmfun-ae is a macro that
writes some array expression options into the lambda list. This example could
also be done simply by copying to a lisp array.

 (defmfun-ae $ae_random_permutation (a)
   "Return expression a with random permutation of arguments."
   (let* ( (a1 ($aex_cp a))  ; shallow copy to array expression from list or array expression
           (n   ($length a1)) )
     (dotimes (i n)
       (let ( (j (+ i ($random (- n i))))
              (tmp    ($aex_get  a1 i)) )
         (declare (fixnum j))
         ($aex_set a1 i ($aex_get a1 j))  ;; these are pretty fast
         ($aex_set a1 j tmp)))
     (defmfun-final-to-ae a1)))  ;; convert to the representation specified in the call.

     ae_random_permutation([1,2,3]);   =>  ~[3,1,2]  (list input , array output)
     ae_random_permutation( aex( [1,2,3]) ); => ~[3,1,2] (array input and output)
     ae_random_permutation( aex( [1,2,3] ), ot->ml ); [1,2,3] (array input, list output)

     The following (compiled) is almost as fast on large lists of numbers (10^5 or 10^6)

   rand_perm(a) := block([a1,n,j,tmp],
     modedeclare([j,n],fixnum),
     a1 : aex_cp(a),
     n : length(a1),
      for i from 0 thru n-1 do (
       j : i + random(n-i),
       tmp : aex_get(a1,i),
       aex_set(a1,i,aex_get(a1,j)),
       aex_set(a1,j,tmp)),
    a1);


  6) cffi example: prime_pi prime counting function. The table is big
  so it is packaged separately.  This may not be easily buildable on
  some systems. I made an interface to a fast c++ prime sieve
  implementation (Walisch) and some tables (Oliveira).  The library is
  multithreaded. This works with sbcl and ccl on linux. The trial
  allegro system would not link the 64 bit library.  It is probably
  not difficult to get it work with MS Win, but I stopped when I got
  linking errors because mingw does not have openmp.  Also, poking
  around the web and the gcl source I could not find how to do ffi for
  gcl.  Example:

  The spacing of entries in the table for 10^12 is greater than 10^8 (Denser tables are available).
  So 10^8 values must be sieved:

 (%i28) prime_pi(10^12 + 10^8, threads->2);
  Evaluation took 0.0940 seconds (0.0940 elapsed) using 0 bytes.
 (%o28) 37611530300

  Here, 10^9 values sieved. Note real time is half the total processor time.

 (%i29) prime_pi(10^15 + 10^9, threads->2);
   Evaluation took 1.6610 seconds (0.8610 elapsed) using 0 bytes.
 (%o29) 29844599369090