text:
# Riemann Geometry and Physics

• I
Killtech
In terms of diff geo it seems like an obvious fact, that a manifold can be equipped with quite a variety of different Riemann metrics. But when it comes to physics (relativity theory in particular) it seems there is a very specific metric singled out. Now i do not entirely understand the connection between physics its mathematical formulation, but that is what i intend to find out.

So my understanding of Riemann geometry is that whether a surface has curvature or not depends entirely on the metric the manifold is equipped with. Furthermore there are many other metrics a manifold can have and the identify function should act as a pullback between them - since those are Riemann metrics i don't see how they could have incompatible topology amongst each other to to break the smoothness of ##id##.

So given a problem (e.g. an equation) on a specific Riemann manifold there should be no issue to pull it back to any other geometry (same manifold, different Riemann metric) and have an equivalent description of the problem there. My question is now if there is anything that distinguishes a specific and unique metric as in "the real depiction of the surface e.g. how it's really curved". Until now my understanding was that one metric is as good as another and if a distinction is made it's just for pragmatic reasons.

So far my naive view was that curvature was merely something resulting from how we chose to measure distances and therefore by itself not inherently a physical entity, which is dictated by nature. On the other hand i am very well aware that any information contained in the curvature of a physical problem is crucial, but i wonder if that's the only way to depict it.

Staff Emeritus
If I understand what you're asking, you're right, that a metric has no physical significance until you relate it to physically meaningful quantities.

The spatial component of the metric is used for computing lengths of objects. That has no physical significance unless you add the physical assumption that, in many situations, the length of a rigid object is unchanged as a function of time, and is unchanged by rotations and translations. Those properties of a rigid object are important for there to be such a thing as a "meterstick". If sticks were not rigid, but were instead stretchable like putty, then you couldn't use them to measure.

But given that there are such things as (approximately; no object is rigid in all possible circumstances) rigid objects, then the metric, and curvature (which is computed from the metric) is a physical property.

