Re: what's it worth to write a short program for polynomial multiplication?

On Jun 2, 8:39 am, hru...@xxxxxxxxxxxxxxxxxxxx (Herman Rubin) wrote:
In article <570bb6f4-6c19-42f1-bc82-f6872d4f6...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,


Well, the next sentence in the abstract is...

What is the smallest expression in
a programming language for such a program? (Assuming that the language
does not have ``multiplication of polynomials'' as a primitive!)



HR:

Obviously, in an appropriate programming language, this
will be a basic operation, so the smallest expression
would be

z = x * y,

where the overloaded operator * does what is expected.

This is not really a solution unless the overloaded operator is a lot
smarter than we usually expect.
That is, "*" must not only look at the types of x and y [which are
presumably "polynomial"] but at other information, such as the domain
of the coefficients, which could be integers, floats, intervals,
matrices, elements in a finite field, strings, etc.
It might also look at the sizes, density, number of variables, and it
might look at the environment: how many processors are available, how
much memory, etc. It certainly should look at both x and y, and
perhaps also look at how z is described.

There is, I think, substantial evidence that the notion of object-
oriented choice of operator based on one operand, and in the typical
shallow way offered by most OO programming languages, is rather weak
for helping in determining the proper algorithm.

If there is exactly one algorithm for multiplying polynomials that
blindly pushes ahead oblivious to whether the inputs are (say) sparse
or dense, then you can be sure that the algorithm is going to be very
inefficient on certain inputs.

Few of the current programming languages come even
close to what is needed for good mathematics, and it
might be a good idea for mathematicians who can
understand the problems to put such languages together,

This was the motivation for several programs of study in computer
algebra systems, and resulted in several system designs, including
most notably, Axiom/ Aldor.

I have observed that mathematicians, as well as physicists, may not be
as good as they think they are in designing computer programming
languages.

.....


A good assembler program, in a good assembler language,
is less than twice the length of a HLL program which
does not have strong intermediate operation in it.
See the above smallest expression.

I'm not sure how one could judge this; but on simple size, I'm not so
convinced.
In the paper I indicated, one can represent sparse multivariate
polynomials as hash tables
whose indexes are lists of exponents of the different variables, and
whose entries are
the coefficients. Then producing a product hashtable can be done this
way:


(defun ptimes(r s)
(let ((ans (make-hash-table :test 'equal )))
(maphash #'(lambda(ex co) ; exponent, coefficient
(maphash #'(lambda (ex2 co2)
(incf (gethash (mapcar #'+ ex ex2) ans
0)
(* co co2))) r)) s)
ans))

This is 7 lines of Common Lisp, though since the language is free-
form, it could be printed all on one line :)
The result can be converted from a hashtable to a list in a few lines.

This is definitely not a recommended program for (say) dense,
univariate polynomials,
which might look more like this below, using a different data
representation of lists of coefficients.
This program accumulates the answer in an array, and then converts to
a list.


(defun ptimes (L1 L2)(array2list (ptimesA2 L1 L2)))

(defun ptimesA2(L1 L2)
(if (or (null L1)(null L2)) nil
(let ((ans (make-array (+ 1(cdar L1)(cdar L2)) :initial-element 0)))
(dolist (i L1 ans)
(dolist (j L2)
(incf (aref ans (+ (cdr i)(cdr j))) (* (car i)(car j))))))))

(defun array2list(A) ; 30x^10+5x^3 is ((30 . 10)(5 . 3))
(let ((ans nil))
(dotimes (i (length A) ans)
(unless (= 0 (aref A i)) (push (cons (aref A i)i) ans)))))

I don't pretend that these are totally obvious to the reader; they are
intended to be fairly ordinary common lisp, though. I invite versions
in (say) Python or other languages. Note that most common lisp
implementations allow you to add type declarations and compile to
pretty good machine language.You can also profile the program and then
decide if it is worthwhile to insert assembler somewhere.



.

Relevant Pages

  • Re: soc.culture.celtic FAQ
    ... The Celts ... Celtic language mailing lists ... How do I identify which Celtic language this is? ... The Irish Penitentials: Their Religious and Social ...
    (soc.culture.celtic)
  • Re: soc.culture.celtic FAQ
    ... The Celts ... Celtic language mailing lists ... How do I identify which Celtic language this is? ... The Irish Penitentials: Their Religious and Social ...
    (soc.culture.celtic)
  • Re: How come Ada isnt more popular?
    ... are praising is, because what about trees of strings, trees of lists etc. ... A language with a Hinldey-Milner type system ... container varies, the element does not. ...
    (comp.lang.ada)
  • Re: soc.culture.celtic FAQ
    ... This FAQ was first launched May 1994. ... The Celts ... Celtic language mailing lists ... How do I identify which Celtic language this is? ...
    (soc.culture.celtic)
  • Re: Ideal computer language from scratch?
    ... Takes 3 float as input, outputs 2 float, nicely formatted in bracktes ... subject and glancing over a volume on the language, ... zipWith takes a function and applies it to 2 lists, ... fibs and. ...
    (alt.lang.asm)