text:
# How to determine the linear and angular velocity of one end of a rod that is pinned on a track on each side?

I am working on trying to determine the velocity of one end of a rod that is pinned on both ends into two different tracks. One track is linear and the pinned end has known values. The other side is pinned to a circular track in which no values are known.

I have attempted to obtain the angular velocity first as I am using $$V_B=V_A+V_{B/A}$$

by using $$\omega = v/r$$

I have also noted to obtain $$V_{B/A}$$ I need to find $$\dot\theta$$ which equals $$\omega$$

$$V_{B/A}$$ has the equation of $$(\dot\theta\hat k) \times I*(cos\theta\hat i - sin\theta\hat j)$$

I am stuck at finding $$\theta$$ or $$V_{B/A}$$ because it seems both need the other in order to get an answer.

Does anyone have a suggestion of equations to look at to obtain one of those two values with the information known?

Could I treat point A is being the center of the circle and use the formula of $$V_A = r\omega$$ to obtain the value for $$\omega$$

• I have doubts that $\frac{d\theta}{dt} = \omega = \frac{v}{r}$. – Futurologist Nov 24 '20 at 21:17
• It's in my textbook as such. – Barrett Cloud Nov 25 '20 at 2:07
• It was done by using $V_A + V_{B/A}$ with $V_{B/A}$ = $\omega$ X $R_{B/A}$ – Barrett Cloud Nov 25 '20 at 2:15
• So what is $r$ here? Isn't it the radius of the circle? Do you mean $r$ should be more like $l$? – Futurologist Nov 25 '20 at 2:28
• R here is the length of the rigid bar, which is how I got the angle of $\theta$ through s being displacement, and r being the length giving me $s = r\theta$ going to $s/r = \theta$, which in turn with the angle from the x axis up to be being 90 degrees leaves $\phi = 90-27.56 = 62.44$ – Barrett Cloud Nov 25 '20 at 3:16

Calculate $$\varphi_0 = \arctan(s)$$. Then the position of point $$A$$ is \begin{align} &X_A = X_A\\ &Y_A = s\,X_A + b \end{align} The position of point $$B$$ can be expressed in terms of the angle $$\theta$$ as \begin{align} &X_B = X_A + l\cos(\theta + \varphi_0)\\ &Y_B = b + s\,X_A + l\sin(\theta + \varphi_0) \end{align} However, we have a restricition for point $$B$$, called a holonomic constrant, which is that $$B$$ always moves along the circle $$(X-c)^2 + Y^2 = r^2$$, Therefore $$(X_B-c)^2 + Y_B^2 = r^2$$ which explicitly is $$\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big)^2 \, + \, \big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big)^2 \, = \, r^2$$ Thus, the position of the bar, moving so that point $$A$$ is always on the line $$Y = sX + b$$ and point $$B$$ is always on the circle $$(X-c)^2 + Y^2 = r^2$$ can be described by the three equations \begin{align} &X_B = X_A + l\cos(\theta + \varphi_0)\\ &Y_B = b + s\,X_A + l\sin(\theta + \varphi_0)\\ &\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big)^2 \, + \, \big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big)^2 \, = \, r^2 \end{align} Hence, if you know the way $$X_A = X_A(t)$$ changes with respect to time $$t$$, then you can blug it in the third equation and solve it for $$\theta = \theta(t)$$. After you have found $$\theta$$ you can plug it alongisde $$X_A$$ in the first two equations to find the coordinates $$(X_B, \, Y_B)$$ of $$B$$.

To find the angular velocity $$\frac{d\theta}{dt}$$ of the bar, you simply differentiate the third equation with respect to $$t$$ and add the new differentiated equation to the system, as a forth equation: \begin{align} &X_B = X_A + l\cos(\theta + \varphi_0)\\ &Y_B = b + s\,X_A + l\sin(\theta + \varphi_0)\\ &\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big)^2 \, + \, \big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big)^2 \, = \, r^2\\ &\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big) \left(\,\frac{dX_A}{dt} - l\sin(\theta + \varphi_0) \frac{d\theta}{dt}\,\right) = \, \\ &+ \,\big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big) \left(\,s\,\frac{dX_A}{dt} + l\cos(\theta + \varphi_0) \frac{d\theta}{dt}\,\right) \, = \, 0 \end{align} To find $$\frac{d\theta}{dt}$$ you need only the last two equations: \begin{align} &\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big)^2 \, + \, \big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big)^2 \, = \, r^2\\ &\big( \, X_A + l\cos(\theta + \varphi_0) - c \,\big) \left(\,l\sin(\theta + \varphi_0) \frac{d\theta}{dt} - \frac{dX_A}{dt}\,\right) \, = \,\big(\,b + s\,X_A + l\sin(\theta + \varphi_0)\,\big) \left(\,s\,\frac{dX_A}{dt} + l\cos(\theta + \varphi_0) \frac{d\theta}{dt}\,\right) \end{align} Given $$X_A = X_A(t)$$ and $$V_A = V_A(t) = \frac{dX_A}{dt}$$, you can take the first equation from the latter system of two equations, plug $$X_A$$ in it and solve for $$\theta = \theta(t)$$. This equation is the hardest to solve. After that, plug in the second equation $$X_A, \, \theta,\, \frac{dX_A}{dt}$$ and solve for the angular speed $$\frac{d\theta}{dt}$$.

Finally, to find the velocity of $$B$$, you simply take the first two equations of the four equation system above and differentiate them with respect to $$t$$: \begin{align} &V_{x,B} = \frac{dX_B}{dt} = \frac{dX_A}{dt} - l\sin(\theta + \varphi_0)\frac{d\theta}{dt}\\ &V_{y,B} = \frac{dY_B}{dt} = s\,\frac{dX_A}{dt} + l\cos(\theta + \varphi_0)\frac{d\theta}{dt} \end{align} So, you just have to plug in this equation the already calculated $$\theta, \,\frac{d\theta}{dt}$$ and $$\frac{dX_A}{dt} = V_A$$.

OLD VERSION. Let's simplify things a bit. First, perform the translation: \begin{align} &X = \tilde{x} + c \\ &Y = \tilde{y} \end{align} Then the equation of the circle becomes $$r^2 = (X - c)^2 + Y^2 = \tilde{x}^2 + \tilde{y}^2$$ Then find the angle between the line $$Y = sX + b$$, which in new coordinates is $$\tilde{y} = s\,\tilde{x} + (sc + b)$$, and the horizontal axis: the slope is the tangent of that angle, i.e. $$\varphi_0 = \arctan(s)$$ Next, perform a clock-wise rotation of angle $$\varphi_0$$ so that the line $$\tilde{y} = s\,\tilde{x} + (sc + b)$$ becomes a line $$\tilde{y} = h$$ (one can calculate the distance $$h$$ between the center of the circle (the origin) and the line in question) parallel to the horizontal $$x-$$axis: \begin{align} \tilde{x} = \cos(\varphi_0)\, x \, - \, \sin(\varphi_0)\, y\\ \tilde{y} = \sin(\varphi_0)\, x \, + \, \cos(\varphi_0)\, y \end{align} Denote by $$x_A$$ the $$x-$$coordinate of the point $$A$$ moving along the line. The $$y-$$coordinate is $$h$$ and is fixed. The equation of the upper half of the circle in these new rotated and translated coordinates can be written as $$y = \sqrt{r^2 - x^2}$$
If $$\theta$$ is the angle between the rod $$AB$$ and the line $$y = h$$, which is parallel to the $$x-$$axis, then the equations for the position of the other end of the rod, point $$B$$, are \begin{align} &{x}_B = x_A + l\, \cos(\theta)\\ &{y}_B = \sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2} \end{align} Observe, there are two free parameters for the position of $$B$$ on the circle, namely $$x_A$$ and $$\theta$$. However, there is another restriction - the distance between $$A$$ and $$B$$ is always $$l$$. Hence: $$\big(x_B - x_A\big)^2 + \big(y_B - y_A\big)^2 = l^2$$ or after substitutions $$l^2 \cos^2(\theta) \, + \, \Big(\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2\,} - h\Big)^2 \, = \, l^2$$ which establishes a link between the coordinates $$x_A$$ and $$\theta$$. You can move the first term from the lefthand side to the right one, then apply a central trigonometric identity to the right hand side, after which you can take square root on both sides, and finally obtain the simplified equation $$\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2\,} - h \, = \, \pm \, l\sin(\theta)$$ where you should have in mind the sign $$\pm$$ depends on the sign of the right hand side. On your picture, $$\theta \in [0, \pi/2)$$ so you can choose a plus sign and the equation is $$\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2\,} - h \, = \, l\sin(\theta)$$
Now, in this latter equation $$x_A = x_A(t)$$ and $$\theta = \theta(t)$$ are function of the time $$t$$, so we can differentiate the equation with respect to $$t$$ and pair it with the latter equation above: \begin{align} &\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2\,} - h \, = \, l\sin(\theta)\\ &\frac{\big(x_A + l\cos(\theta)\big)}{\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2}}\left(l\sin(\theta)\frac{d\theta}{dt} \, - \, \frac{dx_A}{dt}\right) \, = \, l\cos(\theta) \frac{d\theta}{dt} \end{align} You can simplify the second equation, using the first one, by solving for the square root $$\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2}$$ and write the system as follows: \begin{align} &\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2\,} - h \, = \, l\sin(\theta)\\ &\frac{\, x_A + l\cos(\theta)\,}{h \, + \, l\sin(\theta)}\left(l\sin(\theta)\frac{d\theta}{dt} \, - \, \frac{dx_A}{dt}\right) \, = \, l\cos(\theta) \frac{d\theta}{dt} \end{align} This system of equations features four variables: $$x_A, \, \theta, \, \frac{dx_A}{dt}, \, \frac{d\theta}{dt}$$ So, if you are given any two of these, you can solve the system and find the other two. For example, if you know the position and velocity of $$A$$, then you know $$x_A$$ and $$\frac{dx_A}{dt}$$. Then, you can plug $$x_A$$ in the first equation and solve that same first equation for $$\theta$$. Then, knowing already $$x_A, \, \theta, \, \frac{dx_A}{dt}$$, you can plug these three values in the second equation and solve it for the angular velocity $$\frac{d\theta}{dt}$$. This second equation is easier to solve with respect to $$\frac{d\theta}{dt}$$ because it is linear with respect to $$\frac{d\theta}{dt}$$.