The metric also defines what is known as "geodesics", which is the analog of "straight lines" in curved space (actually, to define geodesics, you don't necessarily have to have a metric, but if you do have a metric, then geodesics can be defined in terms of the metric). Geodesics have very little physical relevance until you can connect them to the behavior of physical objects. The connection is through Newton's first law (which generalizes to curved space): An object in motion continues motion in a straight line unless acted upon by an external force. So you throw a rock, and assuming that electrical forces, friction forces, etc., are all negligible, then the path of the rock will be a geodesic.

(A difference between Newtonian physics and General Relativity is that for Newton, gravity was an external force, causing a rock's path to veer away from straight-line motion. For General Relativity, it is assumed that gravity is a manifestation of curved spacetime, so the path of a thrown rock is (approximately) geodesic even when there is gravity.)

Staff Emeritus
Homework Helper
Gold Member
2021 Award
Furthermore there are many other metrics a manifold can have and the identify function should act as a pullback between them
I'm not really sure what you are saying here? Are you saying that the identity function from the manifold to itself should let you pull one metric back to become another metric? If so that is not the case, the identity function on a manifold pulls a metric back to the same metric. You can relate some metrics to each other by considering the pullback of a metric tensor under an automorphism of the manifold, which will generally relate the metrics simply by a coordinate transformation. However, this is not necessarily the case for arbitrary metrics. For example, the pullback will preserve things like curvature scalars etc so you cannot pull back a zero curvature metric and get a metric corresponding to non-zero curvature. In this sense, you cannot change the geometry of the Riemannian manifold using the pullback of an automorphism.

A very important concept is also that of Killing fields, which generate symmetry transformations of the manifold, i.e., the pullback of the metric under the symmetry transformation is the metric itself.

So far my naive view was that curvature was merely something resulting from how we chose to measure distances and therefore by itself not inherently a physical entity, which is dictated by nature. On the other hand i am very well aware that any information contained in the curvature of a physical problem is crucial, but i wonder if that's the only way to depict it.

On the contrary, curvature and more generally the geometry of a Riemannian manifold is something tangible that cannot be changed just through an automorphism's pullback.

PeroK
Killtech
If I understand what you're asking, you're right, that a metric has no physical significance until you relate it to physically meaningful quantities.

The spatial component of the metric is used for computing lengths of objects. That has no physical significance unless you add the physical assumption that, in many situations, the length of a rigid object is unchanged as a function of time, and is unchanged by rotations and translations. Those properties of a rigid object are important for there to be such a thing as a "meterstick". If sticks were not rigid, but were instead stretchable like putty, then you couldn't use them to measure.

But given that there are such things as (approximately; no object is rigid in all possible circumstances) rigid objects, then the metric, and curvature (which is computed from the metric) is a physical property.
Yeah, this is an aspect i was thinking a lot about lately. In particular about the assumption that a rigid object, i.e. the "meterstick" length is unchanged. The structure of Riemann geometry makes me think this postulate is not physical in nature, given the circular definition of any real length measure. I mean how would you know that a meterstick doesn't change length? you have to measure it and every measurement requires comparing your sample vs a reference measure i.e. another meterstick.. so I'm not sure it's logically undecidable if it really does change and it would seem that at some point some meterstick must be simply defined as constant. Poincaré pointed out this problem in a letter from 1904.

But looking at the math i instead got the idea that it doesn't really matter because it's totally sufficient to think of all length measurements as in units of the local length of the meterstick rather then an invariant absolute value. A length measure defined via such a physical meterstick would then only require to suffice the properties of a metric, so even if we consider a stick not being rigid but having a well defined length at each point and direction of space time (Come to think of it this may be a very physical depiction of the metric tensor) it should suffice to define a Riemann metric - at least its purely spatial components (strictly speaking this is not true for the original meter bar in Paris, because it's length at a point of space time would depend on the way it got there. That's a bigger problem then it not being rigid). That at least would fit well with the picture that a manifold has many Riemann metrics to chose from and none is naturally highlighted as the real on in terms of mathematics.

Using different physical objects as reference for length that might change their relative length compared to each other would therefore merely represent different Riemann metrics physics could be represented with. As such there would be no absolute way to say whether a body is rigid in general, as this would depend on the choice of metric.

The metric also defines what is known as "geodesics", which is the analog of "straight lines" in curved space (actually, to define geodesics, you don't necessarily have to have a metric, but if you do have a metric, then geodesics can be defined in terms of the metric). Geodesics have very little physical relevance until you can connect them to the behavior of physical objects. The connection is through Newton's first law (which generalizes to curved space): An object in motion continues motion in a straight line unless acted upon by an external force. So you throw a rock, and assuming that electrical forces, friction forces, etc., are all negligible, then the path of the rock will be a geodesic.

(A difference between Newtonian physics and General Relativity is that for Newton, gravity was an external force, causing a rock's path to veer away from straight-line motion. For General Relativity, it is assumed that gravity is a manifestation of curved spacetime, so the path of a thrown rock is (approximately) geodesic even when there is gravity.)
About Newton and GRT. I wondered if a core difference between those theories could be interpreted that Newtown actually uses a different metric? I try to sketch how i get there: consider Newton and Einstein describing the identical scenario of a spherical mass (think of the Schwarzschild solution for a Earth proxy). Consider both building rings at different radiuses and measuring their length. in GRT space curvature will make it deviate from the ##2 \pi r## formula, so Newtowns case he will find his Euclidean geometry mismatches the measured data. Couldn't he therefore conclude that the 1-SI meter(stick) must change its length depending on its space location (in particular the gravity potential)? So he would have to presume his theory measures lengths differently then the measurement devices do but using a pullback to their metric could remedy it, no?

Last edited:
Killtech
I'm not really sure what you are saying here? Are you saying that the identity function from the manifold to itself should let you pull one metric back to become another metric? If so that is not the case, the identity function on a manifold pulls a metric back to the same metric. You can relate some metrics to each other by considering the pullback of a metric tensor under an automorphism of the manifold, which will generally relate the metrics simply by a coordinate transformation. However, this is not necessarily the case for arbitrary metrics. For example, the pullback will preserve things like curvature scalars etc so you cannot pull back a zero curvature metric and get a metric corresponding to non-zero curvature. In this sense, you cannot change the geometry of the Riemannian manifold using the pullback of an automorphism.
Hmm, okay. Well, there are different types of manifolds i guess and we are not talking about the same here. Consider the identity function as acting only on the bare set of ##M## and forget about it knowing about any other structures defined on it maybe.

Perhaps i better make a concrete example: consider a smooth 2 dimensional manifold ##M## and a coordinate chart ##\phi##. Now let's suppose that someone lost the information about what surface ##M## actually was and we don't have its metric anymore - i.e. we only know how it looks via its coordinates. So we have to look at the possibilities: it could have been just flat surface or maybe it was part of a sphere with a curvature? We can equip ##M## with the possible Riemann metrics for either of those cases, but the set ##M## itself stays identical and we could go from one option to the other by using the ##id## function on the set of ##M##. So ##id## actually maps between two different Riemann manifolds - which is a bit confusing i admit. Now ##id## will be bijective in any case but smoothness requires the topologies on both sides to agree. Anyhow i don't see how ##id## would remain isometric for that case.

Last edited:
Staff Emeritus
Yeah, this is an aspect i was thinking a lot about lately. In particular about the assumption that a rigid object, i.e. the "meterstick" length is unchanged. The structure of Riemann geometry makes me think this postulate is not physical in nature, given the circular definition of any real length measure. I mean how would you know that a meterstick doesn't change length?

Well, you would certainly know if different metersticks changed size in different ways. Then two metersticks that started out the same size would end up different sizes.

If you're asking whether it's possible that everything in the whole universe changed size in exactly the same ratio, so comparisons never changed, well, that wouldn't be observable. In that case, you could just define the length of something to be the length relative to a standard. Then by definition, if the ratio didn't change, then the lengths would be constant.

There is a certain flexibility or tradeoff between "laws of physics" and "geometry". If you wanted to define the surface of the Earth to be a flat plane, you could do so, but then you would find all sorts of effects, such as the lengths of objects changing as you move them around.

The only thing that you can physically test is the combination of particular laws of physics with particular assumptions about geometry. You can't test the two completely separately (I don't think). For example, in a rotating coordinate system, there is an apparent "centrifugal force" seeming to fling objects away from the center of rotation. Properly understood, this is not an actual force, but is a manifestation of geometry.

You could, however, attribute it to a physical force, instead of geometry. That is, you could assume that your coordinates are not rotating, but that there is some strange "anti-gravity" emanating from the center, pushing things out. That's certainly a possible interpretation, but it would lead to a strange theory, because there is no source to this force field. There's no actual object in the center that could be the source of some kind of anti-gravity.

So the choice between what's geometry and what's physical forces is not completely determined, but we choose the geometry that makes the laws of physics as simple as possible.

But looking at the math i instead got the idea that it doesn't really matter because it's totally sufficient to think of all length measurements as in units of the local length of the meterstick rather then an invariant absolute value.

Right. I guess I should have read this before responding with the above.

About Newton and GRT. I wondered if a core difference between those theories could be interpreted that Newtown actually uses a different metric? I try to sketch how i get there: consider Newton and Einstein describing the identical scenario of a spherical mass (think of the Schwarzschild solution for a Earth proxy). Consider both building rings at different radiuses and measuring their length. in GRT space curvature will make it deviate from the ##2 \pi r## formula, so Newtowns case he will find his Euclidean geometry mismatches the measured data. Couldn't he therefore conclude that the 1-SI meter(stick) must change its length depending on its space location (in particular the gravity potential)? So he would have to presume his theory measures lengths differently then the measurement devices do but using a pullback to their metric could remedy it, no?

Yes. There is no such thing (as far as I know) as an effect that absolute cannot be explained using Newton's physics, with flat space and absolute time, as long as you're creative enough about making up new, weird forces. Before Einstein, people did attempt to explain things such as the null result of the Michelson-Morley experiment by proposing forces that physically affected the lengths of rods and the timing of clocks as they move around. It can be made to work, but it's a lot more complicated than Einstein's approach, which makes use of a different spacetime geometry than Newton used.

Killtech
Killtech
If you're asking whether it's possible that everything in the whole universe changed size in exactly the same ratio, so comparisons never changed, well, that wouldn't be observable. In that case, you could just define the length of something to be the length relative to a standard. Then by definition, if the ratio didn't change, then the lengths would be constant.
i don't exactly understand your premise here. You can define various physical objects or length which do change relative to the SI-meter depending on where they are (and in a well defined way). My thinking was that one could equally set these things to have constant length instead thus rendering the SI-meter to not being constant.

So the choice between what's geometry and what's physical forces is not completely determined, but we choose the geometry that makes the laws of physics as simple as possible.
Yeah, that is exactly my thinking. But what the simples possible form laws of physics can take is always depending on the context of your problem, no? For me it looks like in this regard the metric/geometry resembles coordinate transformations in that you could switch between them to simplify your problem. But coordinates are chosen purely for practicality and there is no point of thinking of any choice as the actually "true" or "real" one.

Case in point, when dealing with acoustics, one could you just define a measure of length by using sonar location for distance measurement? due to the properties of the medium the speed of sound differs locally but is well defined to suffice as a metric in regular circumstance i think (ofc, not in a vacuum), so if you measure 1 SI-meter in different locations in terms of the two-way speed of sound the results will deviate. But using the special metric should simplify acoustic physics by rendering the speed of sound artificially constant - at the expense of adding curvature to a previously flat space.

Yes. There is no such thing (as far as I know) as an effect that absolute cannot be explained using Newton's physics, with flat space and absolute time, as long as you're creative enough about making up new, weird forces. Before Einstein, people did attempt to explain things such as the null result of the Michelson-Morley experiment by proposing forces that physically affected the lengths of rods and the timing of clocks as they move around. It can be made to work, but it's a lot more complicated than Einstein's approach, which makes use of a different spacetime geometry than Newton used.
Hmm, you arrive at the very same conclusions i have. I take it as a good sign that I'm not going nuts :). However don't think getting creative in finding ways to fix Newtons physics would be very productive. I would rather look for a way to identify the metrics of Newton and Einstrein and try to find a pullback between them in order to have a clearly defined way to translate all laws of physics from one geometry to another. I mean i would assume there could be some simplifying advantages of having a flat space time. And going back to the example of the 1-SI meter changing length in Newtown's grav potential - by the definition of the meter via the speed of light it implies it's not constant there as well. So Maxwells equations in vacuum would have to get something like a refractive index induced by Newtowns gravity - i.e. something resembling a medium. if a pullback to that geometry existed a Newtonian equivalent of Maxwell could be calculated from GRT right away, right? It would be interesting to know if the old aether theories (like the one originally used to explain Michelson-Morley result) could actually be equivalent to GRT but using a different metric.

Anyhow i don't want to discuss the details of such a approach here but rather trying find out if my way of thinking about this has any major logical flaws or oversights. So i welcome pointing out wherever the math does not warrant such interpretation.

Staff Emeritus
Yeah, that is exactly my thinking. But what the simples possible form laws of physics can take is always depending on the context of your problem, no?

No, I don’t think so. It’s true that geometric effects can look like physical forces. For example, the apparent centrifugal force. But that doesn’t mean that choosing what is forces and what id geometry is arbitrary. Geometric effects have certain universal qualities: They affect all objects in the same way, and they have a characteristic dependence on the velocity of the object. And, more to the point, the effect on test particles can always be locally eliminated by a coordinate change.

That’s not true for other physical effects. If you have an electric field, for example, it affects positively charged particles differently than negatively charged particles. This difference cannot be transformed away through a coordinate change.

Killtech
No, I don’t think so. It’s true that geometric effects can look like physical forces. For example, the apparent centrifugal force. But that doesn’t mean that choosing what is forces and what id geometry is arbitrary. Geometric effects have certain universal qualities: They affect all objects in the same way, and they have a characteristic dependence on the velocity of the object. And, more to the point, the effect on test particles can always be locally eliminated by a coordinate change.

That’s not true for other physical effects. If you have an electric field, for example, it affects positively charged particles differently than negatively charged particles. This difference cannot be transformed away through a coordinate change.
It is clear that all the information contained within the geometry cannot simply get lost via a transformation, so it has to transform into something else. My thinking was not about trying to choose what should be a force and what geometry - but merely chose a different metric and see what happens: If a map can be constructed between the original manifold and the new one arising by equipping the same space with the new metric (the map should therefore be based on ##id## of the underlying space) and that map is homeomorph - then pulling back laws of physical via that map cannot lose any physical information - therefore giving an equivalent description of the very same physics in the new metric. Therefore whatever metric you choose, gravity cannot ever vanish but rather must take some different form.

And about geometries affecting all objects in the same way - it is certainly true, yet the meaning of "same way" is perhaps misleading.

I'll try to make a simple purely mathematical model to sketch that thought. Consider the Minkowski space with only two fields for which the Maxwell equations ##m_1## holds (assuming charge and current always to ##0## for this example). Now let's pick some specific cartesian coordinates and add another two fields for which another Maxwell equations ##m_2## holds that however differs only by using having a different ##c_2## in that particular coordinates. Let's do a Lorentz boost: ##m_1## will obviously be invariant, but because ##m_2## adheres to a different Lorentz group associated with ##c_2## its transformation becomes quite messy. This can be remedied however by it pulling back to its natural Minkowski space arising from ##c_2##. Within that geometry ##m_2## becomes Lorentz invariant but this comes at the expense that ##m_1## won't be anymore. Now i don't think a geometry exists that can achieve both equations to have invariant transformation behavior at the same time, so in terms of Riemann geometry we can construct a case where we have two distinct native metrics for the same space where all physics (##m_1## and ##m_2##) take the simplest possible form.

Last edited:
Killtech
I'm not really sure what you are saying here? Are you saying that the identity function from the manifold to itself should let you pull one metric back to become another metric? If so that is not the case, the identity function on a manifold pulls a metric back to the same metric.
The simples case of what i have in mind would be a Weyl transformation. This also uses the ##id## for the pullback. But in this scenario ##id## is neither an automorphism (no self mapping) nor an isometry - as it maps between two actually different metric spaces. It should only be self-homeomorphism in the topological sense because it is a mapping to the very same topological space.

However i don't want the restriction that limits the transformation to remain within the same conformal class.

Last edited:
Staff Emeritus
Homework Helper
Gold Member
2021 Award
It is not clear to me what you are trying to do. An induced metric is the pullback of the metric in the target space of the embedding to the embedded space. The embedded space does not a priori have a metric - the induced metric becomes what it becomes. If you take a manifold M and it can be made a Riemannian manifold (M,g) by the introduction of a metric g, the pullback of g using the identity mapping (i.e., embedding M in itself using the identity map) is going to be g itself - not a Weyl transform of g.

Killtech
It is not clear to me what you are trying to do. An induced metric is the pullback of the metric in the target space of the embedding to the embedded space. The embedded space does not a priori have a metric - the induced metric becomes what it becomes. If you take a manifold M and it can be made a Riemannian manifold (M,g) by the introduction of a metric g, the pullback of g using the identity mapping (i.e., embedding M in itself using the identity map) is going to be g itself - not a Weyl transform of g.
Oh, no no no. I'm definitively not talking about an induced metric. Okay maybe i call my map ##\phi## instead of ##id## to point out it maps between different metric spaces. Furthermore i don't want to pullback the original metric, therefore the image of the map is not an embedded space.

Think of the two different Riemann manifolds ##(M,g)## and ##(N,h)##, except that ##M## and ##N## is actually the same topological space... so ##\phi: (M,\tau) \rightarrow (N,\tau) = (M,\tau)## (where ##\tau## ist supposed to be the topology). Only in that sense ##\phi## is the identity function. You could still pullback ##g## to ##N## but if you do that the induced metric will be exactly ##g## again - as you said yourself. However i explicitly wish to change the metric by not using an isometric map. So in this case if ##g## and ##h## disagree ##\phi## is no isometry, right?

And technically if ##g = f h## for some function ##f>0##, then ##\phi: (M,g) \rightarrow (M,h)## would be a conformal map i.e. a Weyl trafo. but again, i don't really want to restrict to that special case.

Last edited:
Staff Emeritus
Homework Helper
Gold Member
2021 Award
But that is not a pullback then as you wanted in your OP. It is just a map between different geometries. Different geometries will have different physical characteristics - curves will geerally be of different lengths, angles will be different etc. The geometry is part of the physical description and so the physics are different.

Staff Emeritus
But that is not a pullback then as you wanted in your OP. It is just a map between different geometries. Different geometries will have different physical characteristics - curves will geerally be of different lengths, angles will be different etc. The geometry is part of the physical description and so the physics are different.

I think that @Killtech is saying that the same physics can be described by different geometries, if you also adjust the forces (and the laws for how matter and energy affect geometry).

It's sort of trivially true. Suppose we pick some coordinate system ##x^\mu##, and according to the "true" laws of physics (say, General Relativity plus some force law), the path of a particular particle is given by:

##\dfrac{d U^\mu}{d\tau} = F^\mu - \Gamma^\mu_{\nu \lambda} U^\nu U^\lambda##

where
• ##U^\mu = \dfrac{dx^\mu}{d\tau}##
• ##d\tau = \sqrt{g_{\mu \nu} dx^\mu dx^\nu}##
• ##g_{\mu \nu} = ## the metric tensor
• ##\Gamma^\mu_{\nu \lambda} = \dfrac{1}{2} g^{\mu \sigma} (\partial_\nu g_{\sigma \lambda} + \partial_\lambda g_{\nu \sigma} - \partial_\sigma g_{\nu \lambda})##
• ##g^{\mu \sigma} = ## the inverse of ##g_{\mu \sigma}##.

Now, let's let ##g'_{\mu \nu}## be any candidate alternative metric. Then we can in terms of ##g'_{\mu \nu}## compute an alternative proper time ##\tau'##, and an alternative connection ##\Gamma'^\mu_{\nu \lambda}## and an alternative 4-velocity ##U'^\mu##. Finally we can compute (using the "true" laws of physics) the expression

##F'^\mu = \dfrac{d U'^\mu}{d\tau'} + \Gamma'^\mu_{\nu \lambda} U'^\nu U'^\lambda##

Then ##F'^\mu## will in general be a messy combination of the original force vector ##F^\mu## and the original connection coefficients ##\Gamma^\mu_{\nu \lambda}## and the original 4-velocity ##U^\mu##. Nevertheless, presumably it can be expressed as a function of the coordinates ##x^\mu##, their derivatives with respect to the "false" proper time, ##\tau'## via ##U'^\mu = \dfrac{x^\mu}{d \tau'}##, and the false metric tensor ##g'_{\mu \nu}##.

Killtech
This seems very similar to the other question you asked.

Killtech
But that is not a pullback then as you wanted in your OP. It is just a map between different geometries. Different geometries will have different physical characteristics - curves will geerally be of different lengths, angles will be different etc. The geometry is part of the physical description and so the physics are different.
To be honest i am not entirely sure how this type of transformation of an exchange of metrics is to called properly and I am indeed not sure if applying a pullback via a non-isometric map achieves what i have in mind. Generally i am thinking of something akin to Weyl-transformations but to arbitrary metrics thus without the restriction of conformality. In any case @stevendaryl has written down exactly what i am looking for.

As for physics being different, is that really so if you interpret it right? I mean the mapping to another metric should be perfectly reversible so any solution to a physical problem calculated in the alternative metric can be transformed back again to the original metric - i.e. it is still a solution to the original laws of physics in the original metric. Therefore it seems like it is just a mathematical transformation that will still yield the identical predictions albeit in a different calculus.

But my reason to ask this in the first place is that i do not think that lengths "map" to the physical reality in either trivial nor absolute way. Understanding that connection is what in part motivated my question and the fact that math indicates that there are a lot of alternatives - so i am looking for an interpretation of what that means. I arrive at the view that a metric represents rather an actual real object then an absolute length measure: the metric tensor is kind of an infinitesimal representation of a real Parisian meterstick at the given location and each direction (for the imagination it's perhaps easier to use the old SI-definition here). In particular it seems to describe how much a difference in coordinate value is in term of multitudes the meterstick at that location and in the direction of the coordinate - and therefore not in terms of an abstract absolute length. This also makes it tangible as to what an exchange in the metric means.

Killtech
I think that @Killtech is saying that the same physics can be described by different geometries, if you also adjust the forces (and the laws for how matter and energy affect geometry).

It's sort of trivially true. Suppose we pick some coordinate system ##x^\mu##, and according to the "true" laws of physics (say, General Relativity plus some force law), the path of a particular particle is given by:
[...]
Thank you! this is exactly what i have in mind. But is there a general name for these type of transformations? As you can see i am still lacking the terminology to properly express my questions, hence i easily create misunderstands by using a wrong formulation. There is also the issue that i have trouble finding lectures and papers covering such specific topics to learn from so i know how to properly talk about that.

Well, the forums are kind of my last resort to get any help with that.

This seems very similar to the other question you asked.
Yeah, in part they are. But as you can read in the answer just above i have some trouble formulating the questions correctly, hence my questions usually gets lost in the discussion trying to clear up the misunderstandings. But i am learning and as you can see in this thread some are finally able to understand and answer some my questions.

I mean would really love to find some books or papers to read through that cover that specific stuff rather then having to ask this on a forum. But it is what it is.


text:
## Calculus: Early Transcendentals 8th Edition

$(\dfrac{\partial u}{\partial x})^2+(\dfrac{\partial u}{\partial y})^2=e^{-2s}[ (\dfrac{\partial u}{\partial s})^2+(\dfrac{\partial u}{\partial t})^2]$
$(\dfrac{\partial u}{\partial x})^2+(\dfrac{\partial u}{\partial y})^2=e^{-2s}[ (\dfrac{\partial u}{\partial s})^2+(\dfrac{\partial u}{\partial t})^2]$ Here, we have $\dfrac{\partial u}{\partial s}=e^s \cos t \dfrac{\partial u}{\partial x}+ e^s \sin t \dfrac{\partial u}{\partial y}$ and $\dfrac{\partial u}{\partial t}=-e^s \sin t \dfrac{\partial u}{\partial x}+ e^s \cos t \dfrac{\partial u}{\partial y}$ Now, $(\dfrac{\partial u}{\partial s})^2+(\dfrac{\partial u}{\partial t})^2=e^{2s}[(\dfrac{\partial u}{\partial x})^2+(\dfrac{\partial u}{\partial y})^2]$ Hence, it has been proved that $(\dfrac{\partial u}{\partial x})^2+(\dfrac{\partial u}{\partial y})^2=e^{-2s}[ (\dfrac{\partial u}{\partial s})^2+(\dfrac{\partial u}{\partial t})^2]$

format: plain


text:
1. ## Help me please with my revision questions.

Hey all,

Currently revising for my year 12 maths exam need help with the following 2 problems regarding differentiation. Thanks a bunch.

1) An open cylindrical plastic container is to be designed so that it has a capacity of 2000 cm^3. Find the dimensions of the container if the manufacturer wants the surface area to be minimised.

2) A ball is thrown vertically upward with an initial velocity of 19.6m/s. The displacement (in m) of the ball above the ground is s=-4.9t^2+19.6t, where t is the number of seconds elapsed from the moment that the ball is thrown.

i) Find the initial velocity of the ball as a f(t).
ii) Find when the velocity is zero
iii) Find the greatest height reached by the ball.
iv) What is the acceleration of the ball at any time?

