Items tagged with algorithm algorithm Tagged Items Feed

I am trying to understand how maple "isprime" algorithm works. But I can't find anywhere what special_primes means.

 

 showstat(isprime);

isprime := proc(n)
local btor, nr, p, r;
   1   if not type(n,'integer') then
   2     if type(n,('complex')('numeric')) then
   3       error "argument must be an integer"
         else
   4       return 'isprime(n)'
         end if
       end if;
   5   if n < 2 then
   6     return false
       elif member(n,isprime:-special_primes) then
   7     return true
       elif igcd(2305567963945518424753102147331756070,n) <> 1 then
   8     return false
       elif n < 10201 then
   9     return true
       elif igcd(8496969489233418110532339909187349965926062586648932736611545426342203893270769390909069477309509137509786917118668028861499333825097682386722983737962963066757674131126736578936440788157186969893730633113066478620448624949257324022627395437363639038752608166758661255956834630697220447512298848222228550062683786342519960225996301315945644470064720696621750477244528915927867113,n) <> 1 then
  10     return false
       elif n < 1018081 then
  11     return true
       else
  12     r := gmp_isprime(n);
  13     if not r or n <= 5000000000 then
  14       return r
         end if;
  15     nr := igcd(408410100000,n-1);
  16     nr := igcd(nr^5,n-1);
  17     r := iquo(n-1,nr);
  18     btor := modp(('power')(2,r),n);
  19     if cyclotest(n,btor,2,r) = false or irem(nr,3) = 0 and cyclotest(n,btor,3,r) = false or irem(nr,5) = 0 and cyclotest(n,btor,5,r) = false or irem(nr,7) = 0 and cyclotest(n,btor,7,r) = false then
  20       return false
         end if;
  21     if isqrt(n)^2 = n then
  22       return false
         end if;
  23     for p from 3 while numtheory:-jacobi(p^2-4,n) <> -1 do
  24       NULL
         end do;
  25     return evalb(TraceModQF(p,n+1,n) = [2, p])
       end if
end proc

I would like to pay attention to an article by David Austin "The Stable Marriage Problem and School Choice"

Here is its inroduction:

" Every year, 75,000 New York City eighth graders apply for admission to one of the city's 426 public high schools. Until recently, this process asked students to list five schools in order of preference. These lists were sent to the schools, who decided which applicants to accept, wait-list, or reject. The students were then notified of their status and allowed to accept only one offer and one position on a waiting list. After the students had responded to any offers received, schools with unfilled positions made a second round of offers, and this process continued through a concluding third round.

This process had several serious problems. At the end of the third round of offers, nearly half of the students, usually lower-performing students from poor families, had not been accepted into a school. Many of these students waited through the summer only to learn they had been matched with a school that was not on their list of five schools.

This process also encouraged students and their parents to think strategically about the list of schools they submitted. Students that were rejected by the school at the top of their list might find that their second-choice school had no vacancies in the second round of offers. This made it risky for many students to faithfully state their true preferences, a view encouraged by the Education Department's advice that students "determine what your competition is" before creating their lists of preferred schools.

Lastly, schools would often underrepresent their capacity hoping to save positions for students who were unhappy with their initial offerings.

In the end, the process couldn't place many students while it encouraged all parties, both students and schools, to strategically misrepresent themselves in an effort to obtain more desirable outcomes not possible otherwise. Widespread mistrust in the placement process was a natural consequence.

Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.

The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences.

This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work"

It would be nice to realize that in Maple.

 

 

Hello,

I have a question. I have to compare the times and steps taken by an algorithmus (which contents a loop).

So for time there is the time()-function, right? And is there any similar function for the steps taken?

So far i use a variable increasing by 1 each time, but i think there is an more elegant way to do it, which I just don't know.. :D

 

Thanks for any help!

 

I need to write a procedure that does the following :

Write a procedure quadsum whose input is an integer n and whose output is a list of pairs of solutions [x,y] to the above formula.

Your procedure should implement the following algorithm.

1 Initialization
Set
"mylist = []."

Start at
x = 0
and
y = 0.

2 Phase A
Increment both
x
and
y
until
"x^2+y^2 >=n."

Phase B
Repeat the following until
x^2>n

If you are above the circle
x^2 + y^2 = n
then go down in unit steps until you are on or below the circle.

If you are on the circle, add the point to the list
"mylist. "

If you are on or below the circle
x^2 + y^2 = n
then go one step to the right. My procedure is as follows: but it runs into an infinite loop(most probably because of the while loop defined inside the while loop). What am I doing incorrectly?

I have atta

 

Hi there,

I'm trying to simulate an stochastic SIR model following the Gillespie algorithm, as described here [1].

 

When trying to update each process' probabilities, it looks like Maple is not updating their values. Although each element of the lists S, I and R is updated the ai lists are not updated.

For example, for a given index i

a2[i]:= m*S[i]:

takes the same value for every i, regardless of the value of S[i].

