#5695 fullratsimp(rat(sqrt(c-1)/(c-f(a))^(3/2)-1/(sqrt(c-1)*sqrt(c-f(a))))) loops forever

[David Scherfgen]

Discovered by Claude:

fullratsimp(rat(sqrt(c-1)/(c-f(a))^(3/2)-1/(sqrt(c-1)*sqrt(c-f(a)))));

This loops forever, cycling over two representations.

[David Scherfgen]

Fixed by commit [a05a6b].

[Barton Willis]

Nice that you fixed the actual bug here. Nevertheless, I think that the function fullratsimp should have protection against infinite loops. Something like:

(defmvar *max-fullratsimp-iterations* 32
  "Maximum number of iterations allowed for fullratsimp before falling back.")

(defmfun ($fullratsimp :properties ((evfun t))) (exp &rest argl)
  "Repeatedly applies `ratsimp` to an exp until either (a) a fixpoint is reached 
   (b) cycle is detected (A -> B -> C -> A -> ...), or (c) the number of iterations
   exceeds *max-fullratsimp-iterations*. For case 'a', the fixed point is returned; 
   for cases 'b' & 'c', the expression with the least conssize is returned.

   The optional arguments (`argl`) are passed along to each `ratsimp` call."
   (labels ((local-ratsimp (e) 
             (simplify (apply #'$ratsimp (cons e argl)))))
    (let ((seen (list exp))
          (current exp)
          (next (local-ratsimp exp))
          (k *max-fullratsimp-iterations*))
      (loop
        ;; Fixpoint reached (expression stopped changing)
        (when (alike1 current next)
          (return current))

        ;; Cycle detected (expression started repeating) or maximum number of iterations
        ;; exceeded--return expression with least conssize.
        (when (or (member next seen :test #'alike1) (< k 0))
           (return (reduce (lambda (a b) (if (< (conssize a) (conssize b)) a b))  seen)))
        (push next seen)
        (decf k)
        (setf current next
              next (local-ratsimp next))))))

[Barton Willis]

A better version:

(defmvar *max-fullratsimp-iterations* 32
  "Maximum number of iterations allowed for fullratsimp before falling back.")

(defmfun ($fullratsimp :properties ((evfun t))) (exp &rest argl)
  "Repeatedly applies `ratsimp` to `exp` until either (a) a fixpoint is reached,
   (b) a cycle is detected, or (c) the number of iterations exceeds 
   *max-fullratsimp-iterations*."
  (labels ((local-ratsimp (e)
             (simplify (apply #'$ratsimp e argl))))
    (let* ((k *max-fullratsimp-iterations*)
           (seen (list exp))
           (current exp)
           (next (local-ratsimp exp))
           (best exp)
           (min-size (conssize exp)))
      (loop
        ;; Track the minimum size on the fly
        (let ((sz (conssize next)))
          (when (< sz min-size)
            (setf min-size sz
                  best next)))

        ;; (a) Fixpoint reached
        (when (alike1 current next)
          (return next)) ; or current, they are alike

        ;; (b) Cycle detected or (c) Max iterations exceeded
        (when (or (member next seen :test #'alike1) (< k 0))
          (return best))

        (push next seen)
        (decf k)
        (setf current next
              next (local-ratsimp next))))))

[David Scherfgen]

Do we need an iteration limit if we detect cycles and abort then? I'd say no, intuitively.

[Barton Willis]

Most likely no. The iteration limit check is fast, but the cycle detection is slow. If we got rid of one check, maybe it should be the cycle detection?

[David Scherfgen]

Intuition about "fast" and "slow" in Maxima is often misleading, we'd have to measure. In the normal case, the new expression is not alike1 any previous, and I guess that alike1 aborts very quickly in the average case. I'll do some experiments soon.