Group Abstract

Message Boards

WOLFRAM COMMUNITY

31 Views

4 Replies

2 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Mathematics Equation Solving Wolfram Language Tuning and Debugging

How do we decrease the computation time of this code?

Bharath Krishnan

Bharath Krishnan, India East University

Posted 13 hours ago

I want to decrease the computation time of the following code. If `c` is a large constant, how do we show when: Clear["Global`*"] c=100 LengthS[r_] := LengthS[r] = {3(r-c)!, r!/2 + 1} LengthS1[r_, y_] := LengthS1[r, y] = LengthS[r][[y]] LengthS2[j_, y_] := LengthS2[j, y] = LengthS[j][[y]] V[r_]:=V[r]=r!+1 and: P1=200 Min11[r_, x_] := Min11[r, x] = FindInstance[LengthS1[r1, x] < V[r] && V[r] < LengthS1[r1 + 1, x] && r - P1 <= r1 && r1 <= r + P1, {r1}, PositiveIntegers] Min12[r_, x_] := Min12[r, x] = ArgMin[{RealAbs[LengthS1[r2, x] - V[r]], r - P1 <= r2 <= r + P1}, r2, PositiveIntegers] Min21[r_, y_] := Min21[r, y] = FindInstance[LengthS2[r3, y] < V[r] && V[r] < LengthS2[r3 + 1, y] && r - P1 <= r3 && r3 <= r + P1, {r3}, PositiveIntegers] Min22[r_, y_] := Min22[r, y] = ArgMin[{RealAbs[LengthS2[r4, y] - V[r]], r - P1 <= r4 <= r + P1}, r4, PositiveIntegers] then `rMin1[r,1]==r+c` and `rMin2[r,2]==r` (e.g., `rMin1[r,1]==10+c` and `rMin2[r,2]==10`). rMin1[r_, x_] := rMin1[r, x] = Min12[r, x] + Sign[Floor[RealAbs[2 r - Min11[r, x] - Min12[r, x]]/2]] rMin2[r_, y_] := rMin2[r, y] = Min22[r, y] + Sign[Floor[RealAbs[2 r - Min21[r, y] - Min22[r, y]]/2]] rMin1[10,1] rMin1[10,2] However, it takes too long to compute `rMin1[10,1]` and `rMin2[10,2]` and I do not know what are the actual outputs.

I want to decrease the computation time of the following code.

If c is a large constant, how do we show when:

Clear["Global`*"]

c=100

LengthS[r_] := LengthS[r] = {3(r-c)!, r!/2 + 1}

LengthS1[r_, y_] := LengthS1[r, y] = LengthS[r][[y]]

LengthS2[j_, y_] := LengthS2[j, y] = LengthS[j][[y]]

V[r_]:=V[r]=r!+1

and:

P1=200    

Min11[r_, x_] := 
 Min11[r, x] = 
  FindInstance[LengthS1[r1, x] < V[r] && V[r] < LengthS1[r1 + 1, x] && 
    r - P1 <= r1 && r1 <= r + P1, {r1}, PositiveIntegers]

Min12[r_, x_] := 
 Min12[r, x] = 
  ArgMin[{RealAbs[LengthS1[r2, x] - V[r]], r - P1 <= r2 <= r + P1}, 
   r2, PositiveIntegers]

Min21[r_, y_] := 
 Min21[r, y] = 
  FindInstance[LengthS2[r3, y] < V[r] && V[r] < LengthS2[r3 + 1, y] && 
    r - P1 <= r3 && r3 <= r + P1, {r3}, PositiveIntegers]

Min22[r_, y_] := 
 Min22[r, y] = 
  ArgMin[{RealAbs[LengthS2[r4, y] - V[r]], r - P1 <= r4 <= r + P1}, 
   r4, PositiveIntegers]

then rMin1[r,1]==r+c and rMin2[r,2]==r (e.g., rMin1[r,1]==10+c and rMin2[r,2]==10).

rMin1[r_, x_] := 
 rMin1[r, x] = 
  Min12[r, x] + Sign[Floor[RealAbs[2 r - Min11[r, x] - Min12[r, x]]/2]]

rMin2[r_, y_] := 
 rMin2[r, y] = 
  Min22[r, y] + Sign[Floor[RealAbs[2 r - Min21[r, y] - Min22[r, y]]/2]]

rMin1[10,1]
rMin1[10,2]

However, it takes too long to compute rMin1[10,1] and rMin2[10,2] and I do not know what are the actual outputs.

POSTED BY: Bharath Krishnan

4 Replies

Sort By:

David Trimas

David Trimas, University of Michigan

Posted 6 hours ago

The nice thing here is both `LengthS` and `V` are bijective for positive integer `r`, so the inverses are well-defined and we can just find `r1` using `FindRoot`. So we could write `Min11[r,x]` as: Min11[r_, x_] := r1 /. FindRoot[V[r] == LengthS1[r1, x], {r1, c + 1, c, r + P1}] // Floor//Quiet `Min12[r,x]` is either `Min11[r,x]` or `Min11[r,x] + 1`, whichever one is closer to `V[x]` and within the bounds: Min12[r_, x_] := Module[{r1, cands, closest}, r1 = Min11[r, x]; cands = r1 + {0, 1}; closest = MinimalBy[cands, Abs[LengthS[#, x] - V[r]] &] // First; Min[closest, r + P1] ] And with your definition of `rMin1` we get the expected behavior: rMin1[r_, x_] := Min12[r, x] + Sign[Floor[RealAbs[2 r - Min11[r, x] - Min12[r, x]]/2]] Table[ rMin1[r, 1] == c + r, {r, 10}] ({True, True, True, True, True, True, True, True, True, True}) You can do the same thing for `rMin2`. You may notice that I used `Quiet` to supress `FindRoot::lstol` messages, but it converges well enough (we only need to get a width 1 window for the root) despite the warning messages generated. If you are concerned about this however, you can also do a simple binary search since you start with a lower and upper bound on `r1`, and the constraint functions are monotonic.