Thanks a million!

2. For question number 1, you're gonna need to make a function for the surface area of a cylinder, differentiate it and set it equal to 0, as to find a minimum turning point.
I gave it a try, although I'm not sure if you're supposed to be differentiating pi, so I don't know how to get any further.

3. Originally Posted by Ashgasm
Hey all,

Currently revising for my year 12 maths exam need help with the following 2 problems regarding differentiation. Thanks a bunch.

1) An open cylindrical plastic container is to be designed so that it has a capacity of 2000 cm^3. Find the dimensions of the container if the manufacturer wants the surface area to be minimised.

2) A ball is thrown vertically upward with an initial velocity of 19.6m/s. The displacement (in m) of the ball above the ground is s=-4.9t^2+19.6t, where t is the number of seconds elapsed from the moment that the ball is thrown.

i) Find the initial velocity of the ball as a f(t). Mr F says: Sub t = 0 into ds/dt.
ii) Find when the velocity is zero Mr F says: Solve ds/dt = 0.
iii) Find the greatest height reached by the ball. Mr F says: Sub value of t from ii into s.
iv) What is the acceleration of the ball at any time? Mr F says: Find the double derivative of s with respect to t.

Thanks a million!
1) $\pi r^2 h = 2000 \Rightarrow h = \frac{2000}{\pi r^2}$ .... (1)

