I always wondered how it is possible to find a reverse formula of a linear congruential generator.
For example we have the formula:
X(n+1) = ( ( 0x41C64E6D * X(n) ) + 0x3039 ) mod 0x100000000
which, starting with 0, gives you values: 0, 12345, 3554416254, 2802067423...
So I wonder how it is possible to calculate this reverse formula:
Y(n+1) = ( ( 0xEEB9EB65 * Y(n) ) + 0xFC77A683 ) mod 0x100000000
which gives the expected values: ...2802067423, 3554416254, 12345, 0...
The inverse of x → Ax+B (mod N) is y → A-1y - A-1B (mod N). Assuming gcd(A,N)=1, of course. The inverse takes Ax+B to A-1(Ax+B) - A-1B = x (mod N), for all x.
The multiplicative inverse of A mod N can be computed by the extended Euclidean algorithm. But for the case when N=2m, it's even easier. The process is simply to solve Ax=1 (mod 2m) by writing in binary and determining the bits of x from right to left (least significant to most significant) as follows:
I show you how deep the rabbit hole goes.
Current projects: NES: Tetris "fastest 999999" (improvement, with r57shell)
Genesis: Adventures of Batman & Robin (with Truncated); Pocahontas; Comix Zone (improvement); Mickey Mania (improvement); RoboCop versus The Terminator (improvement); Gargoyles (with feos)
x2=12-A2
and
(1+x)2+12=(1+{(1-A)2+12})2
Two equations and two unknowns. It should be quite easy to calculate.
x≈0.8832
I show you how deep the rabbit hole goes.
Current projects: NES: Tetris "fastest 999999" (improvement, with r57shell)
Genesis: Adventures of Batman & Robin (with Truncated); Pocahontas; Comix Zone (improvement); Mickey Mania (improvement); RoboCop versus The Terminator (improvement); Gargoyles (with feos)
x2=12-A2
and
(1+x)2+12=(1+{(1-A)2+12})2
Two equations and two unknowns. It should be quite easy to calculate.
x≈0.8832
Based on Archanfel's labelling above, we have
x2+A2=1
A/x=(1-A)/1
So A=x/(1+x). Substituting into x2+A2=1 and multiplying by (1+x)2:
x2+(1+x)2x2=(1+x)2
→ x4+2x3+x2-2x-1=0
This is a quartic equation, of which the quartic formula is an utter mess. But let's try adding 2(x2+2x+1) to both sides:
x4+2x3+3x2+2x+1=2(x2+2x+1)
→ (x2+x+1)2=(sqrt(2)(x+1))2
Magic! Both sides are a perfect square! (In the real polynomial ring, of course. 2 isn't a perfect integer square, but we aren't restricting to integers here.)
So then x2+x+1=±sqrt(2)(x+1). Let's only take the positive one (the negative one gives complex numbers). So then
x2+x+1=sqrt(2)(x+1)
→ x2+dx+d=0, where d=1-sqrt(2)
→ x=(1/2)(-d±sqrt(d2-4d))=(1/2)(sqrt(2)-1±sqrt(3-2sqrt(2)-4+4sqrt(2))
→ x=(1/2)(sqrt(2)±sqrt(2sqrt(2)-1))
Since x is positive, we take the positive: x=(1/2)(sqrt(2)-1+sqrt(2sqrt(2)-1)), which is about equal to 0.8832.
Note that A equals the absolute value of the negative root, which is about 0.4690.
Note also that x and A are constructible numbers. I leave it to others to figure out a straightedge and compass construction for x from a unit-length line segment.
For those wondering how I knew to add 2(x2+2x+1) to both sides of x4+2x3+x2-2x-1=0, well, I cheated. I used Wolfram Alpha's Root Finder to find what x was, then reconstructed its minimal polynomial (which is the polynomial above), thus back-solving for the method needed to find x in the first place.
The region of intersection is "obviously" a warped unit square. Thus the area is 1. For certain values of 1, anyway.
But I digress. If this question has some kind of fancy solution, I don't know about it. So I'll just do it the direct way. Warning: wall of computation incoming.
Rotate the diagram about the origin so that the common center of the two circles not centered at the origin is (√17,0) instead of (4,1). This doesn't change the area and makes the following calculations more tolerable.
We then look for the x-values of the intersections of a circle x2+y2=p2 with a circle (x-√17)2+y2=q2 for p in {2,3} and q in {3,4}. Solving the equations gives -2(√17)x+17=q2-p2, or x=(17+p2-q2)/(2√17)=(17+p2-q2)α, where α denotes 1/(2√17) for obvious clarity. Concern ourselves with only the intersections in the first quadrant (positive y).
-For p=2,q=3 (bottom intersection), x=12α.
-For p=2,q=4 (left intersection), x=5α.
-For p=3,q=3 (right intersection), x=17α.
-For p=3,q=4 (top intersection), x=10α.
Now, we derive a formula for computing the area under a unit circle and above the x-axis from x=a to x=b:
int[a,b] sqrt(1-x2)dx=int[*,**] sqrt(1-sin2(θ))cos(θ)dθ (x=sin(θ))
= int[*,**]cos2(θ)dθ=int[*,**] (1+cos(2θ))/2 dθ
= (1/2) θ [θ=*,**] + (1/4) sin(2θ) [θ=*,**]
= (1/2) θ [θ=*,**] + (1/2) sin(θ)cos(θ) [θ=*,**]
= (1/2) (θ [θ=sin-1(a),sin-1(b)] + x sqrt(1-x2) [θ=a,b])
= (1/2) ( sin-1(b)-sin-1(a) + b sqrt(1-b2) - a sqrt(1-a2) )
Therefore the area under a circle of radius r centered at (p,0) and above the x-axis from x=a to x=b is:
Area(r,p,a,b)=(r2/2) ( sin-1(B)-sin-1(A) + B sqrt(1-B2) - A sqrt(1-A2) ),
where A=(a-p)/r and B=(b-p)/r.
Then the area we want is the sum of:
(noting that √17=34α)
* Area(4,√17,5α,10α) (upper left boundary)
= 8 ( sin-1(29α/4) - sin-1(6α) + (29α/4) sqrt(1-(29α/4)2) - 6α sqrt(1-(6α)2) )
* Area(3,0,10α,17α) (upper right boundary)
= (9/2) ( sin-1(17α/3) - sin-1(10α/3) + (17α/3) sqrt(1-(17α/3)2) - (10α/3) sqrt(1-(10α/3)2) )
* -Area(2,0,5α,12α) (lower left boundary)
= -2 ( sin-1(6α) - sin-1(5α/2) + 6α sqrt(1-(6α)2) - (5α/2) sqrt(1-(5α/2)2) )
* -Area(3,√17,12α,17α) (lower right boundary)
= (-9/2) ( sin-1(22α/3) - sin-1(17α/3) + (22α/3) sqrt(1-(22α/3)2) - (17α/3) sqrt(1-(17α/3)2) )
The sum is:
8 sin-1(29α/4) - 10 sin-1(6α) + 9 sin-1(17α/3) - (9/2) sin-1(10α/3) + 2 sin-1(5α/2) - (9/2) sin-1(22α/3)
+
α [ 8 (29/4) sqrt(247/1088) - 10 (6) sqrt(8/17) + 9 (17/3) sqrt(19/36) - (9/2) (10/3) sqrt(128/153) + 2 (5/2) sqrt(247/272) - (9/2) (22/3) sqrt(32/153) ]
=
8 sin-1(29α/4) - 10 sin-1(6α) + 9 sin-1(17α/3) - (9/2) sin-1(10α/3) + 2 sin-1(5α/2) - (9/2) sin-1(22α/3)
+
α [34 sqrt(247/272) - 102 sqrt(8/17) + 17 sqrt(19/4)]
(try evaluating in a calculator)
≈1.07578-0.06317=1.01261≈1.013
Well, that was a mess, wasn't it? Might as well just say that the area is 1.
This was a question in a mathematical olympiad that I've done. Determine all the functions f:ℝ→ℝ such that f(xf(y) + f(x)) = 2f(x) + xy , for all x, y in ℝ.
First note that on the right we have only a linear combination of f, but on the right we have a function of a function. This means that for a polynomial, the left side increases much faster than the right side does. EG a quadratic of a quadratic turns it into a quartic, degree 3 to degree 6, etc. This means to control this growth and equalize both sides we cannot have our function above degree 2, hence we have
f(x)=ax+b.
2f(x)=2ax+2b
2f(x)+xy=2ax+2b+xy=(2a+y)x+2b
f(y)=ay+b.
xf(y)=axy+bx.
xf(y)+f(x)=axy+bx+ax+b=(ay+b+a)x+b
f(xf(y)+f(x))=a((ay+b+a)x+b)+b=(ay+b+a)ax+ab+b=(a2y+ab+a2)x+(ab+b)
These need to be true for all x,y, eg x=0.
2f(x)+xy=f(xf(y)+f(x))
2b=ab+b
0=ab-b=b(a-1)
b=0 or a=1
For b=0
2f(x)+xy=f(xf(y)+f(x))
(2a+y)x=(a2y+a2)x
2a+y=a2y+a2=a2(y+1)
True for all values, eg y=0
2a+y=a2(y+1)
2a=a2
0=a(a-2)
a=0, or 2.
{a,b}={0,0},{2,0}
For a=1
2f(x)+xy=f(xf(y)+f(x))
(2+y)x+2b=(y+b+1)x+(b+b)
(2+y)x+2b=(y+b+1)x+2b
(2+y)x=(y+b+1)x
2+y=y+b+1
2=b+1
1=b
{a,b}={1,1}
TESTING{a,b}={0,0}
f(x)=0x+0=0
2f(x)+xy=0+xy=xy
f(y)=0
2f(y)+f(x)=0+0=0
f(2f(y)+f(x))=f(0)=0
=/=0+xy
BAD{a,b}={2,0}
f(x)=2x+0=2x
2f(x)=4x
2f(x)+xy=4x+xy
xf(y)+f(x)=x(2y)+2x=2xy+2x
f(2f(y)+f(x))=f(2xy+2x)=4xy+4x
=/=2f(x)+xy
BAD{a,b}={1,1}
f(x)=1x+1=x+1
2f(x)=2x+2
2f(x)+xy=2x+2+xy
xf(y)+f(x)=x(y+1)+(x+1)=xy+x+x+1=xy+2x+1
f(xf(y)+f(x))=f(xy+2x+1)=(xy+2x+1)+1=xy+2x+2
=2f(x)+xy
GOOD
Hence the only function is f(x)=x+1. The other 2 generated values failed, because they only satisfied the equation at the local value x=0, (or y=0, IE along main axes).
Flip, you proved that f(x)=x+1 is the only polynomial that solves the question. However, the problem asks for all sorts of functions, even transcendental, discontinuous or weird functions, which appear all the time in analysis.
This was a question in a mathematical olympiad that I've done. Determine all the functions f:ℝ→ℝ such that f(xf(y) + f(x)) = 2f(x) + xy , for all x, y in ℝ.
This is a very difficult question (expected for a mathematical olympiad). I'm still working to see if I can solve it fully; the farthest I have gotten is to show that if f is such a function, then f(x)=x+1 for all integers x.
Edit:
OK, I finally figured out how to do the question. The crux of the question is to figure out that f(-2)=-1, and then put y=-2 into the above equation. Here is my solution:
Based on the equation f(xf(y)+f(x)) = 2f(x)+xy, we know that f(x) is an onto (surjective) function; given a real number c, simply choose x≠0 and y=(c-2f(x))/x and the RHS becomes c. So, choose a,b such that f(a)=1 and f(b)=0. Then f(bf(a)+f(b))=2f(b)+ba, which gives 0=ba. Therefore either a=0 or b=0.
If b=0, then f(0)=0. Then f(xf(0)+f(x))=2f(x)+x*0, which gives f(f(x))=2(f(x)). Since f is onto, that means f(z)=2z for all real z. But then f(1f(1)+f(1))=2f(1)+1*1, which gives 8=5, contradiction.
So a=0, and thus f(0)=1. Now f(-1f(-1)+f(-1))=2f(-1)+(-1)*(-1) gives f(0)=2f(-1)+1, or f(-1)=0. Then f(xf(-1)+f(x))=2f(x)+x*(-1), which gives f(f(x))=2f(x)-x, or x=2f(x)-f(f(x)). Solving the equation f(x)=-1 by substitution gives the only possibility x=2*(-1)-f(-1), or x=-2; since f is onto, that means f(-2)=-1.
Now f(xf(-2)+f(x))=2f(x)+x*(-2), which gives f(f(x)-x)=2*(f(x)-x). Consider the non-empty set {f(x)-x|x in ℝ} and let d be an element of the set. Then f(d)=2d. Taking x=2f(x)-f(f(x)) and using it to solve the equation f(x)=d by substitution gives the only possibility x=2d-f(d), or x=0; since f is onto, that means f(0)=d. But since f(0)=1, that means d=1. Since this holds for every element of {f(x)-x|x in ℝ}, that means {f(x)-x|x in ℝ}={1}, and so f(x)-x=1 for every real x, and therefore as a function, f(x)=x+1.
Interestingly, the solution is pretty much the same even if we allow f to be a function from complex numbers to complex numbers.
By the way, Amaraticando, you said that this was a question on a math olympiad that you did. Did you do and/or solve this question during the olympiad?
Edit 2: Actually, if you replace "choose x≠0 and y=(c-2f(x))/x" with "choose x=1 and y=c-2f(1)", the same logic applies whenever f is a function on an integral domain.
Edit 2.5: Oops, a bit of an error on the last edit. If f is a function on an integral domain where 3=0 (e.g. mod 3), then the apparent solution of f(z)=2z in the case b=0 (f(0)=0) is in fact a solution, since f(xf(y)+f(x)) = 2f(x)+xy gives 4xy+4x=4x+xy and both sides are always equal since 4=1.
By the way, Amaraticando, you said that this was a question on a math olympiad that you did. Did you do and/or solve this question during the olympiad?
I solved it partially, but when I got home, I was able to solve it much faster.
The official solution was quite different than yours, by proving that f is injective and then applying a bunch of (x, y) to the original equation. Your solution is nice too!
For an arbitrary convex, simple quadrilateral ABCD in 3D space, define an S axis that goes from 0 to 1 along AB, and a T axis that goes from 0 to 1 along AD. Having defined a value at each corner, and wanting to find the corresponding value at some point (S,T) using bilinear interpolation, how does one determine the coefficient before ST?
Edit: Perhaps what I am trying to do is not even possible?
For an arbitrary convex, simple quadrilateral ABCD in 3D space, define an S axis that goes from 0 to 1 along AB, and a T axis that goes from 0 to 1 along AD. Having defined a value at each corner, and wanting to find the corresponding value at some point (S,T) using bilinear interpolation, how does one determine the coefficient before ST?
Edit: Perhaps what I am trying to do is not even possible?
If I understand the question correctly, we're trying to fit a function to some values given at the corners of convex simple quadrilateral ABCD, such that the function is bilinear along AB (S-axis) and AD (T-axis). In particular, ABCD is coplanar and no three points are collinear.
In ST-coordinates, A=(0,0), B=(1,0), and D=(0,1). The important thing is to find the ST-coordinates of C. Let v(AB), etc., denote the vector from A to B in its original coordinates. We can find the ST-coordinates of C by solving the matrix equation [v(AB) v(AD)][s,t]T=[v(AC)] for s and t (equivalently, v(AB)s+v(AD)t=v(AC)). There is a unique solution; if there were no solution, then ABCD would not be coplanar; if there were infinitely many solutions, then ABD would be collinear. Let C=(s0,t0) in ST-coordinates. Note that s0 and t0 are nonzero; otherwise ABC or ACD would be collinear.
Let a,b,c,d be the values at A,B,C,D, respectively. We want to fit a bilinear function f(s,t)=w+xs+yt+zst to these values, where (s,t) is the point in ST-coordinates. Then
f(0,0)=w=a
f(1,0)=w+x=b → x=b-a
f(0,1)=w+y=d → y=d-a
f(s0,t0)=w+xs0+yt0+zs0t0=c
→
z=(c-a-(b-a)s0-(d-a)t0)/(s0t0)
This z would be the coefficent of st in f(s,t).
Note that it is not important which vector space ABCD is embedded in or which vector space the values assigned to the corners of ABCD come from; this process applies in any case. In fact, this process may apply even if ABCD is not a convex and/or simple quadrilateral; the only condition is that ABCD is coplanar, and that ABC, ABD, and ACD are not collinear.
Edit: Fixed solution for z; it was missing an "a".
Thanks for the quick answer. I shall elaborate on my problem:
I'm coding a game where there is a "plank" item which is defined by two points. But those two points need to have a fixed distance.
fig.1 just calculates the distance at a given time. I want to attempt to fix the distance for P2 in fig.2 (I hope I'm not confusing).
In my example this happened to be the distance:
(((4-9))*1)^2+((9-16)*1)^2)^(1/2) = 8.602
But let's say I want to fix it to 10, then:
(((4-9))*(10/8.602))^2+((9-16)*(10/8.602))^2)^(1/2) = 10
But this doesn't give me the new P2 X or Y either. How can I extend or shorten the given distance to a fixed distance to find the new position of P2?
Maybe do I need to solve these equations?
(((4-X))*(10/8.602))^2+((9-16)*(10/8.602))^2)^(1/2) = 10
(((4-9))*(10/8.602))^2+((9-Y)*(10/8.602))^2)^(1/2) = 10
Assuming you have calculated the current distance between the two points to be Dc. Scaling the line to become some target distance (Dt) will scale the distances on the x and y axis with the exact same factor. In other words, given your original blue point (Xo, Yo) and current red point (Xc, Yc), it follows that:
Dt / Dc = (Xt - Xo) / (Xc - Xo) = (Yt - Yo) / (Yc - Yo)
where (Xt, Yt) is your target location. I hope this is enough to solve it for you.
Wikipedia asserts that Euclid's parallel postulate is equivalent to Pythagoras' theorem. It also asserts that it's equivalent to the postulates "every triangle can be circumscribed" and "there is no upper limit to the area of a triangle" (Wallis axiom).
The equivalence between those postulates seems extremely non-self-evident and unintuitive. Could someone explain why they are equivalent?
Wikipedia asserts that Euclid's parallel postulate is equivalent to Pythagoras' theorem. It also asserts that it's equivalent to the postulates "every triangle can be circumscribed" and "there is no upper limit to the area of a triangle" (Wallis axiom).
The equivalence between those postulates seems extremely non-self-evident and unintuitive. Could someone explain why they are equivalent?
They are all equivalent because the assumption of their validity (or not) implies something about the Gaussian curvature of the surface your various objects inhabit, and all the examples you gave relate specifically to the properties of triangles on those surfaces.
To wit:
The Pythagorean Theorem is only true on a surface of zero curvature, like the Euclidean Plane. But Euclid's parallel postulate is one of the defining features that differentiates Euclidean geometry from, say, hyperbolic and spherical geometries, where the Pythagorean Theorem doesn't hold. Though this is just informal reasoning and obviously not a proof, it does seem reasonable to consider that the Pythagorean Theorem and the Parallel Postulate might just be equivalent. (Of course it is actually possible to rigorously show that each implies the other.)
Similarly, "every triangle can be circumscribed" isn't true in hyperbolic geometries, where triangles whose vertices lie on horocycles or hypercycles have no circumscribing circles. (I must admit I don't see off the top of my head which spherical triangles have no circumscribing circles, maybe the quadrants? That doesn't really make sense to me but there may be something technical I'm missing ...)
Triangles on spheres obviously have an upper bound on their area, as the sphere itself is a finite surface. Similarly, if I'm not mistaken, ideal triangles on your standard hyperbolic plane have the maximal area, namely pi. So saying "there is no upper limit to the area of a triangle" again implies zero curvature, i.e. the Euclidean Plane, the thing which again is distinguished from other geometries by the parallel postulate. (And by some other things, in various cases, but just generally speaking ...)
I must admit I don't see off the top of my head which spherical triangles have no circumscribing circles, maybe the quadrants? That doesn't really make sense to me but there may be something technical I'm missing ...
On a sphere it's possible to put three points on a straight line and still make a triangle out of them (by "spiralling" around the sphere to connect the outer points with the center point), and it's impossible to circumscribe three points on a straight line.
Euclidean, hyperbolic and elliptic geometries are the only three alternatives in this context? Is a spherical coordinate system an elliptic geometry?
Why isn't it possible to circumscribe every possible triangle in hyperbolic geometry?
Find the area of an intersection, both are the same.
Is fig.1 correct?
What is P2 x and P2 y in fig.2 ?