The next step is to find the linear velocity of $$B$$, which should be tangent to the circle. If you take the equations \begin{align} &{x}_B = x_A + l\, \cos(\theta)\\ &{y}_B = \sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2} \end{align} By the first equation from the system of equations discussed above, you can express $$\sqrt{r^2 - \big(x_A + l\, \cos(\theta)\big)^2} = l\sin(\theta) + h$$ and re-write the latter parametrization as follows: \begin{align} &{x}_B = x_A + l\, \cos(\theta)\\ &{y}_B = l\sin(\theta) + h \end{align} To find the linear velocity of $$B$$, you just have to differentiate the latter parametrization with respect to $$t$$ \begin{align} &\frac{dx_B}{dt} = \frac{dx_A}{dt} - l\, \sin(\theta)\frac{d\theta}{dt}\\ &\frac{dy_B}{dt} = l \, \cos(\theta)\frac{d\theta}{dt} \end{align}
plug the already determined values of $$\frac{dx_A}{dt}, \, \theta, \, \frac{d\theta}{dt}$$.

You are very close to the solution. What you need to consider is that the velocity of each point on the curved path, has to be tangent to the curve. I.e. the velocity of point A plus the $$V_{A|B}$$, needs to have the same direction with the tangent at point B.

So what you need to do is:

• calculate the tangent to the curved path at point B
• express all velocities in the problems in the same frame of reference (XY, or xy). Preferably the latter xy.
• solve the system of the velocities:

e.g. if you select xy system then you should have $$\begin{bmatrix} V_{Bx}\\V_{By} \\0 \end{bmatrix} =\begin{bmatrix} V_{Ax}\\ 0\\ 0 \end{bmatrix} + \begin{bmatrix} 0\\ 0\\ \dot{\theta} \end{bmatrix} \times \begin{bmatrix} I \cos\theta\\ I\sin\theta\\ 0 \end{bmatrix}$$

This reduces to:

$$\begin{bmatrix} V_{Bx}\\V_{By} \end{bmatrix} =\begin{bmatrix} V_{Ax}\\ 0 \end{bmatrix} + \begin{bmatrix} -\dot{\theta}I\sin\theta \\ \dot{\theta}I \cos\theta \end{bmatrix}$$

The above can be solved if you keep in mind the constraint about the direction of the tangent to the curved path (lets denote it $$\phi$$), i.e. $$\tan\phi = \frac{V_{By}}{V_{Bx}}$$.


text:
# Binary sequences and ${2}^{\mathbb{N}}$ have the same cardinality

I recently got the book "selected problems in real analysis", and I'm stuck solving the very first problem

$(u_n)$ is a binary sequence iff it only contains $0$ and $1$ in the sequence

Let $A$ be the set of all binary sequences

I have to prove that $A$ and ${2}^{\mathbb{N}}$ have the same cardinality, that is to say there exists a 1-1 function from one set to another

I've thought about maybe considering integers as base-2 numbers

• This has nothing to do with base two numbers. Imagine you are given a subset $S$ of $\mathbb N$. What 0-1 sequence (i.e. map $\mathbb N\to\{0,1\}$) can you define by making use of $S$ in the most natural way? – Hagen von Eitzen Apr 21 '13 at 12:59
• $0$ if n is even, $1$ if n is odd ? – Gabriel Romon Apr 21 '13 at 13:02
• @Gabriel: That has nothing in particular to do with $S$, though. – Cameron Buie Apr 21 '13 at 13:10

Hint: By $2^{\Bbb N}$ I presume you mean the power set of $\Bbb N$, rather than the set of functions $\Bbb N\to\mathbf{2},$ where $\mathbf{2}:=\{0,1\}$, as these are precisely the binary sequences, and there's nothing to prove. Have you heard of indicator functions?
• thanks, the function that to a subset $S$ associates the indicator of every integer toward $S$ should do. – Gabriel Romon Apr 21 '13 at 13:32
• If I understand you correctly, that will indeed be a bijection from $2^{\Bbb N}$ to the set of functions $\Bbb N\to\mathbf{2}.$ – Cameron Buie Apr 21 '13 at 15:51
• I don't know what you mean by "the indicator of every integer toward $S$." For any $S\subseteq\Bbb N$, the indicator function of $S$ is the function $\mathbf{1}_S:\Bbb N\to\{0,1\},$ given by $$\mathbf{1}_S(n)=\begin{cases}0 & n\notin S\\1 & n\in S.\end{cases}$$ that is, $\langle\mathbf{1}_S(n)\rangle_{n\in\Bbb N}$ is a binary sequence for each $S\in2^{\Bbb N}$. Your job is to show that the map $S\mapsto\langle\mathbf{1}_S(n)\rangle_{n\in\Bbb N}$ is a bijection from $2^{\Bbb N}$ to the set of binary sequences. – Cameron Buie Apr 21 '13 at 19:41
• Let $S$ be a subset of $\mathbb {N}$ Let $f:P(\mathbb {N}) \rightarrow A$ where $A$ is set of all binary sequences such that: $\forall i\in \mathbb {N}, (f(S)_i=0$ if $i\in S$ or$f(S)_i=1$ if $i\notin S$) – Gabriel Romon Apr 22 '13 at 15:29

format: plain


text:
# Tag Info

75

This is a great question to answer graphically. First note that the two can't arrive after 12:45, since they have to spend at least 15 minutes in the bar. Second, note that they meet if their arrival times differ by less than 15 minutes. If we plot the arrival time of person 1 on the x axis, and person 2 on the y axis, then they meet if the point ...

66