$S = 2 \pi r h + \pi r^2$.

Substitute (1) into (2) to get S as a function of r. Solve $\frac{dS}{dr} = 0$. Test nature of solutions. Get value of r corresponding to minimum of S. Sub this value of r into (1) to get h.

4. ## Cylinder

$V=\pi r^2 h$
$S=2\pi r^2+2\pi rh$
where $r$ is the radius, and $h$ is the height.

In order to minimize $S$, we need to write it as a function of a single variable. So we need to write $h$ in terms of $r$. Fortunately, having a specific volume allows us to do just that:

$\pi r^2 h=2000 \\$

$\Rightarrow h=\frac{2000}{\pi r^2}$

now we can substitute this new expression for $h$ back into our original formula for surface area:

$S=2\pi r^2+2\pi r\left(\frac{2000}{\pi r^2}\right)$

which we can in turn simplify to:

$S=2\pi r^2+\frac{4000}{r}$

Now we are ready to minimize this surface area function. Minimum values will occur at critical points--values of $r$ such that $\frac{dS}{dr}=0$. So differentiating we discover:

$\frac{dS}{dr} =4\pi r-4000r^{-2}$

which can be written as:

$\frac{dS}{dr}=\frac{4\pi r^3-4000}{r^2}$

The surface area function will attain an extreme value (minimum or maximum) anywhere that its derivative is zero. solving we find:

$\frac{4\pi r^3-4000}{r^2}=0$

$\Rightarrow 4\pi r^3-4000=0$

$\Rightarrow 4\pi r^3 = 4000$

$\Rightarrow r^3 = \frac{4000}{4\pi}$

$\Rightarrow r=\sqrt[3]{\frac{4000}{4\pi}}=\frac{10}{\sqrt[3]{\pi}}$

$\Rightarrow r\approx 6.828$

So we see that $S$ is at its minimum (you can use the second derivative or a graph to convince yourself that we're not looking at a maximum here) when $r=\frac{10}{\sqrt[3]{\pi}}$. To find the accompanying value for $h$, we can use our value for $r$:

$h=\frac{2000}{\pi r^2}$

$\Rightarrow h=\frac{2000}{\pi \left(\frac{10}{\sqrt[3]{\pi}}\right)^2}$

$\Rightarrow h=\frac{20}{\sqrt[3]{\pi}}$

$\Rightarrow h\approx 13.656$

Collecting our results we find that the dimensions that would minimize the surface area of this cylinder are:

Radius: $\frac{10}{\sqrt[3]{\pi}} \approx 6.828$ cm.

Height: $\frac{20}{\sqrt[3]{\pi}} \approx 13.656$ cm.

5. Thank you all so much!

I now have another stupid question.

If I run hot water into my bath, and then add cold water to cool it down, the temperature of the mixture is a function of the amount of cold water added. In once case, adding x litres of cold water reduced the temperature to T*C, where T=20(x+200)/(x+80)

a) what is the instantaneous rate of change of the water temperature per litre of cold water added? --> I know you have to differentiate this. I couldn't get it to work using the quotient rule. So, I googled it, and used this automatic differentiator thingy, and got this:

So yeah, how did they arrive at that result??

Thanks.

6. Originally Posted by Ashgasm
Thank you all so much!

I now have another stupid question.

If I run hot water into my bath, and then add cold water to cool it down, the temperature of the mixture is a function of the amount of cold water added. In once case, adding x litres of cold water reduced the temperature to T*C, where T=20(x+200)/(x+80)

a) what is the instantaneous rate of change of the water temperature per litre of cold water added? --> I know you have to differentiate this. I couldn't get it to work using the quotient rule. So, I googled it, and used this automatic differentiator thingy, and got this:

So yeah, how did they arrive at that result??

Thanks.
1. I would have thought getting the derivative was a routine application of the quotient rule. It would assist in helping you if you showed your attempt at getting the answer.

2. The answer your "automatic differentiator thingy" gave you is an alternative form of $\frac{-2400}{(x+80)^2}$. As to why it chose to give the answer in the form that it did, computer algebra systems often give unexpected output.


text:
# How do you solve for x in dx-5c=3c?

Mar 22, 2018

$x = \frac{\text{8c}}{d}$

#### Explanation:

Rearrange the equation to solve for $x$:

$\mathrm{dx} - 5 c = 3 c$

$\mathrm{dx} \cancel{\text{- 5c" cancelcolor(red)"+ 5c" = 3c + color(red)"5c}}$

$\mathrm{dx} = 8 c$

$\frac{\cancel{d} x}{\cancel{d}} = \frac{\text{8c}}{d}$

$x = \frac{\text{8c}}{d}$


text:
# statsmodels.tsa.statespace.sarimax.SARIMAXResults.predict¶

SARIMAXResults.predict(start=None, end=None, dynamic=False, **kwargs)

In-sample prediction and out-of-sample forecasting

Parameters
startint, str, or datetime, optional

Zero-indexed observation number at which to start forecasting, i.e., the first forecast is start. Can also be a date string to parse or a datetime type. Default is the the zeroth observation.

endint, str, or datetime, optional

Zero-indexed observation number at which to end forecasting, i.e., the last forecast is end. Can also be a date string to parse or a datetime type. However, if the dates index does not have a fixed frequency, end must be an integer index if you want out of sample prediction. Default is the last observation in the sample.

dynamicbool, int, str, or datetime, optional

Integer offset relative to start at which to begin dynamic prediction. Can also be an absolute date string to parse or a datetime type (these are not interpreted as offsets). Prior to this observation, true endogenous values will be used for prediction; starting with this observation and continuing through the end of prediction, forecasted endogenous values will be used instead.

