Modeling civilizations
This post describes how to use Diophantine linear equations to determine what conditions allow civilizations to depend on each other for survival or make civilizations unable to depend on each other for survival.
Using math to model the state of civilizations
By representing each civilization that interacts with another civilization as part of a Diophantine linear equation, use the greatest common divisor to determine if the civilizations interacting with each other are able to depend on each other for survival or are unable to depend on each other for survival.
Math and compilers
A Diophantine equation is a polynomial equation with 2 or more integer unknowns.
A linear Diophantine equation is an equation with 2 or more integer unknowns and the integer unknowns at most the power of 1.
A homogeneous linear Diophantine equation is
ax + by = 0, where a, b are integer constants and x, y are unknown variables.
A non-homogeneous linear Diophantine equation is
ax + by = c, where a, b, c are integer constants and x, y are unknown variables.
Compilers can use Diophantine linear equations and the Greatest Common Divisor (GCD) to determine if different parts of a program are dependent on each other.[1] If they are not dependent on each other, then they can be executed separately on different cores in the CPU or different computers in the cloud.
If a Diophantine linear equation IS evenly divisible by the GCD, then the terms in the linear equation ARE dependent on each other.
If a Diophantine linear equation is NOT evenly divisible by the GCD, then the terms in the linear equation are NOT dependent on each other.
Loop code in general
int a = constantint b = constantfor (int i = 0; i < n; i++)
{ array[x * i + a] = array[y * i + b];
}
To decide if there is a dependence in the code, where the same memory location is read and written to, between array[x * i + a] and array[y * i + b], perform simple algebra to put the variables on one side of the equals sign and the constants on the other, then calculate GCD(x,y).
Then if the GCD(x,y) evenly divides the constant in the equation, then exists a dependency in the code. If GCD(x,y) does not evenly divide the constant in the equation, then both statements are independent and the parts of code that are represented by the linear Diophantine equation can be executed in parallel.
Example of using non-homogeneous Diophantine linear equations and the Greatest Common Divisor (GCD) to determine if different parts of a program that share the same memory in a computer can be exist on different cores in a computer or different computers in the cloud that do not share the same memory.
Example 1double array[] = new double[1000];for (int i = 0; i < 100; i++) array[2 * i + 2] = array[2 * i + 1];
=> 2*i + 2 = 2*i + 1 => 2*i – 2*i = -1
GCD(2, 2) = 2
=> -1 / GCD(2,2)
=> -1 / 2
=> -1 is not evenly divisible by 2 (it doesn’t result in remainder = 0)
=> no dependency in these different parts of the code
=> different parts of the code can be run on different computers in the cloud
Example 2for (int i = 0; i < 100; i++) array[2 * i] = array[3 * i + 211];
=> 2 * i = 3 * i + 211
=> 2 * i – 3 * i = 211
=> GCD(2,3) = 1
=> 211 is evenly divisible by 1
=> dependency in these parts of the code
=> different parts of the code can’t be run on different computers in the cloud
Applying homogeneous and non-homogeneous Diophantine linear equations to the state of civilizations
If a Diophantine linear equation IS evenly divisible by the GCD, then the terms in the linear equation ARE dependent on each other.
If a Diophantine linear equation is NOT evenly divisible by the GCD, then the terms in the linear equation are NOT dependent on each other.
Just like how Diophantine linear equations and the GCD determine if different parts of a program that share the same memory are dependent on each other, they can also be used to determine if different civilizations are dependent on each other because of the resources that they share or if conditions exist that force the different civilizations to exist independent of each other.
Theoretical example
m = invasion
n = importing food
Civilization X spends 90% of its gold reserves defending against invasion (m) and 10% of its gold reserves importing food (n) plus some other unrelated crisis u.
Civilization Y spends 40% of its gold reserves defending against invasion (m) and 60% of its gold reserves importing food (n) plus some other unrelated crisis v.
m represents invasion, n represents importing food
X: 9m + 1n + u = 0
Y: 4m + 6n + v = 0
Solve the Diophantine linear equation when each civilization is part of the linear equation
Scenario 1
u = v = 0 => no other unrelated crisis occurring in either civilization
This scenario is represented by a homogeneous Diophantine linear equation.
9m + 1n + 0 = 4m + 6n + 0
9m – 4m + 1n -6n = 0
5m -5n = 0
GCD(5,5) = 5
0 is evenly divisible by the GCD
Therefore, civilizations X and Y can depend on each other for their survival under these conditions if both civilizations have these crises at the same time and they spend these different percentages of their time dealing with these crises.
Scenario 2
u = 3, v = 0 => an unrelated crisis occurred for civilization X
u is a constant so it’s some other unrelated crisis—or the resulting effect/strain it has on a civilization—that is affecting only civilization X.
This scenario is represented by a non-homogeneous Diophantine linear equation.
The unrelated crisis in this example is a famine that requires civilization X spend 30% of its silver reserves buying food from another civilization for civilization X to deal with the crisis that is not related to how civilizations X and Y normally interact with each other.
The constant—the unrelated crisis—doesn’t change no matter how the other terms (crises) in the equation change or how they’re related or interact with each civilization.
X: 9m + 1n + 3 = 0
Y: 4m + 6n + 0 = 0
9m + 1n + 3 = 4m + 6n + 0
9m – 4m + 1n -6n = -3
5m – 5n = -3
GCD(5,5) = 5
-3 is not evenly divisible by the GCD
Therefore, civilizations X and Y cannot depend on each other for their survival under these conditions if both civilizations have these crises at the same time and they spend these different percentages of their time dealing with these crises plus some other unrelated crisis c affecting only civilization X.
Conclusion: Civilizations X and Y cannot depend on each other in a time of crisis under these conditions.
Scenario 3
u = 10, v = 0
u is a constant so it’s some other unrelated crisis—or the resulting effect/strain it has on a civilization—that is affecting only civilization X.
This scenario is represented by a non-homogeneous Diophantine linear equation.
The unrelated crisis in this example is a famine that requires civilization X spend 100% of its silver reserves buying food from another civilization for civilization X to deal with the crisis that is not related to how civilizations X and Y normally interact with each other.
X: 9m + 1n + 10 = 0
Y: 4m + 6n + 0 = 0
9m – 4m + 1n -6n = -10
5m – 5n = -10
GCD(5,5) = 5
-10 is evenly divisible by the GCD
Therefore, civilizations X and Y can depend on each other for their survival under these conditions if both civilizations have these crises at the same time and they spend these different percentages of their time dealing with these crises plus some other unrelated crisis u affecting only civilization X.
Conclusion: Civilizations X and Y can depend on each other in a time of crisis under these conditions.
Check the math:
(1) Since GCD(5,5) = 5 and -10 is evenly divisible by the GCD (5), there is an integer solution.
(2) Solve the non-homogeneous Diophantine linear equation for the scenario by finding a solution to the homogenous Diophantine linear equation for the scenario.
5m – 5n = -10, m, n are integers
GCD(5,5) = 5
First, find a particular solution to 5m – 5n = -10
Since 5(2) – 5(4) = -10, m = 2, n = 4 is a particular solution out of many possible ones.
Substitute variables by subtracting the particular solution from the non-homogeneous Diophantine linear equation.
Let u = (m – particular solution for m)
Let v = (n – particular solution for n)
=> u = m – 2, v = n – 4
Original left side of equation was 5m – 5n so substitute m, n with u, v
=> 5u – 5v = 5(m – 2) – 5(n – 4)
=> 5u – 5v = 5m – 10 -5n + 20
=> 5u – 5v = 5m – 5n + 10
Original equation was 5m – 5n = -10 so substitute the values 5m – 5n with -10 in the equation
=> 5u – 5v = 5m – 5n + 10
=> 5u – 5v = -10 + 10
=> 5u – 5v = 0 This is the homogeneous equation for the problem.
Now, solve the homogeneous equation 5u – 5v = 0
=> General solutions are u = -5k, v = 5k
Substitute values in u = m – 2, v = n – 4
=> -5k = m – 2, 5k = n – 4
=> General solutions are:
m = -5k + 2, n = 5k + 4
Substitute the values of the general solution into the original equation
5m – 5n = -10
5(-5k + 2) – 5(5k + 4) = -10
-25k + 10 -25k – 20 = -10
-50k – 10 = -10
-50k = 0
k = 0
To confirm, substitute k into the general solution
m = -5k + 2, n = 5k + 4
=> m = 2, n = 4 Note: this is a particular solution to 5m – 5n = -10
Substitute m, n into the original equation:
5m – 5n = -10
=> 5(2) – 5(4) = – 10
=> 10 – 20 = -10
=> -10 = -10
Confirmed.
References
[1] Compilers Principles, Techniques, & Tools, 2nd edition. pp. 815-820
Michael Wuerth's blog 