unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
* bug#16999: calc crashes when computation limit is increased
@ 2014-03-12 18:30 Florian Beck
  2014-03-12 22:44 ` Jay Belanger
                   ` (2 more replies)
  0 siblings, 3 replies; 16+ messages in thread
From: Florian Beck @ 2014-03-12 18:30 UTC (permalink / raw)
  To: 16999

M-x calc
2n
0
kc

I.e. try to calculate the binomial coefficient of (-2 0). This doesn't
work and calc suggests you give it more time:

Computation got stuck or ran too long.  Type `M' to increase the limit

So do

M
kc

and repeat a couple of times.

Once `max-lisp-eval-depth' hits 64000 emacs crashes.

I can send a backtrace if necessary.


In GNU Emacs 24.3.50.46 (x86_64-unknown-linux-gnu, GTK+ Version 3.8.6)
  of 2014-03-12 on sophokles
Windowing system distributor `The X.Org Foundation', version 11.0.11405000
System Description:	Ubuntu 13.10

Configured using:
  `configure CC=gcc 'CFLAGS=-march=native -mtune=native -msse -msse2
  -msse3 -mmmx -O2 -pipe -g3 -fno-omit-frame-pointer -fno-crossjumping'
  LDFLAGS=-O2'


-- 
Florian Beck





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-12 18:30 bug#16999: calc crashes when computation limit is increased Florian Beck
@ 2014-03-12 22:44 ` Jay Belanger
  2014-03-13  5:13   ` Dmitry Antipov
  2020-09-09 12:19 ` Lars Ingebrigtsen
  2020-09-10 16:02 ` Mattias Engdegård
  2 siblings, 1 reply; 16+ messages in thread
From: Jay Belanger @ 2014-03-12 22:44 UTC (permalink / raw)
  To: Florian Beck; +Cc: 16999


> M-x calc
> 2n
> 0
> kc
>
> I.e. try to calculate the binomial coefficient of (-2 0).

This causes Calc to enter an infinite loop.  It needs to be fixed, but
the problem has been around for a while so it probably needs to wait
until after the release.

> Computation got stuck or ran too long.  Type `M' to increase the limit
>
> So do
>
> M
> kc
>
> and repeat a couple of times.
>
> Once `max-lisp-eval-depth' hits 64000 emacs crashes.

This seems to be an Emacs problem, rather than a problem specific to Calc.
Typing M doubles the sizes of `max-lisp-eval-depth' and
`max-specpdl-size'.  Having  `max-lisp-eval-depth' equal to 64000 by
itself doesn't seem to cause problems, but having `max-lisp-eval-depth'
equal to 64000 and `max-specpdl-size' equal to 83200 does cause Emacs to
crash on an infinite loop; evaluating:

  (setq max-specpdl-size 83200
        max-lisp-eval-depth 64000)

  (defun f ()
     (f))

  (f)

will crash Emacs.






^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-12 22:44 ` Jay Belanger
@ 2014-03-13  5:13   ` Dmitry Antipov
  2014-03-13  9:11     ` Dmitry Antipov
  2014-03-13 13:42     ` Stefan Monnier
  0 siblings, 2 replies; 16+ messages in thread
From: Dmitry Antipov @ 2014-03-13  5:13 UTC (permalink / raw)
  To: jay.p.belanger, Florian Beck; +Cc: 16999

On 03/13/2014 02:44 AM, Jay Belanger wrote:

> This seems to be an Emacs problem, rather than a problem specific to Calc.
> Typing M doubles the sizes of `max-lisp-eval-depth' and
> `max-specpdl-size'.  Having  `max-lisp-eval-depth' equal to 64000 by
> itself doesn't seem to cause problems, but having `max-lisp-eval-depth'
> equal to 64000 and `max-specpdl-size' equal to 83200 does cause Emacs to
> crash on an infinite loop; evaluating:
>
>    (setq max-specpdl-size 83200
>          max-lisp-eval-depth 64000)
>
>    (defun f ()
>       (f))
>
>    (f)
>
> will crash Emacs.

This is C stack overflow (try to attach gdb and do 'bt' on crash). On
*NIX system, 'ulimit -s' shows your current limit.

Perhaps there should be a kind of protection against this. For example,
eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).

Dmitry






^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13  5:13   ` Dmitry Antipov
@ 2014-03-13  9:11     ` Dmitry Antipov
  2014-03-13 14:06       ` Florian Beck
  2014-03-13 16:56       ` Eli Zaretskii
  2014-03-13 13:42     ` Stefan Monnier
  1 sibling, 2 replies; 16+ messages in thread
