Re: VM machine: A CAS answer 25,000,000+ times longer than it is

Robert H. Lewis <rlewis@xxxxxxxxxxx> wrote:
....
Let me mention that you VM machine probably has two
limitations.
First, it seems that you do "black box" testing, so
VM machine can not see source code of tested system.
That makes finding some bugs pretty hard. For example,
could VM machine find that there is something wrong with
gcd of 67108859*67108859*x^2-1 and
67108859*67108859*x^2+2*67108859*x +1
Note: the magic number here is 67108859 and you need to
arrange the two polynomials in specific way to
trigger the bug....

--
Waldek Hebisch

Is this just a hypothetical example, or are you saying there is a CAS that gets this wrong? The problem seems to be extremely simple, and should be done correctly by any CAS in a tiny fraction of a second. What is "magic" about 67108859?


There was a CAS: Axiom and derviatives prior to 2008 got this wrong.
Modulo 67108859 gcd is just 1. Axiom used modular computation
modulo 67108859 to quickly discover relatively prime polynomials.
However, Axiom missed check for divisibility of leading terms by
the modulus, so after modular check it claimed the the
polynomials are relatively prime.
There were other checks present which inhibit simpler examples.
The exact input to trigger bug is:

gcd([67108859*67108859*x^2-1, 67108859*67108859*x^2+2*67108859*x +1])

Fixed in FriCAS (and I think the fix is now in all derviatives).

The point is that unless you hit one of magic values there is
no hint of possible bug -- so either one has really huge test set
or one will miss it.

--
Waldek Hebisch
hebisch@xxxxxxxxxxxxxxxx
.

Relevant Pages

  • Re: whats it worth to write a short program for polynomial multiplication?
    ... specialized for the polynomial type in question. ... valid way to efficiently multiply two polynomials in ... It would be one way of trying to use the "most efficient" algorithm at ... Axiom Lead Developer ...
    (sci.math.symbolic)
  • Re: Floating-point arithmetic in CL
    ... If you believe in the axiom of choice, and in any of the usual ... An algebraic number is a root of a polynomial with rational ... There are only a countable number of polynomials ... with rational coefficients, and each of those polynomials has ...
    (comp.lang.lisp)
  • Re: whats it worth to write a short program for polynomial multiplication?
    ... Obviously, in an appropriate programming language, this ... matrices, elements in a finite field, strings, etc. ... information which describes the polynomials (sparse, univariate, ... There are 58 * operators in Axiom, many of which can by automatically ...
    (sci.math.symbolic)
  • Re: MACSYMA and AXIOM - the same failure pattern
    ... I would already be happy with bug reports. ... do you mean that the Axiom developers ... By the way, we badly need an integration expert, since Manuel Bronstein (who ...
    (sci.math.symbolic)