1
$\begingroup$

In improving my code for this question over on Math, I seem to have run across a condition where TimeConstrained Abort[]s do not occur, but further computation is halted...

(* Cache entries are 
    {{remainder, next finger to try},{list of composites so far}}. *)
Remove[cListCache, cList];
cListCache[n_ /; And[n > 0, Element[n, Rationals]]] := {{n, 4}, {}};

(*  Attempt to express n as an Egyptian fraction with all denominators *)
(* composite.  Use no more than timeLimit seconds to start or continue *)
(* working (from cached state) on this expression.  Generate debug     *)
(* output if printDiags is True.  *)
cList[
  n_ /; And[n > 0, Element[n, Rationals]], 
  timeLimit_: 10, 
  printDiags_: False
] :=
  (* Use cached values if they are finished. *)
  If[cListCache[n][[1, 1]] === 0, 
    {0, cListCache[n][[2]]},

    Module[{
      c,  (* the accumulating list of composite denominators *)
      remainder,  (* n - Plus@@(1/c)  *)
      finger  (* run your finger through the positive composites  *)
    },
      {{remainder, finger}, c} = cListCache[n];

      cListCache[n] = TimeConstrained[

        (* Get the leading consecutive composites to build up close to n *)
        (* This should perhaps be cached and turned into a map, or some  *)
        (* other structure for quick searching. *)
        While[remainder finger > 1,
          AbortProtect[
            AppendTo[c, finger];
            remainder -= 1/finger;
            If[printDiags, Print[{finger, remainder}]];
            finger++;
            If[PrimeQ[finger], finger++]  (*  No consecutive primes above 4 *)
        ]
      ]; 

      (* Until we drive the remainder to zero, keep jumping finger to the  *)
      (* least composite large enough that its reciprocal is <= remainder. *)
      While[remainder > 0,
        AbortProtect[
          finger = Ceiling[1/remainder];
          If[PrimeQ[finger], finger++]; (*  No consecutive primes above 4 *)
          AppendTo[c, finger];
          remainder -= 1/finger;
          If[printDiags, Print[{finger, remainder}]];
        ]
      ];
      (* If we finish, cache a completed result. *)
      {{0, finger}, c}
    ,
      timeLimit,
      (* If we don't finish, cache an incomplete result. *)
      {{remainder, finger}, c}
    ]
    (* Whether finished or not, propagate the completed or incomplete *)
    (* result back out to the caller. *)
  ]
] /; And[timeLimit > 0, 
       Element[timeLimit, Reals], 
       Element[printDiags, Booleans]
     ]

N[cList[3, 10, True][[1, 1]]]
(* Much output.  On my hardware, last element of c has >166,000 digits.  *)
N[cList[3, 100, True][[1, 1]]]
(* Much output.  This completes and the last element of c has >665,000 *)
(* digits. *)

I'm running Mathematica 10.3.0.0 on Linux x64.

When the two cList[3,...] calls are enqueued to evaluate, the first never completes, even after tens of minutes, although it is TimeConstrained to give up after 10 seconds. One CPU core is running 100% until I kill the kernel. If the two instance of "AbortProtect" are changed to "Identity", the first call completes (in a few more than 10 seconds -- on my hardware, it seems to take noticeable time to do all the handling of the 166 kilodigit and/or 655 kilodigit last numbers in the list of composites).

The AbortProtect[]s are to ensure that the internal state variables are coherent (all updated together) when an Abort[] occurs so that cached state is coherent.

Questions:

  • Is it known/expected that AbortProtect[]ing the entire body of a While will prevent reception of Abort[]s (from TimeConstrained[])?
  • What is the right mental model for how AbortProtect[] interacts with looping constructs? (... if that model is different from the expectation the above code entails.)
  • What is the minimal change to the above code that will ensure the bodies of the Whiles are transactions and also will be Abort[]able from TimeConstrained[]?
  • Is there a less awful idiom for mixing default argument values and argument constraints? (Delocalizing constraints to the bottom of the function body is just ... not good.)
  • Other than possibly being overcautious about partial updates to the three state variables for an incomplete computation (for instance, I have not analyzed whether there is an order of updates that ensures that a subsequent continuation will produce valid output (even if it does a little redundant computation)), are there other significant improvements available?

Edit: The parallel kernel manager also thinks these calls are going into spinloops of some sort.

Select[
  ParallelMap[
    {#, Length[cList[#, 3][[2]]]} &, 
    randomRational[100, {0, 6}, 10^4]],  
    (* Imagine "Rationalize[#,10^-100]& /@ RandomReal[{0,6},10^4]]", but *)
    (* with more control over the distribution of denominators.          *)
  NumberQ[#[[2]]] &];
(*  LinkObject::linkd: Unable to communicate with closed link LinkObject["/usr/local/Wolfram/Mathematica/10.3/Executables/wolfram" -subkernel -noinit -wstp,529,8]. >>  *)
(*  Kernels::rdead: Subkernel connected through KernelObject[5,local] appears dead. >>  *)
(*  Parallel`Developer`QueueRun::req: Requeueing evaluations {36} assigned to KernelObject[5,local,<defunct>].  *)
(*  LaunchKernels::clone: Kernel KernelObject[5,local,<defunct>] resurrected as KernelObject[7,local]. >>  *)
(* ... occasionally with new duplicates of the block of diagnostics above. *)
$\endgroup$
1

1 Answer 1

1
$\begingroup$

Looking a bit more at this, I think it is the expected behavior. TimeConstrained in effect sets an alarm clock, and it happens to ring when deep inside a time-consuming evaluation that is itself inside the AbortProtect. Once it emerges from that the Abort generated by TimeConstrained can and will proceed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.