Can anybody tell why this is happening or what's wrong with the worksheet? This is the attempt: MaplePrimes_SIR_model_simulation_Gillespie_algorithm.mw

 

On the other hand, I tried making things more clear through a couple of procedures. However, when it comes to the point where a random number with an exponential distirbution is computed:

Rexp := RandomVariable(Exponential(mu)):

it looks like Maple is unable to evaluate mu. But having a look at the Variables explorer, it has a defined value, indeed.

So what's wrong in the worksheet? Thi is the attempt: MaplePrimes_SIR_model_simulation_Gillespie_algorithm.mw

 

Thanks,

jon

[1] http://www.biosym.uzh.ch/modules/models/ETHZ/StochasticSimulation/sir_stoch.xhtml

Currently calculations: equations, regression analysis, differential equations, etc; to mention a few of them; are developed using traditional methods ie even are proposed and solved by hand and on paper. In teaching our scientists and engineers use the chalkboard as a way to reach students and enable them to solve their calculation. To what extent Maple contributes to research on new mathematical models applied science and engineering ?. Maplesoft appears as a proposal to resolve problems with our traditional proposed intelligent algorithms, development process, embedded components, and not only them but also generates type applications for Apple ipad tablets signature. Based on the computer algebra system Maple Maplesoft gives us the package which works exactly like we were on our work. I will show how mathematics is developed from a purely basic to reach modeling differential equations applied to education and engineering. Also visualizare current techniques for developing applications for mobile devices.

link: https://www.youtube.com/watch?v=FdRUSgfPBoc

 

ECI_2015.pdf

Atte.

Lenin Araujo Castillo

Physics Pure

Computer Science

Dear Maple Experts,

i am new to maple and I am trying to write a maple algorithm in order to calculate the GCD of two functions. 

I have defined the two functions and written the algorithm, but I get an error "Unable to Parse".

Here is my code:

restart; with(Algebraic); with(LinearAlgebra[Generic]); with(RegularChains); with(FastArithmeticTools); with(ChainTools); interface(rtablesize = 15);

f := (y^2-1)*((y+1)*x^4+(y^2-1)*x^3+(y^3-1)*x^2+(y^4-1)*x+y^5-1);

g := (y-1)*x^5+(y^2-1)*x^4+(y^3-1)*x^3+(y^4-1)*x^2+(y^5-1)*x+y^6-1;

SubRes:=proc(f,g,var): local  i,a, delta, beta, psi: if degree(f,var)<degree(g,var) then a[0]:=Algebraic:-PrimitivePart(g,var): a[1]:=Algebraic:-PrimitivePart(f,var): else a[0]=Algebraic:-PrimitivePart(f,var): a[1]:=Algebraic:-PrimitivePart(g,var): fi: delta[0]:=degree(a[0],var)-degree(a[1],var): beta[2]:=(-1)^((delta[0]+1)): psi[2]:=-1: i:=1: while a[i]<>0 do a[i+1]:=(prem(a[i-1], a[i], var))/(beta[i+1]): delta[i]:=degree(a[i],var)-degree(a[i+1], var): i:=i+1: psi[i+1]:=((-lcoeff(a[i-1],var))^((delta[i-2])))*((psi[i])^((1-delta[i-2]))): beta[i+1]:=-lcoeff(a[i-1],var)*(psi[i+1])^((delta[i-1])): od: print("Last Non-Zero Subresultant: ", sort(simplify(a[i-1])),y): return (Algebraic:-PrimitivePart(a[i-1],var)): end proc

and I get this error:

Error, unable to parse

Would you kindly help me to fix this issue?

Kind Regards,

Ash

 

So the pseudocode I'm trying to translate into maple is for the greedy vertex coloring algorithm.

The pseudo code is:

Initialize:
1. for i = 1 to n do
2. f[i] := 0 (: no color assigned yet to vertex i :)
3. end(for)
Main loop:
4. for i = 1 to n do
5. let f[i] be the smallest positive integer
which is not in the set {f(j) : j ∈ adj[i]}
6. end(for)
7 return f

 

The closest I've gotten though is:

greedy := proc (G)

local i, j, n, k, L::list;

description "Take simple graph G and return a coloring of the vertices with at most Delta(G)+1 colors";

n := nops(Vertices(G));
L := [seq(x, i = 1 .. n)];
L := subsop(1 = c(1), L);
j := 1;
for i from 2 to n do
L[Vertices(G)[i]] := c(0)
end do;

for i from 2 to n do
   for k to i do
        if member(Vertices(G)[i], Neighbors(G, Vertices(G)[k])) then j := j+1
       end if; 
   end do;
L[Vertices(G)[i]] := c(j)
end do;
return L;
end proc;

Basically my procedure is returning more than delta+1 colors for most graphs, how can I edit it to fix this? I'm guessing the problem is somewhere in my nested loops. Also, I cannot use commands like greedycolor or isvertexcolorable. Thanks.

 

