Chinese remainder theorem for WoW Professions

I am an engineer with a 24 units of Mithril and 24 Truesilver bars and 16 units of Goblin Rocket fuel How many Goblin Dragon Guns can I make? The Easy answer to this problem would be to assume that you can make 4 guns because you have 24 Mithril bars which is 4 multiples of 6. The problem with this is that 2 Mithril tubes, which you also need takes 6 mithril bars so in reality you can only make 2 guns because you needed 12 Mithril bars not 6 as though to make your gun. Now this problem is relatively simple, but can you think of any ones where the math to figure out the most number of units of something you can make with the least number of mats is a little harder than multiples of 6?

My Theory is that we can use Chinese remainder theorem and the Euclidean division algorithm to figure out the maximum amount of units we can make in any given profession.

(I want to go over some basics first then I will get to the idea, if you are well versed with abstract algebra and number theory in general you can skip to the following paragraph)

What is Chinese remainder theorem you ask? Good Question. Think back to elementary school when you did long division and how when one number did not always go into another you had a little extra; the remainder. The remainder of any number can be computed by a operation in math called a congruence modulus, the congruence modulus effectively solves the problem of the division algorithm, which is actually more of a theorem then a algorithm. The theorem in simple terms let m and n be integers with n > 0. Then there exist a unique integer q (quotient) and r (remainder) such that m=n*q+r , we know this from long division since when we multiply the quotient of our long division time the divsor and add the remainder we end up with the number we originally divided. Now how does this help us with congruence modulus well congruence modulus is the opposite of the division algorithm, not that if a number "a" divides a number b; a|b then b time a number k equals a. Thus b=ka, so then a number x is congruent y modulus r if an integer greater than 1 that divides y-x, so r|(y-x), this means that there exist an integer, let call him q that r=q(y-x) thus qr=y-x. This not only proves that for integers x, y, and r with integer r> 1 (x mod r) = (y mod r) if and only if there exist a integer q that divides (y-x), it also leads to the Chinese remainder theorem which say if the greatest common divisor of n and m is 1, (which means they are prime) the the system of equations x is congruent to a mod n and x is congruent to b mod m, has a solution , and any two solutions are congruent to m*n. This is a lot to digest, but we can then use this theorem in tandem with the euclidean algorithm to solve our optimization problem. Euclidean algorithm is actually an algorithm that helps find the greatest common divisor, it is a repeated use of the division algorithm's formula hence the division algorithm's name we take two numbers which we want to find their greatest common divisor, the largest of two numbers m and n (for this example m>n) is the one that gets long divided, we then write the quotient times our divisor (n) + our remainder (r) equal the integer m that is larger than n so m=qn+r we are going to then number our divisor and remainder so we will have q1 and r1 now we will take our n and do long division on it using our r1 the result will be another equation with a quotient q2 and a remainder r2 this will continue till we don't have a remainder to divide by the divisor of the previous long division. The last equation in which the last remainder=a quotient times the previous remainder, is the integer which is the greatest common divisor of both m and n.

The way then that we use the Chinese remainder theorem in professions then is through the use of the euclidean division algorithm. If the result of the algorithm is 1 for any set of n materials across m objects then there is a solution for the number of mats it takes to make one part and the number of mats needed for your unit. In my Dragon gun example I had 6 bars to make 2 Mithril tubes, and then I had six units to make my gun, now (GCD=greast common divisor) GCD(6,6)=1 where as GCD(6,3)=2. So then by finding the largest item requirement in the material you making and applying a euclidean division algorithm based on your available mats GCD'd with the required mats I am thinking that even some of the most embedded projects in which you are required use a previous made item in the creation of the new item, you should be able to solve the maximum number of items you can make with your minimum number of mats. This should in theory help you to spend less time farming mats and gain profession points that much quicker. In tandem with the Chinese Remainder Theorem, you can make your profession leveling a breeze. I would love to hear your thoughts ( thus the forum post) and critiques, I did write this up in a rush so if you see a theorem error feel free to let me know.
Reply Quote
90 Draenei Shaman
9515
If you remain interested in this topic as your education advances, you should look into Operations Resaearch as an area of advanced study. You'll need an undergraduate degree in Math to apply for most graduate programs, as a heads up warning.

Your first couple homework assignments in one of the initial classes should be quite similar to the problem above, and then things will get a lot more interesting as you continue.

Enjoy!
Reply Quote
Thank you for the reply, I am actually part way through my duel major in Computer Science and Mathematics. I love coming up with the math behind things. My university actually offer a operation research class that is out of my requirement, because you have to declare yourself as an applied mathematics major to have Operations Research be a class that counts toward graduation. Operation Research does sound like a neat field, the optimization problems are from what I know more mind boggling then this one, I knew a guy in operation research he wanted to measure the point at which a thermostat goes on and off to effectively learn ways to conserve power. The Idea was much like how a computer works with its 2 discrete stat system, but since air cools at a rate the data set was a little less discrete, so they were using both discrete and non discrete data methods to compare the room temperature and the time the thermostat stayed in a given stat. It was highly fascinating far above the scope of my learning. That is particularly what I love about math, I only get a brief dusting in undergraduate there is so much more when you dig your heels in and focus on one area.
Reply Quote

Please report any Code of Conduct violations, including:

Threats of violence. We take these seriously and will alert the proper authorities.

Posts containing personal information about other players. This includes physical addresses, e-mail addresses, phone numbers, and inappropriate photos and/or videos.

Harassing or discriminatory language. This will not be tolerated.

Forums Code of Conduct

Report Post # written by

Reason
Explain (256 characters max)
Submit Cancel

Reported!

[Close]