From: Dmitry Antipov @ 2014-03-13  9:11 UTC (permalink / raw)
  To: 16999; +Cc: Paul Eggert

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]

On 03/13/2014 09:13 AM, Dmitry Antipov wrote:

> Perhaps there should be a kind of protection against this. For example,
> eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).

This is rather simple on general *NIX. But:

1) it should be implemented for MS-Windows and OSX too if we really need this;
2) Linux has prlimit to tweak limits of another process at run time,
    so actual limit should be checked each time eval_sub is called, thus
    introducing a (minor?) slowdown.

Dmitry


[-- Attachment #2: error_if_c_stack_overflow.patch --]
[-- Type: text/x-patch, Size: 1566 bytes --]

=== modified file 'src/eval.c'
--- src/eval.c	2014-02-10 09:48:17 +0000
+++ src/eval.c	2014-03-13 08:59:39 +0000
@@ -33,6 +33,10 @@
 #include "xterm.h"
 #endif
 
+#ifdef HAVE_SYS_RESOURCE_H
+#include <sys/resource.h>
+#endif
+
 /* Chain of condition and catch handlers currently in effect.  */
 
 struct handler *handlerlist;
@@ -240,6 +244,13 @@
 
 static struct handler handlerlist_sentinel;
 
+/* C stack overflow protection.  */
+
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+/* Current C stack slimit.  */
+static struct rlimit stack_limit;
+#endif
+
 void
 init_eval (void)
 {
@@ -262,6 +273,10 @@
 #endif
   /* This is less than the initial value of num_nonmacro_input_events.  */
   when_entered_debugger = -1;
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  if (getrlimit (RLIMIT_STACK, &stack_limit))
+    emacs_abort ();
+#endif  
 }
 
 /* Unwind-protect function used by call_debugger.  */
@@ -2060,6 +2075,19 @@
   Lisp_Object funcar;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+  
   if (SYMBOLP (form))
     {
       /* Look up its binding in the lexical environment.


^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13  5:13   ` Dmitry Antipov
  2014-03-13  9:11     ` Dmitry Antipov
@ 2014-03-13 13:42     ` Stefan Monnier
  2014-03-13 14:12       ` Florian Beck
  1 sibling, 1 reply; 16+ messages in thread
From: Stefan Monnier @ 2014-03-13 13:42 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: Florian Beck, 16999

> Perhaps there should be a kind of protection against this.

There is, in the form of max-specpdl-size and max-lisp-eval-depth.
If you bump them up too high, you're asking for trouble.


        Stefan





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13  9:11     ` Dmitry Antipov
@ 2014-03-13 14:06       ` Florian Beck
  2014-03-13 14:30         ` Dmitry Antipov
  2014-03-13 16:56       ` Eli Zaretskii
  1 sibling, 1 reply; 16+ messages in thread
From: Florian Beck @ 2014-03-13 14:06 UTC (permalink / raw)
  To: Dmitry Antipov, 16999

On 13.03.2014 10:11, Dmitry Antipov wrote:
> On 03/13/2014 09:13 AM, Dmitry Antipov wrote:
>
>> Perhaps there should be a kind of protection against this. For example,
>> eval_sub can check current stack depth against getrlimit
>> (RLIMIT_STACK,...).

Sorry, this doesn't work for me. (I applied the patch and bootstrapped, 
but I still get the crash.)


-- 
Florian Beck





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13 13:42     ` Stefan Monnier
@ 2014-03-13 14:12       ` Florian Beck
  2014-03-13 21:15         ` Jay Belanger
  2014-03-13 22:10         ` Stefan Monnier
  0 siblings, 2 replies; 16+ messages in thread
From: Florian Beck @ 2014-03-13 14:12 UTC (permalink / raw)
  To: Stefan Monnier, Dmitry Antipov; +Cc: 16999

On 13.03.2014 14:42, Stefan Monnier wrote:
>> Perhaps there should be a kind of protection against this.
>
> There is, in the form of max-specpdl-size and max-lisp-eval-depth.
> If you bump them up too high, you're asking for trouble.

Maybe calc shouldn't bump them too high, then.

Would I start calc, repetedly press "M" and then crash emacs – well, 
maybe I was asking for trouble. But I pressed M as suggested, then 
checked to docs, then again pressed M as suggested, then did something 
else, returned to calc, pressed M again as suggested, and so on...
-- 
Florian Beck





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13 14:06       ` Florian Beck
@ 2014-03-13 14:30         ` Dmitry Antipov
  0 siblings, 0 replies; 16+ messages in thread
From: Dmitry Antipov @ 2014-03-13 14:30 UTC (permalink / raw)
  To: Florian Beck; +Cc: 16999

[-- Attachment #1: Type: text/plain, Size: 212 bytes --]

On 03/13/2014 06:06 PM, Florian Beck wrote:

> Sorry, this doesn't work for me. (I applied the patch and bootstrapped, but I still get the crash.)

Oops, the guard should be installed in Ffuncall too...

Dmitry


[-- Attachment #2: error_if_c_stack_overflow_fixed.patch --]
[-- Type: text/x-patch, Size: 2168 bytes --]

=== modified file 'src/eval.c'
--- src/eval.c	2014-02-10 09:48:17 +0000
+++ src/eval.c	2014-03-13 14:27:14 +0000
@@ -33,6 +33,10 @@
 #include "xterm.h"
 #endif
 
+#ifdef HAVE_SYS_RESOURCE_H
+#include <sys/resource.h>
+#endif
+
 /* Chain of condition and catch handlers currently in effect.  */
 
 struct handler *handlerlist;
@@ -240,6 +244,13 @@
 
 static struct handler handlerlist_sentinel;
 
+/* C stack overflow protection.  */
+
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+/* Current C stack slimit.  */
+static struct rlimit stack_limit;
+#endif
+
 void
 init_eval (void)
 {
@@ -262,6 +273,10 @@
 #endif
   /* This is less than the initial value of num_nonmacro_input_events.  */
   when_entered_debugger = -1;
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  if (getrlimit (RLIMIT_STACK, &stack_limit))
+    emacs_abort ();
+#endif  
 }
 
 /* Unwind-protect function used by call_debugger.  */
@@ -2060,6 +2075,19 @@
   Lisp_Object funcar;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+  
   if (SYMBOLP (form))
     {
       /* Look up its binding in the lexical environment.
@@ -2749,6 +2777,19 @@
   register Lisp_Object *internal_args;
   ptrdiff_t i;
 
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  ptrdiff_t stack_size;
+  char stack_top_variable;
+  const ptrdiff_t stack_extra = 128 * 1024;
+
+  if (&stack_top_variable < stack_bottom)
+    stack_size = stack_bottom - &stack_top_variable;
+  else
+    stack_size = &stack_top_variable - stack_bottom;
+  if (stack_size + stack_extra > stack_limit.rlim_cur)
+    error ("Attempt to overflow C stack");
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+
   QUIT;
 
   if (++lisp_eval_depth > max_lisp_eval_depth)


^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13  9:11     ` Dmitry Antipov
  2014-03-13 14:06       ` Florian Beck
@ 2014-03-13 16:56       ` Eli Zaretskii
  1 sibling, 0 replies; 16+ messages in thread
From: Eli Zaretskii @ 2014-03-13 16:56 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: eggert, 16999

> Date: Thu, 13 Mar 2014 13:11:50 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Paul Eggert <eggert@cs.ucla.edu>, Eli Zaretskii <eliz@gnu.org>
> 
> On 03/13/2014 09:13 AM, Dmitry Antipov wrote:
> 
> > Perhaps there should be a kind of protection against this. For example,
> > eval_sub can check current stack depth against getrlimit (RLIMIT_STACK,...).
> 
> This is rather simple on general *NIX. But:
> 
> 1) it should be implemented for MS-Windows and OSX too if we really need this;

It should be easy enough to emulate on MS-Windows getrlimit that
supports RLIMIT_STACK.  Let me know if you want me to do that (should
ideally be ready before it is used, to avoid breaking the build).

> 2) Linux has prlimit to tweak limits of another process at run time,
>     so actual limit should be checked each time eval_sub is called, thus
>     introducing a (minor?) slowdown.

I'm not sure we should bother.  We already use getrlimit/setrlimit for
making sure the stack is large enough to accommodate re_max_failures.
We do that only once, at startup, and never look back.  And yet I
don't think we've seen regexp related crashes that would point to
stack overflow.





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13 14:12       ` Florian Beck
@ 2014-03-13 21:15         ` Jay Belanger
  2014-03-13 22:10         ` Stefan Monnier
  1 sibling, 0 replies; 16+ messages in thread
From: Jay Belanger @ 2014-03-13 21:15 UTC (permalink / raw)
  To: Florian Beck; +Cc: Dmitry Antipov, 16999


>> There is, in the form of max-specpdl-size and max-lisp-eval-depth.
>> If you bump them up too high, you're asking for trouble.
>
> Maybe calc shouldn't bump them too high, then.

The Elisp manual has a warning about bumping them too high; perhaps the
Calc manual should have one also.  But this seems more like an Emacs
issue than specifically a Calc issue, so any other fixes should probably
take place out of Calc.

Dmitry has started a separate discussion on handling this issue; good
deal. 

> Would I start calc, repetedly press "M" and then crash emacs – well,
> maybe I was asking for trouble.

The main culprit here is the infinite loop itself, which needs to be
fixed.  Without that, you wouldn't have had any problems.





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-13 14:12       ` Florian Beck
  2014-03-13 21:15         ` Jay Belanger
@ 2014-03-13 22:10         ` Stefan Monnier
  1 sibling, 0 replies; 16+ messages in thread
From: Stefan Monnier @ 2014-03-13 22:10 UTC (permalink / raw)
  To: Florian Beck; +Cc: Dmitry Antipov, 16999

> Maybe calc shouldn't bump them too high, then.

Indeed, it shouldn't.


        Stefan





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-12 18:30 bug#16999: calc crashes when computation limit is increased Florian Beck
  2014-03-12 22:44 ` Jay Belanger
@ 2020-09-09 12:19 ` Lars Ingebrigtsen
  2020-09-10 16:02 ` Mattias Engdegård
  2 siblings, 0 replies; 16+ messages in thread
From: Lars Ingebrigtsen @ 2020-09-09 12:19 UTC (permalink / raw)
  To: Florian Beck; +Cc: 16999

Florian Beck <fb@miszellen.de> writes:

> M-x calc
> 2n
> 0
> kc
>
> I.e. try to calculate the binomial coefficient of (-2 0). This doesn't
> work and calc suggests you give it more time:
>
> Computation got stuck or ran too long.  Type `M' to increase the limit
>
> So do
>
> M
> kc
>
> and repeat a couple of times.
>
> Once `max-lisp-eval-depth' hits 64000 emacs crashes.

It seems like this problem has been fixed by the general C stack
protection.  Trying this in Emacs 28 I just get:

  Re-entering top level after C stack overflow

So I'm closing this bug report.  If this is still a problem, please
respond to the debbugs address and we'll reopen.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2014-03-12 18:30 bug#16999: calc crashes when computation limit is increased Florian Beck
  2014-03-12 22:44 ` Jay Belanger
  2020-09-09 12:19 ` Lars Ingebrigtsen
@ 2020-09-10 16:02 ` Mattias Engdegård
  2020-09-11 10:29   ` Mattias Engdegård
  2020-09-11 11:54   ` Lars Ingebrigtsen
  2 siblings, 2 replies; 16+ messages in thread
From: Mattias Engdegård @ 2020-09-10 16:02 UTC (permalink / raw)
  To: Lars Ingebrigtsen; +Cc: Florian Beck, 16999

reopen 16999
make it so

While the C-level crash has been fixed, the Calc bug (infinite loop) has not.

Whether to signal a domain error for (-2 choose 0) or return the conventional value by extension is a matter of taste; I think the latter would be more useful. In fact, I see no reason not to extend the function to all integral arguments, but would of course value any half-supported opinion on the matter.

Let me attempt a patch, and please forgive my reopening the bug.






^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2020-09-10 16:02 ` Mattias Engdegård
@ 2020-09-11 10:29   ` Mattias Engdegård
  2020-09-11 11:54   ` Lars Ingebrigtsen
  1 sibling, 0 replies; 16+ messages in thread
From: Mattias Engdegård @ 2020-09-11 10:29 UTC (permalink / raw)
  To: Lars Ingebrigtsen; +Cc: 16999

[-- Attachment #1: Type: text/plain, Size: 999 bytes --]

10 sep. 2020 kl. 18.02 skrev Mattias Engdegård <mattiase@acm.org>:

> Let me attempt a patch, and please forgive my reopening the bug.

Here is that patch. Sadly mail to Florian Beck's address bounced but perhaps someone else will see the proposal and subject it to scrutiny. In short:

1. A sign mistake in the original code caused the infinite recursion. Fixed.
2. Some parts of the computation used tail recursion, which limited their applicability in elisp. Changed to use an imperative loop (alas).
3. The binomial coefficients have now been extended for all integral arguments, using definitions from [1]; see also [2] and [3].

[1] M. J. Kronenburg; The Binomial Coefficient for Negative Arguments; https://arxiv.org/abs/1105.3689
[2] D. Loeb, E. Damiani and O. D’Antona; Getting Results with Negative Thinking; https://arxiv.org/abs/math/9502214
[3] David Fowler; The Binomial Coefficient Function; The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17


[-- Attachment #2: 0001-Calc-fix-binomial-coefficients-for-negative-argument.patch --]
[-- Type: application/octet-stream, Size: 6320 bytes --]

From c451146726adfacdec69247c3da6dc4ebacd1b97 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Fri, 11 Sep 2020 11:43:15 +0200
Subject: [PATCH] Calc: fix binomial coefficients for negative arguments
 (bug#16999)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

For some values outside integers 0≤k≤n, (n choose k) gave wrong
results, entered infinite recursion or used unreasonably amounts of
stack space.  This change fixes that and extends the function to all
integer arguments using the definitions from M. J. Kronenburg
(https://arxiv.org/abs/1105.3689).

* lisp/calc/calc-comb.el (calcFunc-choose):
Fix sign error to prevent infinite recursion and extend function to
handle all integer arguments.
(math-choose-iter, math-choose-float-iter): Rewrite in iterative form;
no TCO in elisp yet.
* test/lisp/calc/calc-tests.el (calc-tests--fac, calc-tests--choose)
(calc-tests--check-choose, calc-tests--explain-choose)
(calc-tests--calc-to-number): New helper functions.
(calc-choose): New test.
---
 lisp/calc/calc-comb.el       | 42 +++++++++++++++-------
 test/lisp/calc/calc-tests.el | 67 ++++++++++++++++++++++++++++++++++++
 2 files changed, 96 insertions(+), 13 deletions(-)

diff --git a/lisp/calc/calc-comb.el b/lisp/calc/calc-comb.el
index c5d4d0837e..ce676d17a9 100644
--- a/lisp/calc/calc-comb.el
+++ b/lisp/calc/calc-comb.el
@@ -445,12 +445,25 @@ calcFunc-choose
 	   (math-div (calcFunc-fact (math-float n))
 		     (math-mul (calcFunc-fact m)
 			       (calcFunc-fact (math-sub n m))))))
-	((math-negp m) 0)
-	((math-negp n)
-	 (let ((val (calcFunc-choose (math-add (math-add n m) -1) m)))
+        ;; For the extension to negative integer arguments we follow
+        ;; M. J. Kronenburg, The Binomial Coefficient for Negative Arguments,
+        ;; arXiv:1105.3689v2
+        ((and (math-negp n) (not (math-negp m)))
+         ;; n<0≤m: (n choose m) = (-1)^m (-n+m-1 choose m)
+	 (let ((val (calcFunc-choose (math-add (math-sub m n) -1) m)))
 	   (if (math-evenp (math-trunc m))
 	       val
 	     (math-neg val))))
+        ((and (math-negp n) (math-num-integerp n))
+         (if (math-lessp n m)
+             0
+           ;; m≤n<0: (n choose m) = (-1)^(n-m) (-m-1 choose n-m)
+           (let ((val (calcFunc-choose (math-sub (math-neg m) 1)
+                                       (math-sub n m))))
+             (if (math-evenp (math-sub n m))
+                 val
+               (math-neg val)))))
+	((math-negp m) 0)
 	((and (math-num-integerp n)
 	      (Math-lessp n m))
 	 0)
@@ -467,20 +480,23 @@ calcFunc-choose
 	       (math-choose-float-iter tm n 1 1)))))))
 
 (defun math-choose-iter (m n i c)
-  (if (and (= (% i 5) 1) (> i 5))
+  (while (<= i m)
+    (when (and (= (% i 5) 1) (> i 5))
       (math-working (format "choose(%d)" (1- i)) c))
-  (if (<= i m)
-      (math-choose-iter m (1- n) (1+ i)
-			(math-quotient (math-mul c n) i))
-    c))
+    (setq c (math-quotient (math-mul c n) i))
+    (setq n (1- n))
+    (setq i (1+ i)))
+  c)
 
 (defun math-choose-float-iter (count n i c)
-  (if (= (% i 5) 1)
+  (while (> count 0)
+    (when (= (% i 5) 1)
       (math-working (format "choose(%d)" (1- i)) c))
-  (if (> count 0)
-      (math-choose-float-iter (1- count) (math-sub n 1) (1+ i)
-			      (math-div (math-mul c n) i))
-    c))
+    (setq c (math-div (math-mul c n) i))
+    (setq n (math-sub n 1))
+    (setq i (1+ i))
+    (setq count (1- count)))
+  c)
 
 
 ;;; Stirling numbers.
diff --git a/test/lisp/calc/calc-tests.el b/test/lisp/calc/calc-tests.el
index c8cb97a8bc..5030a55472 100644
--- a/test/lisp/calc/calc-tests.el
+++ b/test/lisp/calc/calc-tests.el
@@ -397,6 +397,73 @@ calc-sum-gcd
                     (var n var-n) -1 1))
                  8)))
 
+(defun calc-tests--fac (n)
+  (apply #'* (number-sequence 1 n)))
+
+(defun calc-tests--choose (n k)
+  "N choose K, reference implementation."
+  (cond
+   ((and (integerp n) (integerp k))
+    (if (<= 0 n)
+        (if (<= 0 k n)
+            (/ (calc-tests--fac n)
+               (* (calc-tests--fac k) (calc-tests--fac (- n k))))
+          0)    ; 0≤n<k
+      ;; n<0, n and k integers: use extension from M. J. Kronenburg
+      (cond
+       ((<= 0 k)
+        (* (expt -1 k)
+           (calc-tests--choose (+ (- n) k -1) k)))
+       ((<= k n)
+        (* (expt -1 (- n k))
+           (calc-tests--choose (+ (- k) -1) (- n k))))
+       (t  ; n<k<0
+        0))))
+   ((natnump k)
+    ;; Generalisation for any n, integral k≥0: use falling product
+    (/ (apply '* (number-sequence n (- n (1- k)) -1))
+       (calc-tests--fac k)))
+   (t (error "case not covered"))))
+
+(defun calc-tests--check-choose (n k)
+  (equal (calcFunc-choose n k)
+         (calc-tests--choose n k)))
+
+(defun calc-tests--explain-choose (n k)
+  (let ((got (calcFunc-choose n k))
+        (expected (calc-tests--choose n k)))
+    (format "(calcFunc-choose %d %d) => %S, expected %S" n k got expected)))
+
+(put 'calc-tests--check-choose 'ert-explainer 'calc-tests--explain-choose)
+
+(defun calc-tests--calc-to-number (x)
+  "Convert a Calc object to a Lisp number."
+  (pcase x
+    ((pred numberp) x)
+    (`(frac ,p ,q) (/ (float p) q))
+    (`(float ,m ,e) (* m (expt 10 e)))
+    (_ (error "calc object not converted: %S" x))))
+
+(ert-deftest calc-choose ()
+  "Test computation of binomial coefficients (bug#16999)."
+  ;; Integral arguments
+  (dolist (n (number-sequence -6 6))
+    (dolist (k (number-sequence -6 6))
+      (should (calc-tests--check-choose n k))))
+
+  ;; Fractional n, natural k
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac 15 2) 3))
+                 (calc-tests--choose 7.5 3)))
+
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac 1 2) 2))
+                 (calc-tests--choose 0.5 2)))
+
+  (should (equal (calc-tests--calc-to-number
+                  (calcFunc-choose '(frac -15 2) 3))
+                 (calc-tests--choose -7.5 3))))
+
 (provide 'calc-tests)
 ;;; calc-tests.el ends here
 
-- 
2.21.1 (Apple Git-122.3)


^ permalink raw reply related	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2020-09-10 16:02 ` Mattias Engdegård
  2020-09-11 10:29   ` Mattias Engdegård
@ 2020-09-11 11:54   ` Lars Ingebrigtsen
  2020-09-14  9:45     ` Mattias Engdegård
  1 sibling, 1 reply; 16+ messages in thread
From: Lars Ingebrigtsen @ 2020-09-11 11:54 UTC (permalink / raw)
  To: Mattias Engdegård; +Cc: Florian Beck, 16999

Mattias Engdegård <mattiase@acm.org> writes:

> While the C-level crash has been fixed, the Calc bug (infinite loop) has not.

Ah, sorry, I thought I had tested that bit too, but I must have done
something wrong...

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#16999: calc crashes when computation limit is increased
  2020-09-11 11:54   ` Lars Ingebrigtsen
@ 2020-09-14  9:45     ` Mattias Engdegård
  0 siblings, 0 replies; 16+ messages in thread
From: Mattias Engdegård @ 2020-09-14  9:45 UTC (permalink / raw)
  To: Lars Ingebrigtsen; +Cc: 16999-done

11 sep. 2020 kl. 13.54 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> Ah, sorry, I thought I had tested that bit too, but I must have done
> something wrong...

Well, you dug up an old bug and turned our attention to it, so in a sense you did bring about the resolution!

Patch pushed and bug closed (again).






^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2020-09-14  9:45 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-03-12 18:30 bug#16999: calc crashes when computation limit is increased Florian Beck
2014-03-12 22:44 ` Jay Belanger
2014-03-13  5:13   ` Dmitry Antipov
2014-03-13  9:11     ` Dmitry Antipov
2014-03-13 14:06       ` Florian Beck
2014-03-13 14:30         ` Dmitry Antipov
2014-03-13 16:56       ` Eli Zaretskii
2014-03-13 13:42     ` Stefan Monnier
2014-03-13 14:12       ` Florian Beck
2014-03-13 21:15         ` Jay Belanger
2014-03-13 22:10         ` Stefan Monnier
2020-09-09 12:19 ` Lars Ingebrigtsen
2020-09-10 16:02 ` Mattias Engdegård
2020-09-11 10:29   ` Mattias Engdegård
2020-09-11 11:54   ` Lars Ingebrigtsen
2020-09-14  9:45     ` Mattias Engdegård

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).