Carl Love

Carl Love

28025 Reputation

25 Badges

12 years, 313 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are answers submitted by Carl Love

I can't see exactly what is causing that error message without seeing your Phi---I can't duplicate the message---but try 

int~(Phi^%T*f, x= 0..1);

Note that ScalarMultiply is unnecessary: The operation is handled by ordinary `*` multiplication.

The tilde (~) after the int is needed to map the operation over a vector.

You could use mu[0,1] or mu[`01`] or mu[o1] or mu[O1].

Use readline to read the first line. Use ImportMatrix to read the rest. ImportMatrix has an option to skip the first n lines of the file.

My experience is that Grid operations do not work very well when the operation being replicated is trivial. In this case, the symbolic application of ln, the operation is utterly trivial, just an unevalated fuction call. My guess is that each step should take at least 1/10 second to use Grid.

Try adding the option linestyle= solid to the plot command.

f''(0) is what your last line of code prints. It's what you called X2.

Most random values are 12 digits. Try

eval(eqn1, y= rand());

You will almost certainly get a numeric overflow. I believe that testeq is somewhat naively doing this. The safer way would be to use &^ instead of ^. I believe that testeq is using modular arithmetic with a large random prime modulus, but it is not changing to the safer &^.

The above is just my speculation based on reading ?testeq.

You can avoid the cut-and-paste step: In file 1.mw, after the definition of aver, include the command

save aver "aver.mpl";

You can use any filename that you want in the quotes. Make sure that the command is executed; this won't work if the command is just sitting there unexecuted. In file 2.mw, use the command 

read "aver.mpl":

This part is the same as TomLeslie's Answer. (The parentheses in his read command are superfluous.) Indeed, the save command creates the plain text file for you.

 

int(ln(1+sqrt((m+1)/m)), m);
simplify(%, symbolic);
value(%);

While the question may seem silly as posed, it is not silly to count (either exactly or by estimate) the solutions. Generalizing, it is very interesting to count the integer lattice points in a bounded convex high-dimension polytope. For the above problem, there are about 14 billion solutions. The exact number is 13,971,037,148. I computed this with the code below in 20 minutes real time on an i7 with eight CPUs, using parallel processing.

It was quite tricky to make this code efficient. Amazingly, many of the fundamental functions for integer programming are not threadsafe: absceilfloorroundfrac. The function frem is threadsafe, but not evalhfable. That leaves only iremiquo, and trunc as safe to use. So, I had to write a replacement for ceil using these. My procedure Ceil below is called inside the most deeply nested loop. A very small tweak in its efficiency would have a large effect on the overall efficiency. Also, it would help if it could somehow be compiled.

It is amazing that the function ceil is still not threadsafe when used inside evalhf code! I verified this by trying it and getting the wrong count of solutions. How can that be? Isn't the evalhf code supposed to be using a separate copy of ceil that avoids all symbolics?

Another way to improve the efficiency would be to unroll the recursion so that evalhf could be applied at a higher level. Doing this by hand makes the code too ugly to be bearable. But perhaps the unrolling could be done automatically via some metaprogramming.

All comments welcome.


Counting the integer lattice points in a bounded convex high-dimension polytope

Author: Carl James Love

2015-May-21

 

In particular, we will count the positive integer solutions of a linear equation with positive integer coefficients.

 

restart:

The parameter C controls the right-hand side (the constant term) of the equation. C=1600 gives the original posted equation's constant term of 8000. If you want to experiment with this code, I recommend reducing C so that it doesn't take as much time to count all the solutions. The minimum feasible value of C is 200.
C:= 1600:

eq:= 30*a + 75*b + 110*c + 85*d + 255*e + 160*f + 15*g + 12*h + 120*i = 5*C;

30*a+75*b+110*c+85*d+255*e+160*f+15*g+12*h+120*i = 8000

Sol:= isolve(eq, {z||(1..8)});

{a = z1, b = z2, c = z3, d = z4, e = z5, f = 2+z3+2*z4+3*z6, g = 2*z1+3*z2+2*z3+z4+3*z5+4*z7, h = 640-5*z1-10*z2-25*z3-35*z4-25*z5-40*z6-5*z7-10*z8, i = z8}