**kwargs

Additional arguments may required for forecasting beyond the end of the sample. See FilterResults.predict for more details.

Returns
forecastarray_like

Array of out of in-sample predictions and / or out-of-sample forecasts. An (npredict x k_endog) array.

forecast

Out-of-sample forecasts

get_prediction

Prediction results and confidence intervals


text:
# 2D Waterfall Plot Matlab

2D Waterfall Plot Matlab: \documentclass{article} \usepackage{amsmath} \begin{document} \begin {equation} \label{eq:w} S_{\mathfrak{g}_{\mathrm{r}}}(S_{\bm{\omega}_{\{\mathfrak{\sigma}_{\bm{x}_{\text{n}}}(\mathbb{C})\}}})=\frac{1}{2}\frac{1-w(\mathbbm{1}_{\{0\}})}{\mathf{1}}\,,\quad {{\mathfbox{$\mathfra{$}}\mathfrightarrow\$}}\left. \begin{array}{c} {\mathf{w}(\mathbb{\bm{x}}_{\mathbf{x}(\mathbf{y}_{\alpha})})}=\mathf{{\mathfleft{[\mathf{\exp}\left(\mathbf{\sigma}\right){\mathfbrack{\mathfbracket{\mathfleft{\left[\mathbf{\omega}}_{\bm{{\mathrm{\omega}}}(\mathbf{{\mathbf y}}_{\alpha})]}}}{\mathrm{{\mathbbm{\sigma}}}}\mathbb{\mathfright{\rangle}}}}}\}}\,,\quad \mathf{{{\mathfbox{\mathfra{\mathfarray{\mathfarrow}\mathbf{\mathfrowspace}{\mathbb{R}}}\mathfright{{\mathcal{Z}\langle\mathfbrace{\mathfbrace{0\}}}_{\mathbb{{\mathsf{Z}}}}}}}=}}\mathrm\mathfarr{0}{{\mathfcomptimeq}}\mathbf{{{\mathrm{\sigma}}}_{\bm\mathfart{{\mathit{w}}(\mathbb{{{\mathbf x}}}\mathbf{w}^\mathbf)}}=}}\frac{\mathf{{1}}}{2}\,,\label{w_1}\\ \mathbf\mathfarrow{\mathf{\left[{\mathmathfbrace{\mathfgrat{{\mathsmash{0}{\mathsf{\omega}\mathbf\omega}(\mathfrak{{\mathscr{Z}}^\mathrm}{\mathbfnabla}_{\omega_\mathbf}}\mathcal{{\mathmbox{\textbf{h}\mathbf}}}_{\omeg_\mathrm {h}}\mathsca\mathbf}_\mathfarch{\mathbf{d}}_{\omegs}{\mathcal{\mathsf{\sigma}{\mathsc}}}_\mathsf{{\mathbm{\omeg}}}_{\alpha}}\mathsf\mathrm {{\mathbbp{\sigma\mathbf}}}_\omega\mathbf 1\mathbf {\mathsf{w}\mathbf{{}\mathsf{\mathsf{h}}}}\right]}}\,,& \qquad {{\mathbf w}^\text{1}\mathbf {\omega}^\alpha}={{\mathb{\mathframes{0}{n}}}({\mathsf {\omega}\omega_{\mathsf {n}}}\mathsf{1}_\omeg\mathbf 0\mathbf k)\mathsf{\vartriangle{\mathbf{{w}}}^\alpha\mathbf {{\mathrm {\sigma}}\mathbm{w}},}}\,, \label{eq_w1}\\ \mathbf\end{array} \label {w_2} \mathsf \mathfarr{\mathfedge{{\mathname{w}}^\alpha}}_{\{\alpha\}}=\frac{{{\mathsf {\rm{\szt}}}}}{{{\mathszt}-{{\mathtt {1}}}}}\,,& \quad \mathscal{w}_2D Waterfall Plot Matlab The matlab provides a method for drawing a plot of a given piece of data into a data frame using Matlab. The matlab function draws the data frame using the same data model as the original data. This method is called matplotlib and can be used to draw data from the original data frame. The following examples are examples of the matlab function: import numpy as np import matplotlib.pyplot as plt x = np.linspace(-1,2,3) y = np.zeros((4,3)) y.shape = (4,3) p = matplotlib x.set_xticks(x,y) plt.xlim(y[0],y[1]) plt[:3] = x plt # to draw the plot to the right 2D Waterfall Plot Matlab It is believed that the waterfall plot will contain the vast majority of the water under the earth. Due to the high pressure of water such as the volcanic or Antarctic plumes, the waterfall is likely to fill around the entire surface of the earth. It is believed that by measuring the waterfall depth in the earth, it will better be able to predict the cause of the anomalies in the waterfall. At the current location of the crater, the water fall is at a depth of over 100 meters. This is a good distance for an accurate measurement of the waterfalls in the earth. The waterfall depth is estimated at the height of the peak of the crater as the peak of a crater is at the same height as the surface of the Earth. The Earth falls at a depth which is about 20 meters. This value is related to the waterfall height which is the height of a crater. The height of a human head is about 260 meters. A crater is about 20 feet high and 20 feet below the surface of Earth.


text:
# Cross levels or interaction term for repeated measures multilevel model?

I'm new to both regression and multilevel modelling, and I'm having trouble with the analysis for my experiment design.

For my study, we are having subjects come in and solve 2 problems. Each problem $$P$$ has 2 $$variants$$, lets call them $$A$$ and $$B$$. Variant $$A$$ is the control, and variant $$B$$ is created by making a modification to variant $$A$$. Each subject receives each problem and each variant. For example, a subject could receive variant $$A$$ of problem 1 and variant $$B$$ of problem 2, or variant $$B$$ of problem 1 and variant $$A$$ of problem 2. So basically a subject won't get the same variant twice or the same problem twice.

The response variable is some performance metric $$Y$$. I am interested in the impact of the variant on $$Y$$.

The variants might have a different effect based on the problem used to create it, as some problems might inherently be more difficult than others. Also, individuals are expected to have inherent differences in their performance metric $$Y$$.

So far, I know that the measurement occasion will be Level 1 and participant Level 2, and that I'm going to use the treatment($$variant$$) as a fixed effect. But I'm not sure how to integrate the problem $$P$$ into the whole situation here. I'm not sure whether to use the $$P$$ as level 3 as follows:

$$Y = variant + (1 | P) + (1 | participant\_id)$$

or if I should model it as an interaction

$$Y = variant * P + (1 | participant\_id)$$

I think that using it as a level better represents the hierarchy of my data, but because I only have 2 levels for $$P$$, I don't think that's a large enough group size for to use it as a level. What do you think?

• How many problems are there ? – Robert Long Oct 31 '19 at 11:13
• Only 2 problems. But I'm also planning to use this experiment design for other experiments where participants will get more problems, but the number of problems should never exceed 4 (due to time constraints). – Devjeet Roy Oct 31 '19 at 15:23

You can't model it with (1|P) if there are only 2 levels of P since you will be asking the software to estimate the variance if a variable from only 2 observations.
If you want to treat P as random then you could use (1|P:ParticipantID)
Or you could treat P as fixed, as in your 2nd example.
• Thanks Robert! I have a similar question about incorporating time, to see if participants performing worse on the second problem due to fatigue from the first, or conversely, if they perform better on the second problem due to some kind of order effect. Because time $T$ again has 2 levels, I'm guessing incorporating it as a fixed effect would be the way to go? – Devjeet Roy Oct 31 '19 at 16:03


text:
## Archive for the ‘C++’ Category

### Back from NWERC 2011

Monday, November 28th, 2011

Hi folks!

This weekend I participated at the North Western European Regional Contest, a regional preliminary round for the ACM ICPC. It is an international students contest about solving as many as possible out of 10 algorithmic problems in 5 hours in teams of three students and one PC. It was my first time there and it was quite fun.

At saturday we visited the historic harbour of Bremen Vegesack, which was partly boring and partly quite nice. At sunday there was the actual contest at the quite decadent and walled Campus of Jacobs University in Bremen (you even have to pay tuition of ~€25000, ~$33000 per year, at public universities you pay about €400-1400, I could live from it for long time, but even at elitist economical universities like EBS and WHU you have to pay much less). We used KDevelop 4.2 for solving the tasks and enjoyed the nice completion, source code reformatting (nice when you are not sure any longer which braces belong together and do not have much time :)), and inline documentation of STL functions. Thank you, KDevelop guys. Our team from RWTH solved only three out of 10 tasks (30st place out of 70). B and E were quite trivial (I did not even had to read B since my team members solved it). I want to tell a bit about the other problems, I hope it is interesting for some of you. Of course you may try to solve the problems your self, it is quite a lot of fun. ### A Given a natural number x<10^15 we should compute all n,k such that binomial(n,k)=x. It was quite simple, but we had a bug in our implementation and I do not have any clue what the problem was. We chose to check the cases binomial(n,1)=n and binomial(n,2)=n·(n-1)/2 manually and brute force the solution for all other cases by computing lines of Pascal’s triangle for k values such that binomial(n,k)≤x and terminating when binomial(n,2)>x. Alternatively you could check more terms explicitly (the team from LMU did it) and compute the whole triangle for the remaining values or use binary search to find the parameters. ### C Given a sequence of films watched by a person we should answer for each time position how many different films have been watched since the last time he watched the current one. By maintaining a binary tree containing the films ordered by the last time they were watched and a map containing this time for each movie this queries can be easily answered to if you have a way to get the number of nodes after a specific one in the tree in O(log n). That for you would have to store the size of each subtree and STL set/map unfortunately do not support this. Thus we decided to write our own tree, we went for a Treap with random priorities since it is the easiest way to avoid degeneration (easier to implement than AVL and Red-Black trees). Unfortunately we did not have enough time for debugging the tree and we even forgot to update the counters when balancing the tree after insertion. There were simplier solutions using segment trees. For this task there were particularly many wrong submissions (the man presenting the solutions assumed that many teams tried to solve this one because the first team solved it yet after 20 minutes and thought it would be the easiest one, he even presented a very funny solution using java.lang.String. a linear time Java indexOf() call, which was of course way too slow). ### D This task was about deciding whether it is possible to partition a given pattern of black and white square into disjoint, L-shaped “puzzle pieces” of one black (in the corner) and two white squares. We had no idea how to solve that, we thought a lot about backtracking, but there semt to be no clever way to do that in polynomial time. The trick was to encode this problem in Boolean formulas and to use a standard algorithm (e.g. resolution) for the 2-SAT problem using variables encoding “white square x,y belongs to the same puzzle piece as the white square x+1,y+1“ etc. ### F Nobody solved this problem at the contest (though there were some people at the semi-live contest at Spoj solving it, a coach of another team said he knew a very similiar task from a different contest). Look at it, it looks like really complicated spam. Only one team tried. Cool geometric structures, quad-trees etc. will not help you to solve this problem: 500×500 fields, each one is either water or grass. You want to build a pool area. The border has to be grass and every pool of water has to be surrounded by a wall, which will cost$a per wall. You can transform water fields into grass, which will cost $b per field, and grass into water for$c. You want to build the cheapest pool area possible.

Actually it is a simple max-flow problem, since a minimum cut in a certain flow encoding the landscape is the optimal solution. You have a source, a sink and a node for every field. A cut should divide the nodes into water-nodes and grass-nodes. Source-to-x edges should have a capacity of the price needed to transform x into a grass-field and x-to-sink edges should have a capacity refering of the price needed to transform x into a water-field, unless the node represents a field at the border, then the capacity should be infinity. Additionally you add x-to-y nodes with a capacity of the price needed to build a wall for adjacent nodes x and y. That is it (if I am not wrong, I hope so :D). Really awesome.

### G

I will post a full description later. For each observation you can yield an inueqility and you can complete the information in a Floyd-Warshall-like manner.

### H

Spam. You have 13 out of 52 regular playing cards and want to partition it into as few as possible bunches of single cards, pairs, triples, quadruples, full-houses and streets of at least five consecutive cards. You can simply use brute force: Test all combinations of up to two full-houses and up to two streets (cannot be more for 13 cards) and greedily take the remaining cards as quadruples, triples, pairs and single cards. We tried that with a lot of copy-and-paste code and our program printed wrong answers, but we have no idea in which cases it failed. Alternatively you can choose a probably more compact solution by building a directed acyclic graph of all 2^13 combinations of your cards where edges represents adding one of the allowed bunches. Then you use breadth-first-search to get the solution. This was one of those typical tasks with useless information in the input (cards were encoded as 4h for ♥4 and Jd for a ♦Jack, in fact the suits did not even matter).

### I

Given integer coordinates of up to 10000 RFID chips, 250000 RFID sensors and 25 walls compute which sensors can detect which chips. Each sensor can detect any chip within a radius of r, while walls reduce the radius by 1. No two sensors are closer to each other than r (“due to interference”^^). We used a sweep-line algorithm. Whenever the sweep line reaches the value x where x+r is the abscissa of a product we add the product to an ordered binary tree (std::set in C++) ordered by the ordinate. When reaching the value x where x-r is the abscissa of a chip we erase it from the tree. If x-r is the abscissa of a sensor we query all products in the tree with ordinates between y-r and y+r using lower_bound and upper_bound where y is the ordinate of the sensor. We count the number of walls intersecting the line between sensor and chip (we check that by adding up angle(p1, q1, p2)+angle(q1, p2, q2)+angle(p1, q2, p2)+angle(q1, p1, q2), which should be 2π (aka 360 degrees) for intersecting line segments) and check whether the chip is within the resulting reduced radius. This solution has a complexity of O((n+m)log(n+m)+n·w) where n is the number of chips, m the number of sensors and w the number of walls. This is guaranteed since the distance between any two sensors is at least r, thus at most 7 sensors can detect one chip (imagine a regular hexagon of sensors with one sensor in the center). Thus for many walls you would probably require a more sophisticated algorithm taking walls into account when sweeping.

Surprisingly only 7 teams solved it, I thought it would be kinda a standard-geometric-sweep-line-problem, it was even easier than E for us (there we used int instead of long long :D). Alternatively you can use binning (since the coordinate space is limited) or quad-trees to solve this problem.

### J

You have a couple of train-stations and ≤1000 connections between these stations. Each connection will be once an hour at a certain minute (e.g. 13:47, 14:47 and so on). However, there is a certain probability that the train will be too late. If it is too late the delay is uniformly distributed in a range from 1 to some number ≤120. You have to compute the minimum expected duration of a trip from the start to the target. We solved that problem by a fixed-point iteration: For each station and each minute (0≤m<60) we store the best known expected duration to the target. We propagate that information till it does not change any longer. Unfortunately it timed out, probably because of floating point issues: we recognised changes which where insignificant or caused by rounding. Only one team solved this problem, three teams tried.

### Subsumption

Yesterday I returned from Bremen, entered the first train at about 17:00, arrived at 0:45 and slept till 12:00. It was a really nice experience. If you are a student, like algorithms and want to participate: go ahead, look for two comrades, ask your professor to register you and join your regional contest! (at some universities there is a local preliminary contest)

PS:
Some visual impressions:

:)