Having solution of an inequations system, is there a way/function/algorithm to find a particular numeric solution (as simplex[minimize] can do) ?

ex:

Q := {1 < x - y, x + y < 1};

R := solve(Q);

      { x < 1 - y, y < 0, y + 1 < x }

manually it's easy to find some numeric solutions:


      y = -1, x = 1
      y = -2, x = 0

but I need an automatic way.

Thank you for your help
s.py

 

Hi all

Can anybody suggest an algorithm allowing to detect, that two matrices of the same size can be obtained each from other by permutations of rows and columns? Maybe, such an algorithm there exists in LinearAlgebra package?

Good day everyone, please help in writing finite difference algorithm for these coupled nonlinear ODE. See it here Algorithm.mw 

#page 320 and 322 of book Singular introduction to commutative algebra

it return too many recursion 

 

hilbertseries([a+a*c, a+a*b, a+b+c]);

eq1 := a+a*c;

eq2 := a+a*b;

eq3 := a+b+c;

eq1a := Homogenize(eq1, h);

eq2a := Homogenize(eq2, h);

eq3a := Homogenize(eq3, h);

T3:=lexdeg([a,b,c,h]);

GB := Basis([eq1a,eq2a,eq3a], T3); #a

 

#MonomialHilbertPoincare(LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3));

 

with(PolynomialIdeals):

MonomialHilbertPoincare := proc (I3)

#I3:=[LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3)];

T2:=lexdeg([h,c,b,a]);

varj := [h,c,b,a];

I2 := InterReduce(I3, T2);

s := nops(I2);

if I2[1] = 0 then return 1 end if:

if I2[1] = 1 then return 0 end if:

if degree(I2[s]) = 1 then return (1-varj[1])^s end if:

lt := LeadingTerm(I2[s],T2);

leadexp := [degree(lt[2],h),degree(lt[2],c),degree(lt[2],b),degree(lt[2],a)];

j := 1;

for z from 1 to nops(leadexp) do

                if leadexp[j] = 0 then

                                j := j + 1;

                end if:

od:

finallist := [];

for z from 1 to nops(GB) do

                finallist := [op(finallist), GB[z]+varj[j]];

od:

quotientlist := Generators(Quotient(GB, varj[j]));

finallist2 := [];

for z from 1 to nops(quotientlist) do

                finallist2 := [op(finallist2), op(z,quotientlist)];

od:

return MonomialHilbertPoincare(finallist) + varj[1]*MonomialHilbertPoincare(finallist2);

end proc;

F:=[LeadingMonomial(GB[1],T3), LeadingMonomial(GB[2],T3), LeadingMonomial(GB[3],T3)];

MonomialHilbertPoincare(F);

 

 Do Hilbert series function classify all or only some type or some form of ideals?

 

Hi

I'm dealing with 2nd order ODE on Maple. By using " infolevel 5" Maple tell me that it use Kovacic's algorithm to find the solution. Could anybody tell me how or at least some idea so that I can go on this my self. Following here my ODE

Thank you so much

Chaimongkol

Hello!

I would like to start with the following set of 9 elements,
A = { E11, E12, E21, E22, E11+E12, E11+E21, E12+E22, E21+E22, E11+E12+E21+E22 }.

I need a procedure that takes each of those elements and creates 3 new ones in the following way: Eij becomes Eij1, Eij2, Eij1+Eij2. So for example, E11 will become: E111, E112, and E111+E112. And for example the fifth element in A (i.e. E11+E12) will become the 3 new elements: E111+E121, E112+E122, and E111+E121 + E112+E122.

Since each of the 9 elements gets triplicated, there will be a new set, call it B, with 27 elements.

B = {E111, E112, E111+E112, E121, E122, E121+E122, ... }

Now I want to repeat this process of triplicating again so that, for example, E111 becomes: E1111, E1112, and E1111+E1112. And so on. This new set C will have 81 elements. Now I want to repeat this one last time. The final set, D, will have 243 (3^5) elements. 

Step 2: 

For every pair of elements x and y in D, I want to compute z:=(x+y)mod2. If z already belongs to D, discard it, otherwise, place z in the set D2. Do this until there are no more elements to add together (note that if x+y is computed then I don't want y+x to be computed also--that's inefficient). Maybe the most efficient way is to perform all possibly combinations of x+y mod 2 to create the set D2 and then just go: D2 setminus D.

Step 3: For x in D and y in D2 perform all possible combinations of z:=(x+y)mod2 and place these in D3 then perform set subtraction again: D3 minus D2 minus D.

Repeat this process again: x in D and y in D3 to create new elements in D4. Repeat again until Dm is empty (that is, D(m-1) will be the last set that contains new elements). I'm expecting around 12 sets... 

The issue with this whole algorithm is that I often run out of memory so I need a clever way to do this, since this algorithm is essentially classifying 2^32 elements into disjoint sets. Thank you! 

1 2 3 4 5 Page 1 of 5