Obviously, the minimum values of  z1, z2, z3, z3, z5, and z8 are all 1. These variables will be assigned values first. To get the minimum value of z6 (given that z1,...,z5,z8 are set), set f to 1. Note that the f equation is the only equation in which z6 occurs with a positive coefficient.

z6_min:= solve(1 = eval(f,Sol), z6);

-1/3-(1/3)*z3-(2/3)*z4

We will apply a ceiling function to that later so that we get an integer.

 

To get the minimum value of z7 (given that z1,...,z5, z8 and z6 are set), set g to 1. Note that the g equation is the only equation in which z7 appears with a positive coefficient.

z7_min:= solve(1 = eval(g,Sol), z7);

-(1/2)*z1-(3/4)*z2-(1/2)*z3-(1/4)*z4-(3/4)*z5+1/4

We will apply a ceiling function to the later so that we get an integer.

 

To get the maximum value of z7 (given that z1,....,z6, z8 are set), set h to 1. Note the h equation is the only equation in which z7 appears with a negative coefficient. Also note that all coefficients are divisible by -5, which is the z7 coefficient.

z7_max:= solve(1 = eval(h,Sol), z7);

639/5-z1-2*z2-5*z3-7*z4-5*z5-8*z6-2*z8

It is only the constant term that makes that non-integer. Use floor.

z7_max:= evalindets(z7_max, fraction, floor);

127-z1-2*z2-5*z3-7*z4-5*z5-8*z6-2*z8

Now I give some procedures for counting the solutions.


#Given values for z1, z2, z3, z4, z5, and z8, count all solutions
#for z6 and z7.

Sols_z6z7:= proc(z1, z2, z3, z4, z5, z8)
local z6, ct:= 0, z7s;
     for z6 from DUMMY_z6_min do
          z7s:= DUMMY_z7_max - DUMMY_z7_min + 1;             
          if z7s > 0 then  ct:= ct+z7s  else  return ct  end if        
     end do
end proc:

#Fill the DUMMYs.
Sols_z6z7:=
     subs([
          DUMMY_z6_min= 'Ceil'(numer(z6_min), denom(z6_min)),
          DUMMY_z7_min= 'Ceil'(numer(z7_min), denom(z7_min)),
          DUMMY_z7_max= z7_max #already integer
     ], eval(Sols_z6z7)  
     )
;

#Need to evaluate ceil(x/y) in a way that is both threadsafe and evalhfable.
#Ordinary ceil is not threadsafe!
Ceil:= proc(x,y)
local r:= irem(x,y), xy:= x/y;
     if r=0 then  xy
     elif xy < 0 then  trunc(xy)
     else  trunc(xy)+1
     end if
end proc:
          

proc (z1, z2, z3, z4, z5, z8) local z6, ct, z7s; ct := 0; for z6 from Ceil(-1-z3-2*z4, 3) do z7s := 128-z1-2*z2-5*z3-7*z4-5*z5-8*z6-2*z8-Ceil(-2*z1-3*z2-2*z3-z4-3*z5+1, 4); if 0 < z7s then ct := ct+z7s else return ct end if end do end proc

 

Note the very powerful metaprogramming accomplished by subs. The end result is a threadsafe and evalhfable procedure. The z variables in the substituted expressions become identified with the procedure parameters; they are no longer globals!


#For example, count all solutions for z1=z2=z3=z4=z5=z8=1:
evalhf(Sols_z6z7(1,1,1,1,1,1));

0.

The variables z1, ..., z5, and z8 can be filled by a simple recursive procedure.

SolsRecurse:= proc()
local z, z1, z2, z3, z4, z5, z8, ct, k;
     #nargs should never be > 6. I coded it this way so that
     #there'd be an error msg (rather than infinite recursion)
     #if the user accidentally enters more than 6 args.     
     if nargs >= 6 then
          (z1,z2,z3,z4,z5,z8):= args;
          trunc(evalhf(Sols_z6z7(z1,z2,z3,z4,z5,z8)))
     else
          ct:= 0;
          for z do
               k:= thisproc(args,z);
               if k > 0 then  ct:= ct+k  else  return ct  end if    
          end do
     end if