The camera of my N97 mini mobile phone had a bug or something like that, however, when trying to photograph an ugly super market or something like that in the early evening and accidentally moving the camera too early I got this nice photo. Could not reproduce.

Could not reproduce :(

PPS:
The contest was sponsored by Facebook and we had to attend a boring presentation of a Facebook employee. It was quite funny how he tried to make advertisement to work there. He assumed everybody in the room would use Facebook, what? We could get free t-shirts when answering his silly questions, did he think we would like to work there because of a t-shirt? It happened multiple times that he said that he is not allowed to tell about xy, really a great opportunity to work for a company where you cannot even superficially talk openly about the things you are doing there. And he told us that they would finally delete all messages six days after you have pressed the delete-button, haha.

PPPS:
I have pushed some solutions here.

### KDevelop-PG-Qt 1.0 Beta

Tuesday, October 4th, 2011

Today KDevelop-PG-Qt 1.0 Beta (aka 0.9.82) got released, the parser generator used by several KDevelop (and Quanta) language plugins. There are some new features, and various bugs have been reported in the last few months since 0.9.5 and are now fixed.

### New features

Most effort has been spent for implementing the lexer generation. You can now write a simple specification of the lexical structure by using regular expressions, the generated token stream class, which generates tokens from the input-data, can be used directly by the generated parser, but you can also just create a lexer without a parser. Thus, despite the name, KDevelop-PG-Qt is no longer just a parser generator. My motivation for writing the lexer generator was the lack of decent Unicode support in most lexers. Quex is quite good, but it is not free software (despite the LGPL based license) because of excluding military usage. The lexer can not only read different encodings, but also use different encodings for internal processing, e.g. it can either convert a UTF-8 stream to UTF-32 first or directly operate on UTF-8 bytes. Simple example:

%lexer ->
for FOR ;
"some keyword" SOME_KEYWORD ;
{alphabetic}* WORD ;
;

It does also include limited support for look-ahead (full support like in Flex make generated code more complicated and inefficient), and a simlar – but in my experience more useful for modern languages – feature called “barriers” which will be explained in the documentation soon.

The API used by the generated files has been cleaned up, some method names were very counterintuitive, some methods were not used at all. This break requires updating KDevelop-PG-Qt to build the latest versions of PHP, QMake, SGML and CSS plugins (you may have to do a clean build).

There are also some minor new features: AST structs now get forward declared reducing dependencies, code which relied on definitions at some places has been fixed some time ago. The token types do not get declared by the parser any longer. Additionally you no longer need “;;” in the grammer files, though it is still supported for compatibility.

### Bug fixes

The bug fixes include proper line numbering. In GCC you can now see correct line numbers refering to the location of wrong code in the grammer file, for other compilers you may have to activate the –use-line-directive, then it will use the #line directive instead of the GCC specific syntax, but you will not see the location in the generated code. The CMake-macro will do that automatically. Some compatibility errors have been reported reported by Fedora and Debian packagers and fixed, special thanks to them. KDevelop-PG-Qt builds with QT_STRICT_ITERATOS now and also builds under Windows with MSVC (MSVC is not perfect for C++11 and Flex is not perfect for Windows). Annoying wrongly formated error messages in the lexer and parser of KDevelop-PG-Qt have been fixed, too.

Some bug fixes might be necessary, thus there is this beta-version first. There is some work to do now first: The documentation and the kate grammar file for proper syntax highlighting have to be updated.

### C++11

This is the second release using C++11 features, especially the auto keyword and STL hashes (unordered_map and unordered_set). I had used variadic templates before to construct UTF-8 automata, but for compatibility with MSVC it has been replaced with a Ruby script generating some code, the variadic template had been quite ugly anyway.

### Future development of KDevelop-PG-Qt

• Parser and lexer should be rewritten using KDevelop-PG-Qt
• Long requested: there should be a way to mark conflicts as resolved, that for the conflict reporting has to be refactored a bit
• The next release will hopefully support LL(k) parsing, making some stupid look-aheads obsolete
• Cleaning up further code

Special thanks to Milian Wolff for all his patience, bug reports and support with the release.

I will post the link to the tar-ball as soon as it is uploaded, there is only the tag for now.Tar-ball can be found here.

### Unexpected Bottle Neck: vector<bool>

Tuesday, August 23rd, 2011

Hi folks!

The last paragraph is actually the interesting one for every C++-programmer, the leading-in might not be understandable.

The new lexer component of KDevelop-PG-Qt is not very fast, it can take several minutes with complex grammars, especially when using UTF-8 as internal encoding for the automata. Of course, first I want to finish the most important features and that for I am writing an example lexer for PHP to check its capabilities to spot bugs and missing features, but now I was curious and asked Valgrind/Callgrind for analysis. I expected a lot of useless copying/assignments because I have not done any optimisation yet and tried to be “defensive” by using too much copying. Indeed: For my first example about 78% of the runtime were spent on copying. But then I tried a full (as far as it is finished) PHP example with UTF-8 and it was a real surprise:

KCacheGrind Overview

It spends most of the time with comparing instances of std::vector<bool>! For the powerset construction I have to maintain following states for subsets of states in the NFA and after that I map those subsets to new unique IDs for the states of the DFA. For both cases I wanted to use a map with vector<bool> (a subset of states) as key_type, I could not decide if I should use map or unordered_map – I used map, but there is also some code to make it possible to use QBitArray with unordered_map, just for the case. However: I expected the minimisation to be a bottle neck (disclaimer: I stopped valgrind after some time, maybe it becomes a bottle neck later), but now the comparisons used in the map-implementation are crucial. I was not very economical with those map-operations – I could have done the mapping while computing the necessary subsets, it has to be optimised and I may use unordered_map and unordered_set (hashes) instead of map and set, but that is not the reason why I am writing this blog post.

The interesting thing about it is the usage of std::_Bit_reference. std::vector<bool> has a specialised implementation, the booleans get packed, thus it will only need size()/8+const Bytes when it is full. There is a special hashing-implementation directly using the integers used to store the bits, but there is only a generic comparison implementation. Thus it will iterate over all the bits, instead of using comparisons of chunks (like 32 or 64 bit, depending on the CPU). Of course it will be much slower, keep in mind that each iteration requires some bit-manipulation. Especially in my case of a red-black-tree the vector will get compared to very similar ones next to it in the tree, and in that case it takes especially long time. Be aware of vector<bool>, it is often awesome (safe a lot of memory), but something like this slow comparison may happen, and always keep in mind that the index-operator might be slower than for vector<char&gt. Unfortunately there seems to be no API for accessing the integer-chunks. Btw. QBitArray does not support comparison at all. I have filed a bug-report to GCC/libstdc++.

### Regarding Dynamic Typing

Sunday, July 10th, 2011

Currenty there seems to be a big hype about EcmaScript (JavaScript). Google probably wants to enslave the world with Chrome OS, where the system is not much more than an EcmaScript virtual machine provider (maybe it will support native applications through NaCl, like Android does not only allow Java…), Microsoft wants to reimplement their Windows interface, Qt invented QML, the EcmaScript extension we all know about, providing cool declarative features. Today I want to talk about a fundamental property of EcmaScript and why it just sucks: dynamic typing.

### Clarification

First let us clarify the meaning of “dynamic typing”. “Dynamic typing” means that the type of expressions gets checked at runtime, expressions which may have any type are possible. It should not be confused with duck typing, e.g. many types using dynamic typing have a lot of built-in functions relying on specific types (“the frog will not get accepted”), e.g. most functions in PHP’s standard library (expecting string, integer, array or what ever). But for example C++ function templates in etc. provide duck typing (they will accept anything looking like an iterator), or the signatures in old g++ versions provided duck typing. Determining types may happen at compile time (type inference) even with dynamic typing, and of course optimising compilers/interpreters are doing that.

### Impact on Development

Let us talk about an argument for dynamic typing: it makes life easier. Actually, that can be right, there are domains where you just do not want to care about such stuff, for example when writing a shell script with few lines of code or when quickly doing some calculations with a computer algebra system. But Typo3, MediaWiki, Windows, Plasma etc. are much more than that. Why do I doubt that dynamic typing makes life easier in those contexts? Because it is error-prone. It is always better when errors get detected at compile time. It is good to fulfill contracts when programming, and they should get verified at compile time, such that they can be easily found and will not annoy the user. A type of contract (not the only one, cf. design by contract) which has been used for long time is the type system. The programmer assures that a variable has a certain type. What happens in dynamically typed languages? You do not have to state the contract, the compiler (or code checker) will usually not be able to check it, it is just in your brain, but of course you will still rely on that contract, the type is something you rely on most of the time when programming, I know that x is an integer when using x for some arithmetics. But you will do mistakes and you get buggy software. That is the fundamental disadvantage when programming, but of course I have to compare it to the advantages of dynamic typing: you can write code quickly and efficiently not mentioning the type everywhere. But there are more proper ways to achieve that: use type inference. The type of a variable will be determined by the compiler when initialising it and you will get an error when you are trying to change the type. That is good because in most cases the type of a variable will not change. And you will get informed about undefined variables (a typo should not cause a runtime error, but in dynamically typed languages it does). For the case that you need a structure allowing different types at the same position there are algebraic data types. With algebraic data types you can state a contract with only few tokens (instead of a nested array/dictionary data structure with a layout which is just implicitly given by the manipulation of it, that does often happen in dynamically typed languages), for variable declaration you only need one token, maybe a single character. That minimalistic overhead in code length is definitely worth it once the software has reached a certain complexity. That threshold is probably not very high, annoying mistakes which could have been avoided with static type checking can already occur in small programs just computing some stuff or something like that.

### Performance

Dynamic typing causes big overhead because instructions have to be choosen at runtime based on type information all the time. Of course it is much more complicated to optimise dynamically typed languages, there might be corner cases where the type is not the expected one, but the runtime has to care about it etc. I often read statements like “the performance critical parts are implemented natively” etc., but regarding the amount of applications running using such languages (JavaScript, PHP, Ruby, Python, Lua) we have to state: it is performance critical, PHP is used for more than a preprocessor, QML is used for more than just representing the UI, JavaScript is used for drawing a lot of complex stuff in the browser, Python gets used for scientific computations, and Ruby is establishing new standards regarding overhead (that is not true, Scheme has been that slow before ;), but Ruby allows modifying a lot of stuff at runtime, too). There is reasonable overhead—for abstraction, generalisation, internationalisation etc., but dynamic typing affects nearly any operation when running the program, that is unreasonable and of course it will sum up to significant overhead, although it is simply not needed (and bad for environment ;)).