As has been noted, the usual definition of the Lebesgue integral has little to do with probability or random variables (though the notions of measure theory and the integral can then be applied to the setting of probability, where under suitable interpretations it will turn out that the (Lebesgue) integral of (a certain) functions corresponds to the ...

61

$$\text{chance they meet} = \frac{\text{green area}}{\text{green area + blue area}} = \frac{45^2 - 30^2}{45^2}$$

54

This problem, known as the Monty Hall problem, is famous for being so bizarre and counter-intuitive. It is in fact best to switch doors, and this is not hard to prove either. In my opinion, the reason it seems so bizarre the first time one (including me) encounters it is that humans are simply bad at thinking about probability. What follows is essentially ...

49

Maybe this simple example will help. I use it when I teach conditional expectation. (1) The first step is to think of ${\mathbb E}(X)$ in a new way: as the best estimate for the value of a random variable $X$ in the absence of any information. To minimize the squared error $${\mathbb E}[(X-e)^2]={\mathbb E}[X^2-2eX+e^2]={\mathbb E}(X^2)-2e{\mathbb ... 49 I haven't quite got this straight yet, but I think one way to go is to think about choosing points at random from the positive reals. This answer is going to rather longer than it really needs to be, because I'm thinking about this in a few (closely related) ways, which probably aren't all necessary, and you can decide to reject the uninteresting parts and ... 38 For non-negative integers a, b and t \in [0, 1], the expression t^a (1 - t)^b describes the probability of randomly selecting a+b real numbers in [0, 1] such that the first a are in [0, t] and the last b are in [t, 1]. The integral \int_0^{1} t^a (1 - t)^b dt then describes the probability of randomly selecting a+b+1 real numbers such ... 37 Hint: The probability that an equal number of tails and heads appear is \large{{2k \choose k} \frac{1}{2^{2k}}} The two remaining outcomes (that there are more heads than tails or more tails than heads) are equally likely. 35 The simplest and surest way to compute the distribution density or probability of a random variable is often to compute the means of functions of this random variable. In the case at hand, one wants to write \mathrm E(g(W)) as$$ \color{blue}{\mathrm E(g(W))=\int g(w)f(w)\mathrm{d}w}, $$for every bounded measurable function g, then one can be sure that ... 34 (This answer takes as its starting point the OP's question in the comments, "Let me understand mass before going to density. Why do we call a point in the discrete distribution as mass? Why can't we just call it a point?") We could certainly call it a point. The utility of the term "probability mass function," though, is that it tells us something about ... 33 To understand why your odds increase by changing door let us take an extreme example first. Say there are 10000 doors. Behind one of them is a car and behind the rest are donkeys. Now, the odds of choosing a car is 1\over10000 and the odds of choosing a donkey are 9999\over10000. Say you pick a random door which we call X for now. According to the ... 29 The geometric approach works. Let’s compute the volume of the 2n dimensional ball, D^{2n}, in two ways. One way is extremely clever but has been known for centuries and provides interesting insights: it’s based on Liouville’s trick. Specifically, we will compute two integrals in polar coordinates, one of which is the volume of the ball and the other ... 27 I think this is a slightly more intuitive way of looking at the question: Suppose f (x)=k. Once we have chosen k, there are 200 possible values for g (x), one of which is k, hence we get an answer of \frac{1}{200}. 26 See Durrett, Probability: Theory and Examples (link goes to online copy of the fourth edition). On p. 164 Durrett gives a proof that simple random walk is recurrent in two dimensions. First find the probability that simple random walk in one dimension is at 0 after 2n steps; this is clearly \rho_1(2n) = \binom{2n}{n}/2^{2n}, since \binom{2n}{n} is ... 24 Let's say the \sigma-algebra on X is generated by the sets A_i \subseteq X. For each subset I of the natural numbers, consider the set B_I = \bigcap_{i \in I} A_i \cap \bigcap_{i \notin I} (X \setminus A_i). For distinct sets I and J, the corresponding sets B_I and B_J are disjoint. Now take cases: either only finitely many of the B_I ... 23 For probability theory as probability theory (rather than normed measure theory ala Kolmogorov) I'm quite partial to Jaynes's Probability Theory: The Logic of Science. It's fantastic at building intuition behind the rules and operations. That said, this has the downside of creating fanatics who think they know all there is to know about probability theory. ... 22 A Markov chain is a discrete random process with the property that the next state depends only on the current state (wikipedia) So P(X_n | X_1, X_2, \ldots X_n-1) = P(X_n | X_{n-1}). An example could be when you are modelling the weather. You then can take the assumption that the weather of today can be predicted by only using the knowledge of ... 22 Here are some asymptotics for the first part: Claim For every fixed m, the random variable$$ S_n^m = T_{n}^m - \log n - (m-1) \log\log n+\log((m-1)!) $$converges in distribution to the "extreme value" distribution independent of m given by$$ F_{S_\infty}(s) = \exp\left(-\mathrm e^{-s}\right). $$Proof For frog j and t\ge 0, let ... 21 Given: (X,Y) is Uniformly distributed on a disc of unit radius. Then, the joint distribution of n such points, ((X_1,Y_1), ..., (X_n,Y_n)), each drawn independently, will have joint pdf:$$f( (x_1,y_1), ..., (x_n,y_n) ) = \begin{cases}\pi^{-n}& (x_1^2 + y_1^2 < 1) & \text{ & } \cdots \text{ & }&(x_n^2 + y_n^2 < 1) \\ 0 ...

21

This only holds if $X$ and $Y$ are independent, so we suppose this from now on. We have for $k \ge 0$: \begin{align*} P(X+ Y =k) &= \sum_{i = 0}^k P(X+ Y = k, X = i)\\ &= \sum_{i=0}^k P(Y = k-i , X =i)\\ &= \sum_{i=0}^k P(Y = k-i)P(X=i)\\ &= \sum_{i=0}^k e^{-\mu}\frac{\mu^{k-i}}{(k-i)!}e^{-\lambda}\frac{\lambda^i}{i!}\\ ...

20

There's a nice approach in Coverage by Randomly Deployed Wireless Sensor Networks by Wan and Yi that allows us to get an expansion in $\mu:=R/r$ for the expected number of raindrops required. The basic idea is to focus on the intersections among the circles. Since any uncovered area must be bounded by arcs bounded by intersections that aren't covered by ...

18

Gambling is a good starting-point for probability. We can treat $\sigma$-field as a structure of events as we need to define the addition and multiplication for numbers. The completeness of the real numbers is suitable for our calculations, and $\sigma$-field plays the same role. I hope the following gambling example helps you to understand the filtration ...

18

I have uploaded KCd's translation of the questions for year 5 and my translation of the questions for years 6-8 here. Please let me know if anything is unclear.

18

Consider the compact metric space $(A,d)$ where $A$ is the set of binary sequences with metric $$d(a,b) = \sum_{n=1}^{\infty} \frac{ |a_i - b_i|}{2^n}.$$ Define $f:A\to [0,x]$ by $f(a) = \displaystyle \sum_{n=1}^{\infty} a_n x_n.$ Then $f$ is continuous so $f(A)=X$ is compact.

17

Consider $$f(x)=\begin{cases}0&\text{if }x<0\\1&\text{if }x\ge 0\end{cases}$$ Any continuous $g$ with $||f-g||_\infty<\frac 13$ must have $g(x)<f(x)+\frac13=\frac13$ for all $x<0$. By countinuity, $g(0)\le \frac13$, contradicting $g(0)>f(0)-\frac13=\frac 23$. Even if we only require $|f(x)-g(x)|<\frac13$ for almost all $x$, the ...

16

The range of an $n$-dimensional vector measure is always closed. See the paper (and references therein) P. R. Halmos (1948), The range of a vector measure, Bull. Amer. Math. Soc. 54, 416–421. So the set will always be closed.

16

Uniqueness does not hold in general. Besides the usual product measure of two measure spaces $(X,\mathfrak{M},\mu)$ and $(Y,\mathfrak{N},\nu)$, there is a different version of the product measure, called the complete locally determined product. For products of non-$\sigma$-finite measure spaces it has many desirable properties that the usual product measure ...

16

I think a good way to answer question 2 is as follows. I am performing an experiment, whose outcome can be described by an element $\omega$ of some set $\Omega$. I am not going to tell you the outcome, but I will allow you to ask certain questions yes/no questions about it. (This is like "20 questions", but infinite sequences of questions will be allowed, ...

16

The problem arises in the countable union; your argument is correct as far as it goes, but from the fact that $\cup_{i=1}^n x_i\in \cup_{i=1}^{\infty}F_i$ for each $n$ you cannot conclude that $\cup_{i=1}^{\infty} x_i$ lies in $\cup_{i=1}^{\infty} F_i$: the full union must be in one of the $F_j$ in order to be in $\cup_{i=1}^{\infty}F_i$. For an explicit ...

15

I'd say that each of them arrives at some time uniformly distributed on [12:00, 12:45], where the times are independent. They meet if their arrival times differ by less than fifteen minutes. In the interest of not having annoying numbers all over the place, measure time in units of fifteen minutes, starting at noon. Let the first person's arrival time be ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
## Negative Paneitz constant on $n$-sphere

Let $\Pi$ be the Riemannian functional defined on the space of Riemannian metrics on $S^n$, $n>4$, as follows: $$\Pi(g) = \int_M \frac{(n-4)(n^3-4n^2+16n-16)}{16(n-1)^2(n-2)^2} R_g^2 - \frac{2(n-4)}{(n-2)^2} |Ric_g|^2 dv_g.$$ Here $R_g$ is the scalar curvature, and $|Ric_g|$ is the norm of the Ricci tensor. This functional is sometimes referred to as the Paneitz functional. It is of great interest to conformal differential geometers, because of its connection to $Q$-curvature. The coefficients, which are functions of the dimension, are positive if $n>4$ (here I am not including the negative sign as part of the coefficient). The reason the coefficients are strange in appearence is that they are carefully constructed so that the $Q$-curvature has nice conformal properties.

Since there will be a scalar flat metric on $S^n$ it is known that $\Pi$ obtains a non-positive value on the space of Riemannian metrics on $S^n$, $n>4$. Can you show that it takes on negative values on the space of Riemannian metrics on $S^n$ as well? Note, this would trivially follow from the existence of a scalar flat metric on $S^n$, $n>4$, that was not Ricci flat. Note as well that all Einstein metrics will return a non-negative value.

-
For those of you interested in conformal differential geometry, the above integral is the total $Q$-curvature of the manifold. Hence, we are asking if there exists a metric on $S^n$ that has a negative average value of $Q$-curvature. – Viktor Bundle Jun 20 2011 at 0:46
That's a pretty amazing normalization factor! :) – Mariano Suárez-Alvarez Jun 20 2011 at 1:51
Mariano: The coefficients seem baffling because they are at specific value that provide nice conformal properties for $Q$-curvature. Interestingly enough, there is one other combination of constants that has this property. – Viktor Bundle Jun 20 2011 at 2:17
Anton: that is correct. I'll edit the post to make that clear. – Viktor Bundle Jun 20 2011 at 14:34


text:
The number of values of k for which the equation x3−3x+k=0 has two distinct roots lying in the interval (0,1) are

# The number of values of k for which the equation ${x}^{3}-3x+k=0$ has two distinct roots lying in the interval $\left(0,1\right)$ are

1. A
2. B
3. C
4. D

Register to Get Free Mock Test and Study Material

+91

Verify OTP Code (required)

### Solution:

Let there be a value of k for which ${x}^{3}-3x+k=0$

has two distinct roots between 0 and 1.

Let $a,b$ be two distinct roots of ${x}^{3}-3x+k=0$ lying between 0 and 1 such that $a

Let $f\left(x\right)={x}^{3}-3x+k\text{.}$Then

Between any two roots of a polynomial  there exists at least one roots of its derivative  Therefore,has at least one root between a and b. But, $f\text{'}\left(x\right)=0$ has two roots equal to± 1 which do not lie between a and b. Hence, $f\left(x\right)=0$ has no real roots lying between 0 and 1 for any value of

Register to Get Free Mock Test and Study Material

+91

Verify OTP Code (required)


text:
# Simplification of Fractions – Definition, Facts, Examples | How to Simplify Fractions Step by Step?

Get detailed information regarding the simplifaction of fractions here. Check all the important terms, formulae, and the usage of simplifying fractions. Refer step by step procedure to simplify the fraction problems. Know the various methods used to simplify proper, improper, mixed fractions, etc. Go through the below sections to follow the importance and problems of division on fractions.

## What are Fractions?

A fraction number is considered as the ratio between any two numbers. Fractions are usually represented as $$\frac {m}{n}$$ where m is called the numerator which means the equal number of parts that are counted and n is called the denominator which means a number of parts in the whole.

Example $$\frac {1}{2}$$ is a fractional number, 1 is the numerator and 2 is the denominator, in a whole of 2 parts we are counting 1 part.

### What is Simplification of Fractions?

Simplification of fractions means converting a given fractional number to its lowest terms until it is divided by only 1. In other words, any given fractional number is said to be in its simplest form if it is having 1 as the only common factor if its numerator and denominator are only divided by 1.

### How to do Simplification of Fractions?

For example, $$\frac {8}{9}$$, is said to be in its simplest form because 1 is the only common factor of 8 and 9.

If we consider $$\frac {2}{4}$$, this fractional number can be further simplifed as $$\frac {1}{2}$$ as we know 2 and 4 can be divided by 2. After simplifing $$\frac {1}{2}$$ is in its lowest terms and 1 is the only common factor of 1 and 2.

### Simplification of Fractions Examples

Now that we know what is meant by simplification of fractions and how it is done, let us see few examples for simplifying proper and improper fractions

Example 1:
Simplify $$\frac {7}{16}$$?
Solution:
Now let’s see what are the factors of numerator 7 = 1, 7
And factors of denominator 16 = 1, 2, 4, 8, 16
Now, we can see that 1 is the only common factor for 7 and 16
So given fractional number $$\frac {7}{16}$$ can’t be simplified any further.
Therefore, $$\frac {7}{16}$$ is in its simplest form.

Example 2: Simplify $$\frac {12}{20}$$
Solution:
Now let’s see what are the factors of numerator 12 = 1, 2, 3, 4, 6, 12
And factors of denominator 20 = 1, 2, 4, 5, 10, 20
Now, we can see that 1 is not the only common factor for 12 and 20
So given fractional number $$\frac {12}{20}$$ can be simplified as $$\frac {6}{10}$$
Factors of numerator 6 = 1, 2, 3, 6
Factors of denominator 10 = 1, 2, 5, 10
1 is not the only common factor for 6 and 10
Which means fractional number $$\frac {6}{10}$$ can be simplified as $$\frac {3}{5}$$
Factors of numerator 3 = 1, 3
Factors of denominator 5 = 1, 5,
Now we can see 1 is the only common factor for 6 and 10
So fractional number $$\frac {3}{5}$$ can’t be simplified any further.
Therefore, the simplest form for $$\frac {12}{20}$$ is $$\frac {3}{5}$$.

### Simplification of Mixed Fractions

Let us try to simplify few examples on a mixed fractional number.

Example 3: Simply 2$$\frac { 9 }{ 13 }$$.
Solution:
To simply a given mixed fraction first we need to convert it into a proper or improper fraction.
Now mixed fraction 2$$\frac { 9 }{ 13 }$$ can be converted as $$\frac { 35 }{ 13 }$$
Let’s see what are the factors of numerator 35 = 1, 5, 7, 35
And factors of denominator 13 = 1, 13
Now, we can see that 1 is the only common factor for 35 and 13.
So fractional number $$\frac {35}{13}$$ can’t be simplified any further.
Therefore, 2$$\frac {9}{13}$$ is in its simplest form.

Example 4: Simply 2$$\frac { 2 }{ 3 }$$.
Solution:
To simply a given mixed fraction first we need to convert it into a proper or improper fraction.
Now mixed fraction 2$$\frac { 2 }{ 3 }$$ can be converted as $$\frac { 8 }{ 3 }$$
Let’s see what are the factors of numerator 8 = 1, 2, 4, 8
And factors of denominator 3 = 1, 3
Now, we can see that 1 is the only common factor for 8 and 3.
So fractional number $$\frac {8}{3}$$ can’t be simplified any further.
Therefore, 2$$\frac {2}{3}$$ is in its simplest form.

#### FAQs on Simplification of Fractions

1. When is a fraction said to be simplified?
A fraction is said to be simplified when it is in its lowest terms and can not be divided any further.

2. How do you know when a fraction is simplified?
A fraction is said to be fully simplified when it can be further divided into whole numbers.

3. What are the fraction that can not be simplified?
If the numerator and denominator of a fraction are only having 1 as their common factor then those fractional numbers can not be simplified.

4. What is mean by the reduction of a fraction number?
The reduction of a fraction number is nothing but simplifying it into its lowest terms.

Scroll to Top


text:
My watch list
my.chemeurope.com

# Brønsted catalysis equation

The Brønsted catalysis equation or law or correlation, after Johannes Nicolaus Brønsted, gives the relationship between acid strength and catalytic activity.

$\ log(k) = \alpha*log(K_a) + C$

A plot of the common logarithm of the reaction rate constant k versus the logarithm of the ionization constant Ka for a series of acids (for example a group of substituted phenols or carboxylic acids) gives a straight line with slope α and intercept C. The Brønsted equation is a free-energy relationship. The relationship implies that the Gibbs free energy for proton dissociation is proportional to the activation energy for the catalytic step. When the relationship is not linear, the chosen group of catalysts do not operate through the same reaction mechanism.

Specific and general catalysis is also found in base catalysed reactions and base Brønsted equation also exists with constant β.

The Brønsted equation gives information about a reaction mechanism. Reactions that have low values for proportionality constants α or β are considered to have a transition state closely resembling the reactant with little proton transfer. With a high value, proton transfer in the transition state is almost complete. In a study of a group of phenalene compounds it was concluded from Brønsted analysis that phenalene acidity is very different from either indene acidity or phenylene acidity 1.

## References

• 1 The Brønsted correlation for phenalene hydrocarbons Andrew Streitwieser, Michael J. Kaufman, Daniel A. Bors, Craig A. MacArthur, James T. Murphy, and Francois Guibé Arkivoc (EJ-1384C) pp 200-210 full article open access publication


text:
This quarter, in my advanced algorithms class, I've been going through Vazirani's Approximation Algorithms book chapter-by-chapter, and learning lots of interesting material that I didn't already know myself in the process.

One of the things I recently learned (in covering chapter 6 on feedback vertex set approximation)* is that, although all the students have taken some form of linear algebra, many of them have never seen a vector space in which the base field is not the real numbers or in which the elements of the vector space are not tuples of real coordinates. So instead of discussing the details of that algorithm I ended up spending much of the lecture reviewing the theory of binary vector spaces. These are very important in algebraic graph theory, so I thought it might be helpful to write a very gentle introduction to this material here.

First of all we need the concept of a field. This is just a system of elements in which we can perform the usual arithmetic operations (addition, subtraction, multiplication, and division) and expect them to behave like the familiar real number arithmetic: addition and multiplication are associative and commutative, there are special values 0 and 1 that are the identities for addition and multiplication respectively, subtraction is inverse to addition, division is inverse to multiplication by anything other than zero, and multiplication distributes over addition. The field that's important for this material is a particularly simple one, GF(2), in which the required special values 0 and 1 are the only elements. The arithmetic of these two values can be described as ordinary integer arithmetic mod 2, or equivalently it can be described by saying that addition is Boolean xor and multiplication is Boolean and. Subtraction turns out to be the same as addition, and division by 1 (the only value that it's possible to divide by) is just the identity operation. It's not hard to verify that these operations have all the desired properties of a field, and doing so maybe makes a useful exercise (Exercise 1).

Next, a vector space is a collection of elements that can be added to each other and multiplied by scalars from a field. (One can generalize the same concept to other kinds of arithmetic than fields but then one gets modules instead of vector spaces.) The vector addition operation must be commutative and invertible; this implies that it has an identity element, and this element (whatever it happens to be) is called the zero vector. Additionally, scalar-scalar-vector multiplications must be associative, scalar multiplication by the special element 1 of the field must be the identity operation, and scalar multiplication must be distributive over both vector and field addition.

One easy way to construct vector spaces over a field $$\mathbb{F}$$ is to make its elements be $$k$$-tuples of elements of $$\mathbb{F}$$ with the addition and scalar multiplication operations acting independently on each coordinate, but it's not the only way. For the vector spaces used in this chapter, a different construction is more natural: we let the elements of the vector space be sets in some family of sets, and the vector addition operation be the symmetric difference of sets. The symmetric difference $$S \bigtriangleup T$$ of two sets $$S$$ and $$T$$ is the set of elements that occur in one but not both of $$S$$ and $$T.$$ This operation is associative, commutative, and invertible, where the inverse of a set is the same set itself: $$S \bigtriangleup T \bigtriangleup T = S$$ regardless of which order you use to perform the symmetric difference operations. If a nonempty family of sets has the property that the symmetric difference of every two sets in the family stays in the family, then these sets can be interpreted as the elements of a vector space over GF(2) in which the vector addition operation is symmetric difference, the zero vector is the empty set (necessarily in the family because it's the symmetric difference of any other set with itself), scalar multiplication by 0 takes every set to the empty set, and scalar multiplication by 1 takes every set to itself. One has to verify that these addition and multiplication operations are distributive, but again this is a not-very-difficult exercise (Exercise 2).

As with other kinds of vector spaces, these vector spaces of sets have bases, collections of vectors such that everything in the vector space has a unique representation as a sum of scalar products of basis vectors. Every two bases have the same number of vectors as each other (Exercise 3: prove this), and this number is called the dimension of the vector space. If the dimension is $$d,$$ the total number of vectors in the vector space is always exactly $$2^d,$$ because that is the number of different ways that you can choose a scalar multiple (0 or 1) for each basis vector.

The families of sets that are needed for this chapter are subsets of edges of a given undirected graph. These can also be interpreted as subgraphs of the graph, but they're not quite the same because the usual definition of a subgraph also allows you to specify a subset of the vertices (as long as all edges in the edge subset have endpoints in the vertex subset), and we won't be doing that. Every graph has three important vector spaces of this type associated with it, the edge space, the cycle space, and the cut space. The edge space is the family of all subsets of edges (including the set of all edges of the given graph and the empty set). That is, it is the power set of the set of all edges; it has a natural basis in which the basis vectors are the one-edge sets, and its dimension is the number of edges in the graph.

The cycle space is the family of all subsets of edges that have even degree at all of the vertices of the graph (Exercise 4: prove that this family is closed under symmetric difference operations). So it includes the simple cycles of the graph, but it also includes other subgraphs; for instance in the graph of an octahedron (a six-vertex graph with four edges at each vertex) the set of all edges is in the cycle space, as are the sets of edges formed by pairs of triangles that touch each other at a single vertex and the sets complementary to triangles or 4-cycles. It's always possible to find a basis for the cycle space in which the basis elements are themselves simple cycles; such a basis is called a cycle basis. For instance you can form a "fundamental cycle basis" by choosing a spanning forest of the given graph and then finding all cycles that have one edge $$e$$ outside this forest and that include also the edges of the unique path in the forest that connects the endpoints of $$e.$$ Or, for a planar graph, you can form a cycle basis by choosing one cycle for each bounded face of a planar embedding of the graph. There are lots of interesting algorithmic problems associated with the cycle space and its cycle bases, but for this chapter the main thing that's needed is to compute its dimension, which has the nice formula $$|E|-|V|+c,$$ where $$E$$ is the edge set of the given graph, $$V$$ is the vertex set, and $$c$$ is the number of connected components. One name for this dimension is the cyclomatic number of the graph, and the book chapter denotes it as $$\operatorname{cyc}(G).$$ (It's also possible to interpret it topologically as the first Betti number of the graph but for students who don't already know about binary vector spaces that would probably be more confusing than helpful.)

The cut space of the graph doesn't take part in this chapter, but can be defined similarly as the set of all cut-sets of the graph. A cut of a graph is a partition of its vertices into two disjoint subsets; in some contexts we require the subsets to both be nonempty but we don't do that here, so the partition into an empty set and the set of all vertices is one of the allowed cuts. The corresponding cut-set is the set of edges that have one endpoint in each of the two subsets. The family of cut-sets is closed under symmetric difference (Exercise 5) so it forms a vector space, the edge space. If the edges are all given positive weights and the graph is connected, then the minimum weight basis of the edge space can be represented by a tree on the vertices of the graph, in which each tree edge determines a cut (the partition of the tree into two subtrees formed by deleting that edges) and has an associated number (the weight of its cut). This tree is called the Gomory–Hu tree of the graph and it came up (stripped of its linear-algebra origin) earlier, in an approximation for $$k$$-cuts in chapter 4. I also have a recent preprint on computing this basis and this tree for graphs that can be embedded onto low-genus surfaces: see arXiv:1411.7055.

*Unrelatedly, in preparing to cover this topic, I was confused for a long time by a typo in this chapter. On page 56 it states that, for a minimal feedback set, "clearly" the sum over feedback vertices of the number of components formed by deleting that one vertex equals the number of feedback vertices plus the number of components that are formed by deleting the whole feedback set but that touch only one vertex in the set. This is not true. What is true, and what is needed for the later argument, is that the left hand side is greater than or equal to the right hand side.

None:
2015-01-22T23:59:47Z
At this stage a gentle introduction to Matroid theory may be mentioned and interested students can look up the topic and read more.
11011110:
2015-01-23T00:05:43Z
Matroid theory is also relevant (especially in the algorithms for finding minimum weight bases for these spaces) but if I'd tried including that as well I wouldn't have had time for any of the approximation algorithms.
asher63:
2015-01-23T01:25:30Z
This is mostly way over my level, but it's interesting. I remember learning the definition of a field in cryptography, where they're useful for modular arithmetic and discrete logarithms. I'm taking beginning linear algebra now, so that aspect of it caught my eye as well.
11011110:
2015-01-23T08:15:37Z
Linear algebra over GF(2) is also important in crypto, for instance in the Gaussian elimination stages of the quadratic sieve and general number field sieve. In those cases the sets that you're treating as vectors are sets of prime factors that occur an odd number of times in a relation, and multiplying two relations corresponds to taking symmetric differences of these sets.
mathsandcrafts:
2015-01-23T07:47:04Z
It is nice to see that CS students can digest math. I admire the way you serve it too.
11011110:
2015-01-23T08:19:00Z
You say that as if you weren't once a CS student...anyway, thanks. And happy birthday Saturday!
mathsandcrafts:
2015-01-23T09:28:53Z
My master's was in maths. Thanks! CS students at TU/e needed a calculator to evaluate whether log x for a given x was above 1. So CS students who can do linear algebra seem almost SF.


text:
# Symmetric function of two normal distribution implies bilinear

This question is related to my previous question which was partially answered my @MichaelHardy.

Let $X$ and $Y$ be two independent standard normal random variables. Now, suppose that $g:\mathbb{R}^2\mapsto \mathbb{R}$ is a symmetric smooth function such that $g(X,Y)$ is normally distributed. Intuitively, $g$ should be in the form $g(X,Y)=a(X+Y)+b$ for some $a,b\in \mathbb{R}$ since the other "algebraic operations" except sum will never give normal distribution again. However, how will we prove this conjecture precisely?

• With symmetric you mean that $g(x,y)=g(y,x)$, right? – Bernhard Aug 3 '15 at 11:46
• @Bernhard: Yes, exactly. – Jlamprong Aug 3 '15 at 11:47

The product $X\cdot Y$ has a product normal distribution with cumulative distribution function $F_{PN}$. Hence, as a consequence, $F_{PN}(X\cdot Y)$ has a uniform distribution by the Inverse Transform Sampling Method. Similarly, if $Z$ has normal distribution with cumulative distribution function $F_N$, then $F_N(Z)$ has a uniform distribution. Hence, $F_N^{-1}(F_{PN}(X\cdot Y))$ has normal distribution, too.


text:
Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-001 | 1st January 2021 21:37

#### Computation Over the Noisy Broadcast Channel with Malicious Parties

TR21-001
Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Publication: 3rd January 2021 23:04
Keywords:

Abstract:

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed?

Assuming there are no malicious parties, Gallager gave an $\mathcal{O}(n \log \log n)$-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties.

We present a novel $n \cdot \tilde{\mathcal{O}}\left(\sqrt{\log n}\right)$-round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map "close" messages to "close" codewords, while messages that are not close are mapped to codewords that are very far apart.

We view our result as a first step towards a theory of property preserving interactive coding, i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager's, preserves this property of the original protocol.

ISSN 1433-8092 | Imprint


text:
# Writing Expressions in the Form $kx^n$

Note: When you're looking at the math, then:

• $\,(3x)^2\,$ is most easily read aloud as: ‘three ex, (slight pause), squared’
• $\,3x^2\,$ is most easily read aloud as: ‘three, (very slight pause), ex squared’

In the audio for this lesson, some pauses are over-emphasized to help you hear them!

## Examples

Question: Write $\,(3x)^2\,$ in the form $\,kx^n\,.$

Solution:
$(3x)^2 = 3^2x^2 = 9x^2\,$
or
\cssId{s10}{\begin{align} (3x)^2 &= (3x)(3x)\cr &= (3\cdot 3)(x\cdot x)\cr &= 9x^2 \end{align}}

Question: Write $\,(2x)^3\,$ in the form $\,kx^n\,.$

Solution:
$(2x)^3 = 2^3x^3 = 8x^3\,$
or
\cssId{s16}{\begin{align} (2x)^3 &= (2x)(2x)(2x)\cr &= (2\cdot 2\cdot 2)(x\cdot x\cdot x)\cr &= 8x^3 \end{align}}

Question: Write $\,(-3x)^2\,$ in the form $\,kx^n\,.$

Solution:
$(-3x)^2 = (-3)^2x^2 = 9x^2\,$
or
\cssId{s22}{\begin{align} (-3x)^2 &= (-3x)(-3x)\cr &= (-3\cdot -3)(x\cdot x)\cr &= 9x^2 \end{align}}

For mental math, the following thought process can be used:

• It's a negative number to an even power; so, the answer will be positive.
• What's the size of the answer?   $3^2 = 9$
• What's the variable part?   $x^2$
• Put it together to get $\,9x^2\,.$

Question: Write $\,(-2x)^3\,$ in the form $\,kx^n\,.$

Solution:
$(-2x)^3 = (-2)^3x^3 = -8x^3\,$
or
\cssId{s33}{\begin{align} (-2x)^3 &= (-2x)(-2x)(-2x)\cr &= (-2\cdot -2\cdot -2)(x\cdot x\cdot x)\cr &= -8x^3 \end{align}}

For mental math, the following thought process can be used:

• It's a negative number to an odd power; so, the answer will be negative.
• What's the size of the answer?   $2^3 = 8$
• What's the variable part?   $x^3$
• Put it together to get $\,-8x^3\,.$

$$\cssId{s40}{2^5 = 32}$$ $$\cssId{s41}{3^4 = 81}$$ $$\cssId{s42}{3^5 = 243}$$ $$\cssId{s43}{4^3 = 64}$$ $$\cssId{s44}{5^3 = 125}$$
Input the exponent using the  ‘ ^ ’  key:  on my keyboard, it is above the $\,6\,$.
 Write in the form $\,kx^n\,$:


text:
Evaluating the limit

Evaluate the limit $$\lim_{n\to+\infty}(\sqrt[n]{n}-1)^n$$

I know the limit is 0 by looking at the graph of the function, but how can I algebraically show that that is the limit?

-
Showing $\sqrt[n]{n}-1 \to 0$ would be a good start (actually, you need less). –  Daniel Fischer Nov 21 '13 at 14:45

$$a_n:=\left(\sqrt[n]n-1\right)^n\implies\log a_n=n\log\left(\sqrt[n]n-1\right)=-\infty\implies$$

$$\lim_{n\to\infty} a_n=\lim_{n\to\infty}e^{\log a_n}=0$$

-


text:
# Convolution and space-time Fourier transform

#### shekharc

Hi,

I have a general function u(x,y,z,t). Then, (1) what would be the space-time Fourier transform of G⊗(∂nu/∂tn) and (2) would the relation G⊗(∂nu/∂tn) = ∂n(G⊗u)/∂tn hold true? Here, note that the symbol ⊗ represents convolution and G is a function of (x,y,z) only (i.e. it does not depend on time).

Any answer would appreciated. Thanks!!

-Chandra

#### jasonRF

Science Advisor
Gold Member
Chandra,

Most of your question is answered by applying the properties of Fourier transforms, all of which are, for exmaple, at:
http://fourier.eng.hmc.edu/e101/lectures/handout3/node2.html
including the convolution theorem (in link above and in this link: https://en.wikipedia.org/wiki/Convolution_theorem )
and a knowledge of the Fourier transform of a derivative.
would the relation G⊗(∂nu/∂tn) = ∂n(G⊗u)/∂tn hold true?
Here you are essentially asking a question about interchanging differentiation and integration. As an engineer, I typically deal with "nice" functions for which this holds (indeed, I assume it holds!), but it doesn't always hold for any choice of functions. I cannot help you much more than that - sorry!
jason

#### shekharc

Dear Jason,

Thanks for your suggestions. In fact, I was a bit confused because of involvement of both space and time in the Fourier transform. Anyway, I did it (hopefully correctly) by taking Fourier transforms two times; first, I took the transform with respect to space, and then with respect to time. As for the 2nd question, "u" is not a very nice function--it does not converge to zero when x,y,z-->INFINITY. So, currently I am looking at whether I can use generalized Fourier Transforms to deal with it.

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving


text:
# Area bounded by the x-axis and the curve..

Find the area bounded by the $x$ axis and the curve $$y = \frac{(x^2−x−2)}{(x^3+8)}$$ between its points of intersection with the $x$ axis.

So point of intersection are $(-1,2)$ since $$f(y)=0$$ when $x^2-x-2=0$. Not we take integral $$\int^2_{-1} \frac{(x^2−x−2)}{(x^3+8)} \Rightarrow \int \frac{A}{x+2} + \frac{Bx+C}{x^2-2x+4}$$ from here if we solve equation $A=\frac{1}{3} \quad B = \frac{2}{3} C = -\frac{5}{3}$ so $$\int \frac{\frac{1}{3}}{x+2}=\frac{1}{3}ln(x+2)$$

• Seems you are on the right track, the partial fraction decomposition has $A=1/3, B=2/3$, and $C=-5/3$ – SquirtleSquad Jun 8 '16 at 23:20
Concerning the antiderivative, you properly found that $$I=\int \frac{(x^2−x−2)}{x^3+8}dx=\frac{1}{3}\int\frac{dx}{ x+2}+\frac{1}{3}\int\frac{2 x-5}{ x^2-2 x+4}dx$$ The first integral does not make any problem. Now for the second, consider $$J=\int\frac{2 x-5}{ x^2-2 x+4}dx=\int\frac{2 x-2-3}{ x^2-2 x+4}dx=\int\frac{2 x-2}{x^2-2 x+4}dx-3\int\frac{dx}{ x^2-2 x+4}$$ In the first you can recognize $\int\frac{du}u=\log(u)$ and we are left with $$K=\int\frac{dx}{ x^2-2 x+4}=\int\frac{dx}{ x^2-2 x+1+3}=\int\frac{dx}{ (x-1)^2+3}$$ So now change variable $$x-1=\sqrt 3 y\implies x=1+\sqrt 3 y\implies dx=\sqrt 3 dy$$ which makes $$K=\frac 1 {\sqrt 3}\int\frac {dy}{1+y^2}$$ which is well known.
• So the answer is $$\frac{1}{3}ln(x+2)+ \frac{1}{3}ln(x^2-2x+4)- \frac{3}{\sqrt{3}} arctan \frac{x-1}{\sqrt{3}} + C$$ right? – user296169 Jun 9 '16 at 10:27


text:
Cache

Cache ([ kæʃ ], [ kaʃ ]) refers to a fast buffer memory in information technology , which helps to avoid (repeated) access to a slow background medium or costly recalculations. Data that has already been loaded or generated once remain in the cache so that it can be retrieved from it more quickly if required later. Data that will probably be needed soon can also be called up in advance from the background medium and initially made available in the cache ( read-ahead ).

Caches can be designed as a hardware structure (for example as main memory chips ) or software structure (for example as temporary files or reserved storage space ).

Cache is a loan word from English. It has its origin in the French cache , which actually means hiding place . The name illustrates the fact that the cache and its substitute function for the addressed background medium are usually hidden from the user. Anyone who uses the background medium does not need to know the size or functionality of the cache, because the cache is not addressed directly. The user "addresses the background medium", but instead the cache "responds" - exactly in the same way as the background medium would have responded, ie would have delivered data. Because this intermediate unit is invisible, it is also called transparency . In practice, it is a mirrored resource that can be edited / used very quickly on behalf of the original.

If, in addition to the device using the cache, other devices access the background medium, this can lead to inconsistencies . In order to be able to access an identical data image, it is necessary to transfer the changes to the cache to the background medium before access. Cache strategies like write-through or write-back are practical here. In extreme cases, a complete " cache flush " must be carried out.

In addition, the cache may have to be informed that data on the background medium has changed and its content is no longer valid. If the cache logic does not ensure this, the disadvantage arises that changes made in the background medium or in the computer program are not recognized in the meantime. If changes are suspected or to ensure that the current status is taken into account, the user must explicitly initiate a cache update.

Use

The goals when using a cache are to reduce the access time and / or to reduce the number of accesses to a slow background medium. In particular, this means that the use of caches is only worthwhile where the access time also has a significant influence on the overall performance. While the z. B. is the case with the processor cache of most (scalar) microprocessors, it does not apply to vector computers , where the access time plays a subordinate role. That is why caches are usually not used there because they are of little or no use.

Another important effect when using caches is the reduction of the necessary data transfer rate to the connection of the background medium (see e.g. memory hierarchy ); the background medium can therefore be connected “more slowly”. B. can result in lower costs. Because the majority of queries can often be answered by the cache ("cache hit", see below), the number of accesses and thus the necessary transmission bandwidth decrease . For example, a modern microprocessor without a cache, even with a very short main memory access time, would be slowed down by not having enough memory bandwidth, because the omission of the cache would greatly increase the number of accesses to the main memory and thus the demand on memory bandwidth.

In the case of CPUs, the use of caches can thus help reduce the Von Neumann bottleneck in the Von Neumann architecture . The execution speed of programs can be increased enormously on average.

A disadvantage of caches is their poorly predictable timing, since the execution time of an access is not always constant due to cache misses. If the data is not in the cache, the user must wait until it has been loaded from the slow background medium. With processors, this often happens when accessing data that has not yet been used or when loading the next program command with (wide) jumps .

Cache hierarchy

Since it is technically complex and therefore usually not economically sensible to build a cache that is both large and fast, you can use several caches - e.g. B. a small, fast cache and a significantly larger, but somewhat slower cache (which is, however, still much faster than the background memory to be cached). This means that the competing goals of low access time and large cache size can be achieved together. This is important for the hit rate .

If there are several caches, they form a cache hierarchy that is part of the memory hierarchy . The individual caches are numbered according to their hierarchical level , ie level ‑ 1 to level ‑ n or L1, L2 for short, etc. The lower the number, the closer the cache is to the fast "user"; the lowest number therefore denotes the cache with the fastest access time; this is searched first. If the L1 cache does not contain the required data, the (usually somewhat slower, but larger) L2 cache is searched, etc. This happens until the data is either found in a cache level (a "cache hit", see below) or all caches were searched without success (a "cache miss", see below). In the latter case, the slow background memory must be accessed.

If a cache hit occurs e.g. B. in the L3 cache, the requested data is delivered to the accesser and transferred to the L1 cache at the same time; for this a cache line has to give way, which "sinks" into the L2 cache.

• With an inclusive cache , each cache level is transparent in itself; H. a cache line that is in the L1 cache is also present in the L2 and L3 cache. If the cache line is "displaced" from the L1 cache (overwritten with data from a different address), nothing else needs to be done - it is still available in the L2 cache (if no write-back or similar is necessary is).
• With an exclusive cache , a cache line of an address is only available once in all cache levels. A cache line to address A in the L1 cache is not also available in the L2 or L3 cache. If it is displaced from the L1 cache, it can either be discarded entirely or it must be explicitly copied into the L2 cache. A (different) cache line is therefore also displaced there to make room for the sinking one. This other one now sinks into the L3 cache, where a third cache line has to give way.

Exclusive cache hierarchies generate significantly more data traffic between the caches. As many cache lines as the sum of the L1, L2 and L3 cache sizes can be kept available for this purpose, while only the L3 cache size is decisive for the inclusive cache.

In the hardware area, modern CPUs in particular have two or three cache levels; other devices usually only have one cache level. In the software sector, mostly only one cache level is used, a prominent exception are web browsers that use two levels ( main memory and hard disk drive ).

Strategies

Cache size

In order to maximize the usefulness of the cache, which is usually several powers of ten, compared to the background memory, the locality properties of the access patterns are used in the functioning and organization of a cache . For example, if you observe the activity of a running program on a processor over a short time interval, you will notice that a few and “always the same” small memory areas (e.g. code within loops, control variables, local variables and procedure parameters) are repeatedly accessed becomes. Therefore, even small caches with a few kibibytes can be very effective.

However, if an algorithm is constantly processing new data (e.g. streaming data), a cache cannot accelerate it through multiple accesses, at best slightly through read-ahead .

Exploitation of the location

Since caches are supposed to be fast, a different (faster) memory technology is used for them than for the memory to be cached (for example SRAM versus DRAM , DRAM versus magnetic disk , etc.). Therefore, caches are usually much more expensive in terms of the price-bit ratio, which is why they are designed much smaller. This means that a cache cannot have all the data available at the same time. In order to solve the problem of which data should be kept in the cache, the locality properties of the accesses are used:

Temporal locality
Since data is accessed repeatedly (e.g. when processing a program loop), it is more likely that data that has already been accessed will also be accessed again. This data should therefore preferably be kept in the cache. This also results in the need to remove old data that has not been used for a long time from the cache in order to make room for newer data. This process is called “repression”.
Spatial locality
Since program code and data are not scattered around randomly in the address space, but are arranged "one behind the other" and sometimes only in certain address areas (code, data, stack segment, heap , etc.), it is after access to a specific address it is likely that a “nearby” address (read: the difference between the two addresses is very small) is accessed. When processing a program z. For example, one command after the other is processed, with these being “one after the other” in the memory (if there is no jump command). Many data structures such as arrays are also located “one behind the other” in memory.

Because of their spatial location, caches do not store individual bytes, but rather blocks of data ("cache block" or sometimes also called "cache line"). In addition, this makes implementation easier and reduces memory overhead , since you don't have to save an address per data byte, but only for each cache block. The choice of block size is an important design parameter for a cache that can have a major impact on performance.

organization

A cache consists of a (mostly) fixed number of entries, each entry consists of:

Cache line
The actual cached data (e.g. 64 bytes for current PC processors)
The address on the background media at which the cached data begins
Access / management information
v. a. Information for the "displacement strategy" (see below)

Cache-Line / Cache-Line

A cache line is the smallest administrative unit within the cache of processors. It is a copy of a storage area. The accesses from the cache memory to the CPU or to the main memory thus take place in a single, block-wise transfer. The size of a cache line is 16 bytes ( Intel 80486 ), 32 bytes (Pentium P5 to Pentium III) and 64 bytes (Pentium 4 to current Core-i / AMD ZEN processors in 2018). The minimum length results from the memory bus width multiplied by the prefetch depth of the memory.

In the following, it is assumed that cache lines are only ever read and written from addresses whose address can be divided by the (byte) length of the cache line.

example

A cache line is said to be 64 bytes. It should be specified that data can only be read and written with start addresses e.g. B. 0, 64, 128, 192, 256, ... The background medium is divided into blocks that are just the size of a cache line.

Then the entire (start) address of the data no longer has to be stored in the address tags, but only the number of data blocks cached on the background medium. By choosing suitable numbers (powers of two) in the binary system, the tags can be saved in a space-saving manner; this speeds up checking whether a requested address is contained in the cache.

Block / sentence division of the tags

Fully associative cache

The blocks (cache lines) of a cache can be summarized in so-called sets. Only one of the records is responsible for a specific address. Within a set, all blocks serve only part of all available addresses. In the following, the variable stands for the total number of cache blocks and for the number of blocks per record, the so-called associativity. The cache then consists of records . ${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle {\ tfrac {m} {n}}}$

organization Number of sets Associativity
DM ${\ displaystyle m}$ 1
FA 1 ${\ displaystyle m}$( ) ${\ displaystyle = n}$
SA ${\ displaystyle {\ tfrac {m} {n}}}$ ${\ displaystyle n}$

Depending on how strongly you make this division, one speaks of one of the three types of cache organization:

Mapped directly (Engl. Direct mapped , short DM )
${\ displaystyle n = 1}$, d. that is, each block represents its own sentence, so there are as many sentences as blocks. Thus exactly one cache block is responsible for a given address. So there is a direct mapping between the background memory address and cache blocks, hence the name. When making a request to such a cache, you only have to read out a single cache block (more precisely, check the associated tag , see below), which minimizes the hardware requirements for the tag comparator. In return, the efficiency of the cache is limited, as there may be free cache blocks that are not used, see Conflict Miss below.
Fully associative (Engl. Fully associative, shortly FA )
${\ displaystyle n = m}$, d. i.e., there is only one sentence that contains all blocks. This means that every address in every cache block can be cached. When making a request to the cache, it is therefore necessary to check all cache tags. Since caches have to be as fast as possible, this is carried out in parallel, which increases the amount of hardware required for tag comparators. The advantage, however, is that the cache can always hold data as long as any cache block is still free.
Set associative or quantity associative (Engl. Set associative, short SA )
${\ displaystyle n}$is chosen between 2 and , d. that is, the cache blocks are arranged in sets of blocks each. Here, directly mapped caches are selected fully associatively (i.e. freely). This cache is then called n-fold sentence -associative or n-fold associative for short . This type of cache represents a compromise between hardware complexity and cache efficiency: compared to a DM cache, you gain efficiency, compared to an FA cache you save hardware.${\ displaystyle {\ tfrac {m} {2}}}$${\ displaystyle n}$${\ displaystyle {\ tfrac {m} {n}}}$

The first two are a special case of the sentence-associative cache. The directly mapped and the fully associative cache can thus be derived from the set-associative cache: n = 1 leads to a directly mapped cache, n = m to a fully associative cache.

Explanation based on an example

The main sizes of a cache are:

• The size of the stored data (i.e. size of the cache): here in the example 64  KiB
• The size of the address space to be covered: here in the example 4  GiB
• The length of a cache line: here in the example 64 bytes
• The granularity of the data: here in the example 1 byte
• Presence of dirty and valid tags.

Regardless of the structure, the cache consists of 64 KiB / 64 bytes = 1024 cache lines

Fully associative cache
 31 30th 29 28 27 26th 25th 24 23 22nd 21st 20th 19th 18th 17th 16 15th 14th 13 12 11 10 9 8th 7th 6th 5 4th 3 2 1 0 Length of address tag Byte position

There is one cache group that includes all 1024 cache lines. Each main memory data word can be stored in any of the 1024 cache lines of the one cache group. 1024 comparators are required, which must compare log2 (4 GiB / 64 bytes) = log2 (4 GiB) -log2 (64 bytes) bits = 32-6 = 26 bits. These 26 bits are attached to each cache line as an address tag. Hardware effort:

• 1024 comparators
• 1024 × 64 × 8 bit actual cache
• 1024 × 26 bit address tag
• 1024 × 64 bit valid tags
• 1024 × 64 bit dirty tags
• 1024 ×? bit for the LRU tags
Direct mapped cache / simple or non-associative cache
 31 30th 29 28 27 26th 25th 24 23 22nd 21st 20th 19th 18th 17th 16 15th 14th 13 12 11 10 9 8th 7th 6th 5 4th 3 2 1 0 Length of address tag cache group used Byte position

There are 1024 cache groups, each with one cache line. Each main memory data word can only be stored in this cache line belonging to its address. The cache group results from bits 15 to 6 of the address. Only one comparator is required, which has to compare log2 (4 GiB) -log2 (64 KiB) bits = 16 bits. These 16 bits are attached to each cache line as an address tag. Hardware effort:

• A comparator
• 1024 × 64 × 8 bit actual cache
• 1024 × 16 bit address tag
• 1024 × 64 bit valid tags
• 1024 × 64 bit dirty tags
• No LRU tags
Double associative cache
 31 30th 29 28 27 26th 25th 24 23 22nd 21st 20th 19th 18th 17th 16 15th 14th 13 12 11 10 9 8th 7th 6th 5 4th 3 2 1 0 Length of address tag cache group used Byte position

There are 512 cache groups with two cache lines each. Each main memory data word can be stored in one of the two cache lines belonging to its address. The cache group results from bits 14 to 6 of the address. Two comparators are required which have to compare log2 (4 GiB) -log2 (64 KiB) +1 bits = 17 bits. These 17 bits are attached to each cache line as an address tag. Hardware effort:

• Two comparators
• 1024 × 64 × 8 bit actual cache
• 1024 × 17 bit address tag
• 1024 × 64 bit valid tags
• 1024 × 64 bit dirty tags
• 1024 × 1 bit LRU tags
2 ^ n-fold associative cache
 31 30th 29 28 27 26th 25th 24 23 22nd 21st 20th 19th 18th 17th 16 15th 14th 13 12 11 10 9 8th 7th 6th 5 4th 3 2 1 0 Length of address tag cache group used Byte position

There are 1024/2 ^ n cache groups with 2 ^ n cache lines each. Each main memory data word can be stored in one of the 2 ^ n cache lines belonging to its address. The cache group results from bits 15- (n-1) to 6 of the address. 2 ^ n comparators are required, which have to compare log2 (4 GiB) -log2 (64 KiB) + n bits = 16+ (n-1) bits. These 16+ (n-1) bits are attached to each cache line as an address tag. Hardware effort:

• 2 ^ n comparators
• 1024 × 64 × 8 bit actual cache
• 1024 × (16 + n-1) bit address tag
• 1024 × 64 bit valid tags
• 1024 × 64 bit dirty tags
• 1024 × multiple bit LRU tags

Cache hits and misses

The process in which the data of a request to a cache is available is called a “cache hit”, the reverse is called a “cache miss”.

In order to obtain quantitative measures for the evaluation of the efficiency of a cache, two parameters are defined:

Hit rate
The number of requests for which a cache hit occurred divided by the total number of requests made to this cache. As you can easily see from the definition, this quantity is between zero and one. A hit rate of e.g. B. 0.7 (= 70%) means that in 70% of all requests to the cache, the cache was able to deliver the data immediately and had to match in 30% of all requests.
Miss rate
Similar to the hit rate, this is defined as the number of requests for which the data was not in the cache divided by the number of total requests. The following applies: Miss rate = 1 - hit rate.

There are three types of cache misses:

Capacity
The cache is too small. Data was available in the cache but was removed from it. If this address is then accessed again, this miss is referred to as a "capacity miss". The only remedy is a larger cache.
Conflict
Due to the set-associative organization (also applies to DM caches) it is possible that there is no longer enough space in one set while there are still free cache blocks in other sets. Then a block must be removed from the overcrowded record, although the cache actually still has space. If this removed block is accessed again, this cache miss is called a "conflict miss". This can be remedied by increasing the cache blocks per record - i.e. increasing the associativity. In the case of fully associative caches (which only have one record) there are no conflict misses due to the principle involved.
Compulsory
A “Compulsory Miss” or “Cold Start Miss” is the name given to the first access to an address whose data is not yet in the cache, and at the same time the cache still has free space. The difference to the other two misses is that there is no repression here, but a block is described for the first time / anew. It is difficult or impossible to prevent. Modern processors have “ prefetcher ” units that automatically load data into the caches speculatively if there is still space. This is to reduce the number of compulsory misses.

These three types are also known as "The Three Cs" for short. In multiprocessor systems, when using a cache coherence protocol of the Write-Invalidate type , a fourth "C" can be added, namely a "Coherency Miss": When a processor writes to a cache block, the same block in the cache of a second processor is thrown out If the second processor has to access an address that was covered by this remote cache block, this leads to a coherency miss.

Working method

When managing the cache, it makes sense to only keep those blocks in the cache that are frequently accessed. There are various replacement strategies for this purpose. A frequently used variant is the LRU strategy ( l east r ecently u sed ), in which the block is always exchanged that has not been accessed for the longest time. Modern processors (e.g. the AMD Athlon ) mostly implement a pseudo-LRU replacement strategy that works almost like real LRU, but is easier to implement in hardware.

Displacement strategies

FIFO (First In First Out)
The oldest entry is suppressed.
LRU (Least Recently Used)
The entry that has not been accessed for the longest time is suppressed.
LFU (Least Frequently Used)
The least frequently read entry is suppressed. However, no complete timestamps are saved, which would require a relatively long integer number. Rather, only a few bits are used (two are common, but only one is possible) to mark a cache entry as being used more or less frequently. The bits are updated in parallel to a displacement.
Random
A random entry is suppressed.
CLOCK
Data is stored in the cache in the order in which it is accessed. If a data item is accessed, a bit is set for this cache block. In the event of a miss, the first date without a set bit is searched from front to back; this is replaced. The bit is cleared for all data passed through. It is also marked which date was last loaded into the cache. From there the search for a date begins that can be replaced.
Optimal
The Laszlo Belady process , in which the memory area is displaced which will not have been accessed for the longest, is optimal. However, it is only applicable if the complete program flow is known in advance (i.e. it is a so-called offline method, in contrast to FIFO and LRU, which are online methods). The program sequence is almost never known in advance; therefore, the best practice cannot be used in practice. However, the optimal algorithm can serve as a comparison for other methods.

Writing strategy

In principle, there are two possibilities for write access to a block that is in the cache:

Copy back (write-back)
When writing, the block to be written is not immediately stored in the next higher memory level, but first in the cache. This creates an inconsistency between the cache and the memory to be cached. The latter therefore contains outdated information. Only when the word has been displaced from the cache is it also written to the next higher memory level. In addition, each cache block is given a so-called dirty bit, which indicates whether the block has to be copied back when it is replaced. This leads to problems with memory access by other processors or DMA devices because they would read outdated information. The remedy here cache coherency protocols such. B. MESI for UMA systems.
Continuous writing (write-through)
The block to be written is immediately stored in the next higher memory level. This ensures consistency. So that the processor does not have to wait every time until the block is stored in the next higher memory level (which is slower than the cache), a write buffer is used. However, when this fills up, the processor has to stop and wait.

Analogous to the above, there are basically two options for write access to a block that is not in the cache:

write-allocate
As with a normal cache miss, the block is fetched from the next higher memory level. The corresponding bytes that were changed by the write access are then overwritten in the block that has just arrived.
non-write-allocate
It is written to the next higher memory level bypassing the cache without the corresponding block being loaded into the cache. This can be advantageous for some applications in which a lot of written data is never read again. Using non-write-allocate prevents other, possibly important blocks from being displaced, thus reducing the miss rate.

Some instruction sets contain instructions that enable the programmer to explicitly specify whether data to be written is to be written past the cache.

Usually either the combination write-back with write-allocate or write-through with non-write-allocate is used. The first combination has the advantage that successive write accesses to the same block (principle of locality) are completely processed in the cache (except for the first miss). This is of no advantage in the second case, since every write access to the main memory must anyway, which is why the combination write-through with write-allocate is rather unusual.

Cache flush

A cache flush ("buffer memory emptying") causes the entire contents of the cache to be written back to the background memory. The contents of the cache are mostly left untouched. Such a procedure is necessary to restore the consistency between the cache and the background memory. This is necessary, for example, whenever data from the main memory is required by external devices, for example for multiprocessor communication or when transferring part of the main memory used as an output buffer to the DMA controller.

Others

Entries in the cache

The following is stored in the cache for each cache block:

• The actual data
• The day (part of the address)
• Several status bits, such as:
modified or dirty
Indicates whether this cache block has been changed (only for write-back cache).
various status bits depending on the cache coherence protocol, e.g. B. one bit each for:
owner
Equivalent to "modified & shared". Indicates that the block has been modified and is in other caches. The owner is responsible for updating main memory when removing the block from its cache. The processor that last wrote to the cache block becomes the new owner.
exclusive
Indicates that the block has not changed and is not present in any other cache.
shared
Sometimes has different meanings: With MESI , this indicates that the block has not been changed, but is also present in caches of other processors (also unchanged there). With MOESI , it just means that the block is in other processor caches . Here it is also permitted that the block has been changed, i.e. is inconsistent with the main memory. In this case, however, there is an “owner” (see above) who is responsible for updating the main memory.
invalid
Indicates whether the block is free (i.e. filled with invalid data) or occupied (i.e. filled with valid data).

Hot and cold caches

A cache is “hot” when it is working optimally, ie when it is full and has only a few cache misses; if this is not the case, the cache is considered "cold". After being put into operation, a cache is initially cold because it does not yet contain any data and often has to reload data, which is time-consuming, and then warms up increasingly because the temporarily stored data increasingly correspond to the requested data and less reloading is required. In the ideal state, data access is served almost exclusively from the cache and reloading can be neglected.

Examples

Processor cache

With CPUs, the cache can be integrated directly in the processor or placed externally on the motherboard (previously more common, today rather untypical). Often there are several levels that build on one another. Smaller levels are typically faster, but are smaller in size for cost reasons. Depending on the location of the cache, it works with different clock frequencies: The L1 (level 1, closest to the CPU) is almost always integrated directly in the processor (i.e. on the die ) and therefore works with the full processor clock - i.e. U. several gigahertz . An external cache, on the other hand, is often only clocked at a few hundred megahertz .

Current processors (e.g. AMD Ryzen , Intel Core i series , IBM Power 9 ) mainly have three cache levels: L1, L2 and L3. Common sizes for L1 caches are 4 to 256  KiB per processor core, the L2 cache is 64 KiB to 1024 KiB (usually also per core), the L3 cache 2 to 32 MiB (common for all cores). In cheaper versions, the L3 cache is sometimes left out or switched off, but the L2 cache is partially enlarged. Processor cache as an extra chip on the mainboard is no longer built as an extra die in the same chip housing (see multi-chip package ).

In any case, logging is necessary to ensure the coherence of the data (e.g. between caches and main memory). Flags are used for this purpose , which mark a memory area (typically a whole line of 64 bytes) as "dirty", i.e. changed (see above under write strategy ). The problem is exacerbated with multiple cache levels and multiple processors or processor cores.

The cache consistency must be observed both with several active devices on the data bus and with several interconnected processors ( multiprocessor systems ).

In multi-processor systems, a distinction is made between a. between SIMD and MIMD structures (Single / Multiple Instruction - Multiple Data). With MIMD systems, the probability is high that different processors will access different memory areas, with SIMD it is less. The cache configuration can then be set.

Modern processors have separate L1 caches for programs and data (read and write cache); this is also partly the case with the L2 ( Montecito ). One speaks here of a Harvard cache architecture . This has the advantage that you can use different cache designs for the different access patterns for loading program code and data. In addition, if you have separate caches, you can better place them in relation to the respective units on the processor die and thus shorten the critical paths in the processor layout. Furthermore, instructions and data can be read / written at the same time, which further reduces the Von Neumann bottleneck . One disadvantage is that self-modifying code has to be treated separately, which greatly slows its execution. However, for safety reasons and because it is often difficult to understand, difficult to test and therefore difficult to maintain, it is used very rarely today anyway.

Drive cache

In the case of hard disks, the cache is located on the control board (see hard disk cache ) or on a separate board, the hard disk controller .

The size of current hard disks - depending on the intended use of the hard disk by the manufacturer - is between 8 and 64 MiB (as of 2012).

Most optical drives have caches to absorb the access times and fluctuations in the data stream (e.g. due to synchronization problems), which are often in the three-digit millisecond range.

Software caches

Caches can also be used with software; the same principle is meant here as with hardware implementation: data is temporarily stored for faster access to a faster medium.

Examples:

Hard drive cache (managed by the operating system)
Hard disk → main memory
Application data ( memoisation )
Calculation → main memory
Browser cache
Network → (hard disk / RAM)
Web server
Database → HTML file ( HTTP caching )

Software caches, which use the hard disk as a faster medium, are usually created in the form of temporary files .

Caching is also used when an operating system has certain resources - such as B. function libraries or fonts - initially left in the working memory, although they are no longer needed after their use. As long as there is no lack of memory, they can remain in the main memory in order to be immediately available without reloading from the hard disk when they are needed again. However, if the memory management of the operating system detects a lack of memory, these resources are deleted first.

Search engine cache

The search engine cache is the reading cache of a search engine. A search engine has three core components:

1. A web crawler searches the WWW for new or changed websites and loads them (additionally) into
2. the search engine cache, which is used to regularly create various indexes . Looks through these indexes
3. a search algorithm that is supposed to find suitable web pages according to a user query.

The content of all websites that the search engine takes into account as basic data for user queries is temporarily stored in the search engine cache. The servers of a search engine cannot search every website for the latest content in real time for every query ; instead, an index over the cache is searched for.

In general, a website operator can report changes to his website to the search engine, then the web crawler queries the page again as soon as possible; otherwise the web crawler checks every website at regular intervals - the cache contents can therefore be out of date. A web page can give the crawler an indication of how often it changes in general. Search engines sometimes deal with this information in different ways.

The most popular search engine in Germany is Google ; their cache, indexing and search strategies are therefore of particular interest. The web crawler frequency with which websites are checked is between one and four weeks for most websites ("[...] content is usually updated every 7 days "). The so-called Googlebot examines reported websites .


text:
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 7 2 1 100.000%

## 문제

Alice and Bob are playing a game of baggage delivery using a toy solar car. A number of poles are placed here and there in the game field.

At the start of a game, the solar car is placed right next to a pole, and the same or another pole is marked as the destination. Bob chooses one of the poles and places the baggage there. Then, Alice plans a route of the car to pick up the baggage and deliver it to the marked destination. Alice chooses the shortest possible route and Bob should choose a pole to maximize the route length.

The solar car can drive arbitrary routes but, as it has no battery cells, it would stop as soon as it gets into shadows. In this game, a point light source is located on the surface of the field, and thus the poles cast infinitely long shadows in the directions opposite to the light source location. The drive route should avoid any of these shadows.

When the initial positions of the solar car and the destination are given, assuming that both players make the best choices, the length of the drive route is uniquely determined.

Let us think of all the possible game configurations with given two sets of poles, one for the start positions of the solar car and the other for the destinations. When both the initial car position and the destination are to be chosen uniformly at random from the corresponding sets, what is the expected route length?

Your task is to compute the expected value of the route length, given the set of the initial positions of the car and that of the destinations.

## 입력

The input consists of a single test case of the following format.

n
x1 y1
.
.
.
xn yn
p
a1 b1 c1 d1
.
.
.
ap bp cp dp

Here, n is the number of poles (3 ≤ n ≤ 2000). The poles are numbered 1 through n and the i-th pole is placed at integer coordinates (xi, yi) (−1000 ≤ xi ≤ 1000, −1000 ≤ yi ≤ 1000). The point light is at (0, 0). Poles are not placed at (0, 0) nor in a shadow of another pole, and no two poles are placed at the same coordinates.

p is the number of pairs of sets (1 ≤ p ≤ 105). The i-th pair of sets is specified by four integers (ai, bi, ci, di) (1 ≤ ai ≤ bi ≤ n, 1 ≤ ci ≤ di ≤ n). Specifically, the solar car is initially placed at the j-th pole, with j chosen uniformly at random from {ai, . . . , bi}, and the destination pole is also chosen uniformly at random from {ci, . . . , di}.

## 출력

Output the answer for each pair of sets. Absolute or relative errors less than 10−7 are permissible.

## 예제 입력 1

5
7 0
3 3
0 7
-3 3
-7 0
6
1 1 3 3
3 3 4 4
1 1 5 5
5 5 2 2
2 2 4 4
1 5 1 5

## 예제 출력 1

24.000000000000
20.440306508911
20.000000000000
19.000000000000
15.440306508911
21.606571644990

## 힌트

For the first set pair of this test case, the solar car is placed at (7, 0) and the flag is placed at (0, 7). Then, Bob places the baggage at (−7, 0). The length of the shortest route from (−7, 0) to (0, 7) is 10, because the straight path from (−7, 0) to (0, 7) crosses the shadow of pole 4. The length of the shortest route from (7, 0) to (−7, 0) is 14, so the total length is 24.

Figure F.1. Shortest routes for the first five set pairs of Sample Input 1. Black dots are the positions of the poles and gray lines are their shadows. The yellowish brown dots are the positions of the point lights. For each figure, the red lines indicate the shortest route from the initial car position to the destination.


text:
### On the Shortness of Vectors to be found by the Ideal-SVP Quantum Algorithm

Léo Ducas, Maxime Plançon, and Benjamin Wesolowski

##### Abstract

The hardness of finding short vectors in ideals of cyclotomic number fields (hereafter, Ideal-SVP) can serve as a worst-case assumption for numerous efficient cryptosystems, via the average-case problems Ring-SIS and Ring-LWE. For a while, it could be assumed the Ideal-SVP problem was as hard as the analog problem for general lattices (SVP), even when considering quantum algorithms. But in the last few years, a series of works has lead to a quantum algorithm for Ideal-SVP that outperforms what can be done for general SVP in certain regimes. More precisely, it was demonstrated (under certain hypotheses) that one can find in quantum polynomial time a vector longer by a factor at most $\alpha = \exp({\tilde O(n^{1/2})})$ than the shortest non-zero vector in a cyclotomic ideal lattice, where $n$ is the dimension. In this work, we explore the constants hidden behind this asymptotic claim. While these algorithms have quantum steps, the steps that impact the approximation factor $\alpha$ are entirely classical, which allows us to estimate it experimentally using only classical computing. Moreover, we design heuristic improvements for those steps that significantly decrease the hidden factors in practice. Finally, we derive new provable effective lower bounds based on volumetric arguments. This study allows to predict the crossover point with classical lattice reduction algorithms, and thereby determine the relevance of this quantum algorithm in any cryptanalytic context. For example we predict that this quantum algorithm provides shorter vectors than BKZ-300 (roughly the weakest security level of NIST lattice-based candidates) for cyclotomic rings of rank larger than about $24000$.

Note: *Erratum.* A previous version (Feb. 2019) of this report included errors in Figure~\ref{fig:compare_with_bkz}: our plotting script had a mistake overpredicting the root-Hermite factor. After correction (Aug. 2021), various cross-over points with BKZ have therefore noticeably decreased. We are grateful to Daniel J. Bernstein, Kirsten Eisenträger, Tanja Lange, Karl Rubin, Alice Silverberg, and Christine van Vredendaal for detecting, identifying, and reporting this mistake.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Quantum CryptanalysisCyclotomic Ideal Lattices.
Contact author(s)
ducas @ cwi nl
History
2021-08-23: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/234

CC BY

BibTeX

@misc{cryptoeprint:2019/234,
author = {Léo Ducas and Maxime Plançon and Benjamin Wesolowski},
title = {On the Shortness of Vectors to be found  by the Ideal-SVP Quantum Algorithm},
howpublished = {Cryptology ePrint Archive, Paper 2019/234},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/234}},
url = {https://eprint.iacr.org/2019/234}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
# If during a no-load test on an induction motor it takes 10 A current and 300 watts of power at a line voltage of 200 V, the stator core loss will be (assume stator resistance /phase as 0.3 Ω)

Free Practice With Testbook Mock Tests

## Options:

1. 165 W

2. 300 W

3. 210 W

4. 192 W

### Correct Answer: Option 3 (Solution Below)

This question was previously asked in

DMRC JE EE 2018 Official Paper 3

## Solution:

Concept:

No-load test or open circuit test:

It is used to find out shunt branch elements of the equivalent circuit R0 and X0 and to find constant losses of the induction machine.

To find out constant losses,

W0 = Losses in induction motor under no-load condition (mechanical power output is zero)

W= Iron losses (stator core losses) + Mechanical losses + No load stator copper losses

Constant losses = W0 - No-load stator copper losses

Calculation:

No load current (I0) = 10 A

No load power (W0) = 300 W

Stator resistance /phase (R) = 0.3 Ω

Stator copper losses $$= 3I_0^2R = 3 \times {10^2} \times 0.3 = 90\;W$$

Stator core losses = No load power - stator copper losses = 300 - 90 = 210 W