end proc:

#For example, count all solutions with z1=z2=z3=z4=1:
SolsRecurse(1,1,1,1);

141011

Now I could count all solutions by SolsRecurse(), but I want to use parallel processing.

#Find a close upper bound for z1 (or a).

solve(eq,a);

800/3-(5/2)*b-(11/3)*c-(17/6)*d-(17/2)*e-(16/3)*f-(1/2)*g-(2/5)*h-4*i

eval(%, indets(%,name)=~ 1);

3584/15

Max_z1:= floor(%);

238

(Note that that maximum will never be achieved. In particular, it is easy to see that the minimal value of h is at least 5, not 1. It doesn't matter: We just need a close upper bound, not an exact maximum.)

SolsParallel:= proc()
local z1;
     Threads:-Add[tasksize= 1](SolsRecurse(z1), z1= 1..Max_z1)
end proc:
     

The line below took 20 minutes of real time on an Intel i7 with eight CPUs. Its memory usage is insignificant on a moderm computer.

st:= time[real]():
SolsParallel();
time[real]() - st;

13971037148

1217.083


Download LatticeCount.mw

You need to take a few steps to complete this integration:

1. Don't use the same variable as both the integration variable and as a limit of integration. I changed your upper limit of integration from x to X.

2. Assume that X is in some interval. I chose [0,5] somewhat arbitrarily.

3. Use expand to factor the functions of t outside of the integral.

In the code below, I used notation for your integrand simply because it's less to type. You'll get the same answer if you use the diff notation that you had.

assume(X > 0, X < 5);
int(D[1,2](w)(x,t)^2 + D[1](w)(x,t)*D[1,2](w)(x,t), x= 0..X);
expand(%);

It is not a bug. Your pp has a root at cp=3220 for any value of x. You can see this by eval(pp, cp= 3220), which is identically 0. Because of floating point variation, Roots will find that root at slightly less than 3220 or exactly 3220 or slightly more than 3220. Often Roots will not find this root at all, because the curve becomes vertical (is not differentiable) at 3220. Because you asked for roots in the interval 1..3220, the root will be reported when it is less than or equal than 3220. Since you are not interested in seeing the root at 3220 on your graph, change the interval to 1..3219 and you will never see them.

Edit: Added sentence about Roots often not finding the root at 3220.

1. You seem to have some confusion as to what "leading coefficient" means. It means the coefficient of the term with the largest exponent on the main variable. What you are calling the leading coefficient is actually the "trailing coefficient."

2. Polynomials can be sorted into ascending or descending powers of their main variable with the sort command. For example:

sort(collect(expand(lhs(e4)),t), t, ascending);

3. You cannot control the order that items appear in a Maple set. If you use curly braces {}, it will be a set. If want to maintain an order, use square brackets [ ] to make it a list.

4. Why do you care about the order? Relying on a certain order is often (but not always) a sign of poor coding practice.

Use convert to convert to diff form and another convert to convert back to form. It can all be done in one line.

eq:= D[2](u)(x,t)= a^2*D[1,1](u)(x,t):
expr:= D[2,2](u)(x,t):
convert(eval[recurse](convert([expr, [eq]], diff)[]), D);

Your immediate problem is that you can't use a formal parameter, x, as the index of a for loop. I think that you meant for i to be the index.

There are other problems which don't produce syntax errors: By local top::0, you surely mean to initialize top to 0. That should be top:= 0. And by 

top =top+(((x^(2+i))*top)^(1/(n+2-i)))

you surely mean to update the value of top. So that should be 

top:= top+(x^(2+i)*top)^(1/(n+2-i))

Now the problem is that the above line can never change top from 0. So your formula is wrong, but I have no idea how to correct it because I don't recognize what this formula is supposed to do.

With all my corrections, the code becomes:

soru:= proc(n, x)
local i, top:= 0;
     for i from 2 to n do
          top:= top+(x^(2+i)*top)^(1/(n+2-i));
          print(top);
     od;
     top
end proc;

First 260 261 262 263 264 265 266 Last Page 262 of 395