### Special Issues

#### Regarding extreme flexibility

First of all: in 95% of applications you do not need it, you do not have to modify types at runtime, adding member functions to classes or objects and all that stuff. Sometimes it may be a good way to establish abstraction etc., but in those cases there are usually alternatives: meta-programming can be done at compile time, when manipulating all the types in Ruby they usually could have been manipulated at compile time, too, but Ruby does not support sophisticated compile time meta programming (ML and Template Haskell do, in C++ and D it is kinda limited). Regarding collection of information, debugging etc. using such features: debugging facilities should not influence the performance and cleanness, I am sure by involvement of meta programming you could implement language features allowing that when debugging without neglecting the type system. And of course a lot of flexibility at runtime can be achieved without allowing any type everywhere: dynamic dispatch (including stuff like inheritance, interfaces, signatures and even multi-dispatch), variant types at few places (e.g. QVariant, although I think it is used too often, signals can be implemented in a type safe way, and there are those type safe plugin factories as alternative to QtScript and Kross), signals and slots, aspects etc.

#### Regarding EcmaScript

You might say that EcmaScript is becoming fast enough because of good compilers and extensions like type safe arrays (e.g. containing only floating points). But EcmaScript will stay EcmaScript, it will keep the downsides of dynamic typing, those type safe arrays are an ugly hack to make it feasible for some specific applications. It is simply lacking a proper type system and it will not get it.

#### Regarding QML

Using EcmaScript for QtScript was a pragmatic choice, no awesome innovation: there were many web developers knowing about JavaScript. Unfortunately that caused yet another way to integrate scripts and certainly not the most flexible one (cf. my previous blog post), for some reason they did not want to reuse KDE’s innovation (like QtCreator and KDevelop, but that is really a different topic…). QML is based on EcmaScript because QtScript had been based on it before. Dynamic typing is definitely not an inherent property of such declarative UI, most of it could have looked the same with a native implementation based on C++, but also implementations in Ruby or whatever would be easily possible. I have to admit that C++ is not perfect, it does not provide sophisticated meta programming, algebraic types or one-letter type inference (“auto” has four letters ;)), the last one may be a small problem, but overall it is simply not simple enough ;), languages like Scala, D and OCaml have certain problems, too. Hence some of the non-declarative code in QML would have been disproportionately complicated compared to the declarative code. The general approach of declarative UI is certainly good, and now we probably have to accept that it has been implemented using EcmaScript, we can accept it, as long as it is still possible to write Plasmoids using C++ or whatever etc.—obviously that is the case. Thus QML is generally a good development in my opinion, although implementing program logic in it is often not a good idea and although dynamic typing leaves a bitter aftertaste.

I hope you have got my points about dynamic typing. Any opinions?

Wednesday, March 23rd, 2011

Hi!

#include <iostream>
using namespace std;

// a struct, because there are no partial specializations
// for functions
template<typename... args>
struct Print
{
// checking, because you cannot explicitly construct
// a parameter pack of strings
static_assert((sizeof...(args)) == 0, "illegal arguments");
static void exec()
{
}
};

template<typename... args>
struct Print<string, args...>
{
static void exec(string x, args... rest)
{
cout << x << endl;
// recursion, because there is no static-for (ammendment: unlike the foreach for tuples in D)
print(rest...);
}
};

// that function works
// but it would be probably three lines in D
template<typename... T>
void print(T... args)
{
Print<T...>
::exec(args...);
}

I think you see what I meant, variadic templates are nice for printf and tuples, but for any slidely different tasks they are still ugly.

Yes, I used it, really (skip deleted files and minor edits), it was ugly, but it provides some abstraction making the code – probably not readable – at least less redundant (I do not like copy&paste programming, the reason for copy&paste programming the lack of nice meta-programming features). Some last words why I am not using D: in C++ I can achieve anything using templates and implicit casts, and I have real value-semantics, D did not want to be like Java, but it forbids some stuff which is responsible for a lot of flexibility in C++. And if I would switch the language, I would try to choose a language involving some new, innovative and consistent concepts, that is not the case for D, maybe for Scala, but it does not allow value-semantics, too.

### Equal rights for the void!

Wednesday, March 9th, 2011

Hi!

This post may sound strange, but it is about programming languages, so do not care, if you are not interested in programming.

Well, today I want to talk about the type “void” in many programming languages. It is a really special type, because actually it does nothing. In Java you cannot do a lot with this type, I think the only valid usage of “void” is for methods’ result-type, void is not really a type in Java, it is more like the procedure-keyword in Pascal. In Java there are some relicts from C which do not actually fit into the concepts of the language (e.g. switch). However, in C and C++ you can do more with void, it is somehow a “real” type. Such features may appear weird at the first look, but I think they are really nice:

• You have void-pointers, you can cast any pointer into a void-pointer – explicitly or implicitly
• You can cast any value into a void-value, which you canot use then – explicitly or implicitly (cf. the definition of Q_UNUSED)
• You can return any value from a void-function

Well, for long time I could not imagine what this could be good for. But now I think: that is really beautiful. When should implicit casts be allowed? When thinking about it, you may notice two cases: coercion from one type into a more powerful one (e.g. int → long), and coercion from one type into a more general, weaker one (e.g. QWidget* → QObject* or iostream& → istream&). But it is basically the same, consider types as sets or families of possible values/objects, implicit coercion from type A into type B is possible, iff A ⊂ B (A subset of B). And any operation supported for elements of B should be supported by elements of A. Which operations are supported for values of the type void? No operations, so all operations supported for void are supported for all the other types, why should we not cast from any type to void?
That is supported by C++. But unfortunately there are limitations: You cannot have void-variables or constants, but that would nicely fit into the concept and sometimes it would make generic programming easier. You cannot dereference a void-pointer, but why should it not simply be a void-value as usual? And of course it should be possible to allocate void on the heap, it should be just NULL, and the address of a void-value should be NULL, too. It is okay for me, if the compiler wants to warn you about your usage of void, but just for consistency in the language void should not be that different from the other types, and not having variables of that type is simply not very nice. Equal ights for the void!

However, there are two things which may be not so nice: 1. When considering two sets represented by two types and one set should be a superset of the other set, you have to consider some elements of those different sets being equal, and of course in practice you do it all the time when comparing ints with shorts etc., but for voids that is impossible, you cannot decide, if two void-values are equal, and 2. you cannot explicitly cast back from a void-value to a non-void-value. However, void-values are not the only ones, where comparison is impossible, though for the most frequently used types it is of course possible. Consider functions (handled at runtime) internally stored using some kind of an arithmetic formulas, Turing-machines, Lambda-calculus or whatever. Generally it is not possible to decide, if two of such functions are equal (unless the arithmetics are too simplistic), notice that there are many different representations for the same function. So requiring values to be comparable is not very clever in a general-purpose programming language. In practice for some types you may not even want to support the equality-test, because it may be difficult to implement or very slow or something like that. That are my reasons, why I think that the first issue is void. I currently cannot imagine any two types different from void where explicit casting is only possible in one direction. Maybe you can? However, if the type does not support equality-checking, after casting back and forth you cannot even say that the value is identical to the original one. But this issue remains unsolved. However, altogether I think that void should be a real type in our programming languages, because it is very consistent, and it should be different from nil/NULL/None, because nil/NULL/None should indicate the absence of a value of one specific type, and not the void.

Or I can put it that way: The void is like qualia: it is everywhere, it is contained in each individual, it does not express anything specific, you cannot differentiate between “my” and “your”, and of course you cannot cast it back to the individual with its personality.

PS: My statements about allocation a position 0 were wrong in my opinion. Cf. the comments.


text:
# Lightman et al Problem 3.24

1. Jul 15, 2008

### jdstokes

I'm confused about the wording of this problem,

They define the wedge product by $u \wedge v = u\otimes v - v\otimes u$ but as far as I can tell this operation is not associative!

2. Jul 16, 2008

### George Jones

Staff Emeritus
They have not tried to define an associative algebra, i.e., the exterior algebra, in this question.

They have defined meanings for the the abstract symbols $u \wedge v$, $u \wedge v \wedge w$, and $u \wedge v \wedge w \wedge x$, where $u$, $v$, $w$, and $x$ are all arbitrary vectors.

Their definitions can be extended to the definition of the exterior algebra, but this is not needed to do the question.

3. Jul 16, 2008

### jdstokes

If the operation is not associative then an expression such as $u \wedge v \wedge w$ is not defined because the order of operations is not specified.

4. Jul 16, 2008

### George Jones

Staff Emeritus
They have defined what this symbol means. Don't think of it as the product of two wedges, think of it as one symbol.

Consider all possible permutations of the juxtaposed symbols $uvw$. Stick a + in front of the permutation if it is an even permutation of $uvw$ and and a - in front if the permutation is odd. Add all the terms, and insert tensor product symbols.