text:
## Horner’s Rule

This post is about my all-time favourite calculation, of a linear-time algorithm for the maximum segment sum problem, based on Horner’s Rule. The problem was popularized in Jon Bentley’s Programming Pearls series in CACM (and in the subsequent book), but I learnt about it from Richard Bird’s lecture notes on The Theory of Lists and Constructive Functional Programming and his paper Algebraic Identities for Program Calculation, which he was working on around the time I started my DPhil. It seems like I’m not the only one for whom the problem is a favourite, because it has since become a bit of a cliché among program calculators; but that won’t stop me writing about it again.

## Maximum segment sum

The original problem is as follows. Given a list of numbers (say, a possibly empty list of integers), find the largest of the sums of the contiguous segments of that list. In Haskell, this specification could be written like so:

$\displaystyle \begin{array}{lcl} \mathit{mss} &=& \mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{segs} \end{array}$

where ${\mathit{segs}}$ computes the contiguous segments of a list:

$\displaystyle \begin{array}{lcl} \mathit{segs} &=& \mathit{concat} \cdot \mathit{map}\,\mathit{inits} \cdot \mathit{tails} \\ \mathit{tails} &=& \mathit{foldr}\,f\,[[\,]] \quad\mathbf{where}\; f\,\mathit{x}\,\mathit{xss} = (\mathit{x}:\mathit{head}\,\mathit{xss}):\mathit{xss} \\ \mathit{inits} &=& \mathit{foldr}\,g\,[[\,]] \quad\mathbf{where}\; g\,\mathit{x}\,\mathit{xss} = [\,] : \mathit{map}\,(\mathit{x}:)\,\mathit{xss} \end{array}$

and ${\mathit{sum}}$ computes the sum of a list, and ${\mathit{maximum}}$ the maximum of a nonempty list:

$\displaystyle \begin{array}{lcl} \mathit{sum} &=& \mathit{foldr}\,(+)\,0 \\ \mathit{maximum} &=& \mathit{foldr}_1\,\max \end{array}$

This specification is executable, but takes cubic time; the problem is to do better.

We can get quite a long way just with standard properties of ${\mathit{map}}$, ${\mathit{inits}}$, etc:

$\displaystyle \begin{array}{ll} & \mathit{mss} \\ = & \qquad \{ \mbox{definition of~} \mathit{mss} \} \\ & \mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{segs} \\ = & \qquad \{ \mbox{definition of~} \mathit{segs} \} \\ & \mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{concat} \cdot \mathit{map}\,\mathit{inits} \cdot \mathit{tails} \\ = & \qquad \{ \mbox{naturality of~} \mathit{concat} \} \\ & \mathit{maximum} \cdot \mathit{concat} \cdot \mathit{map}\,(\mathit{map}\,\mathit{sum}) \cdot \mathit{map}\,\mathit{inits} \cdot \mathit{tails} \\ = & \qquad \{ \mathit{maximum} \cdot \mathit{concat} = \mathit{maximum} \cdot \mathit{map}\,\mathit{maximum} \} \\ & \mathit{maximum} \cdot \mathit{map}\,\mathit{maximum} \cdot \mathit{map}\,(\mathit{map}\,\mathit{sum}) \cdot \mathit{map}\,\mathit{inits} \cdot \mathit{tails} \\ = & \qquad \{ \mbox{functors} \} \\ & \mathit{maximum} \cdot \mathit{map}\,(\mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{inits}) \cdot \mathit{tails} \end{array}$

For the final step, if we can write ${\mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{inits}}$ in the form ${\mathit{foldr}\,h\,e}$, then the ${\mathit{map}}$ of this can be fused with the ${\mathit{tails}}$ to yield ${\mathit{scanr}\,h\,e}$; this observation is known as the Scan Lemma. Moreover, if ${h}$ takes constant time, then this gives a linear-time algorithm for ${\mathit{mss}}$.

The crucial observation is based on Horner’s Rule for evaluation of polynomials, which is the first important thing you learn in numerical computing—I was literally taught it in secondary school, in my sixth-year classes in mathematics. Here is its familiar form:

$\displaystyle \sum_{i=0}^{n-1} a_i x^i = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} = a_0 + x(a_1 + x(a_2 + \cdots + x\,a_{n-1}))$

but the essence of the rule is about sums of products:

$\displaystyle \sum_{i=0}^{n-1} \prod_{j=0}^{i-1} u_j = 1 + u_0 + u_0u_1 + \cdots + u_0u_1\ldots u_{n-1} = 1 + u_0(1 + u_1(1 + \cdots + u_{n-1}))$

Expressed in Haskell, this is captured by the equation

$\displaystyle \mathit{sum} \cdot \mathit{map}\,\mathit{product} \cdot \mathit{inits} = \mathit{foldr}\,(\oplus)\,e \quad \mathbf{where}\; e = 1 \mathbin{;} u \oplus z = e + u \times z$

(where ${\mathit{product} = \mathit{foldr}\,(\times)\,1}$ computes the product of a list of integers).

But Horner’s Rule is not restricted to sums and products; the essential properties are that addition and multiplication are associative, that multiplication has a unit, and that multiplication distributes over addition. This the algebraic structure of a semiring (but without needing commutativity and a unit of addition, or that that unit is a zero of multiplication). In particular, the so-called tropical semiring on the integers, in which “addition” is binary ${\max}$ and “multiplication” is integer addition, satisfies the requirements. So for the maximum segment sum problem, we get

$\displaystyle \mathit{maximum} \cdot \mathit{map}\,\mathit{sum} \cdot \mathit{inits} = \mathit{foldr}\,(\oplus)\,e \quad \mathbf{where}\; e = 0 \mathbin{;} u \oplus z = e \max (u + z)$

Moreover, ${\oplus}$ takes constant time, so this gives a linear-time algorithm for ${\mathit{mss}}$.

## Tail segments, datatype-generically

About a decade after the initial “theory of lists” work on the maximum segment sum problem, Richard Bird (with Oege de Moor and Paul Hoogendijk) came up with a datatype-generic version of the problem in the paper Generic functional programming with types and relations. It’s clear what “maximum” and “sum” mean generically, but not so clear what “segment” means for nonlinear datatypes; the point of their paper is basically to resolve that issue.

Recalling the definition of ${\mathit{segs}}$ in terms of ${\mathit{inits}}$ and ${\mathit{tails}}$, we see that it would suffice to develop datatype-generic notions of “initial segment” and “tail segment”. One fruitful perspective is given in Bird & co’s paper: a “tail segment” of a cons list is just a subterm of that list, and an “initial segment” is the list but with some tail (that is, some subterm) replaced with the empty structure.

So, representing a generic “tail” of a data structure is easy: it’s a data structure of the same type, and a subterm of the term denoting the original structure. A datatype-generic definition of ${\mathit{tails}}$ is a little trickier, though. For lists, you can see it as follows: every node of the original list is labelled with the subterm of the original list rooted at that node. I find this a helpful observation, because it explains why the ${\mathit{tails}}$ of a list is one element longer than the list itself: a list with ${n}$ elements has ${n+1}$ nodes (${n}$ conses and a nil), and each of those nodes gets labelled with one of the ${n+1}$ subterms of the list. Indeed, ${\mathit{tails}}$ ought morally to take a possibly empty list and return a non-empty list of possibly empty lists—there are two different datatypes involved. Similarly, if one wants the “tails” of a data structure of a type in which some nodes have no labels (such as leaf-labelled trees, or indeed such as the “nil” constructor of lists), one needs a variant of the datatype providing labels at those positions. Also, for a data structure in which some nodes have multiple labels, or in which there are different types of labels, one needs a variant for which every node has precisely one label.

Bird & co call this the labelled variant of the original datatype; if the original is a polymorphic datatype ${\mathsf{T}\,\alpha = \mu(\mathsf{F}\,\alpha)}$ for some binary shape functor ${\mathsf{F}}$, then the labelled variant is ${\mathsf{L}\,\alpha = \mu(\mathsf{G}\,\alpha)}$ where ${\mathsf{G}\,\alpha\,\beta = \alpha \times \mathsf{F}\,1\,\beta}$—whatever labels ${\mathsf{F}}$ may or may not have specified are ignored, and precisely one label per node is provided. Given this insight, it is straightforward to define a datatype-generic variant ${\mathit{subterms}}$ of the ${\mathit{tails}}$ function:

$\displaystyle \mathit{subterms}_{\mathsf{F}} = \mathit{fold}_{\mathsf{F}}(\mathit{in}_{\mathsf{G}} \cdot \mathit{fork}(\mathit{in}_{\mathsf{F}} \cdot \mathsf{F}\,\mathit{id}\,\mathit{root}, \mathsf{F}\,!\,\mathit{id})) :: \mathsf{T}\,\alpha \rightarrow \mathsf{L}(\mathsf{T}\,\alpha)$

where ${\mathit{root} = \mathit{fst} \cdot \mathit{in}_{\mathsf{G}}^{-1} = \mathit{fold}_{\mathsf{G}}\,\mathit{fst} :: \mathsf{L}\,\alpha \rightarrow \alpha}$ returns the root label of a labelled data structure, and ${!_{\alpha} :: \alpha \rightarrow 1}$ is the unique arrow to the unit type. (Informally, having computed the tree of subterms for each child of a node, we make the tree of subterms for this node by assembling all the child trees with the label for this node; the label should be the whole structure rooted at this node, which can be reconstructed from the roots of the child trees.) What’s more, there’s a datatype-generic scan lemma too:

$\displaystyle \begin{array}{lcl} \mathit{scan}_{\mathsf{F}} &::& (\mathsf{F}\,\alpha\,\beta \rightarrow \beta) \rightarrow \mathsf{T}\,\alpha \rightarrow \mathsf{L}\,\beta \\ \mathit{scan}_{\mathsf{F}}\,\phi &=& \mathsf{L}\,(\mathit{fold}_{\mathsf{F}}\,\phi) \cdot \mathit{subterms}_{\mathsf{F}} \\ &=& \mathit{fold}_{\mathsf{F}}(\mathit{in}_{\mathsf{G}} \cdot \mathit{fork}(\phi \cdot \mathsf{F}\,\mathit{id}\,\mathit{root}, \mathsf{F}\,!\,\mathit{id})) \end{array}$

(Again, the label for each node can be constructed from the root labels of each of the child trees.) In fact, ${\mathit{subterms}}$ and ${\mathit{scan}}$ are paramorphisms, and can also be nicely written coinductively as well as inductively. I’ll return to this in a future post.

## Initial segments, datatype-generically

What about a datatype-generic “initial segment”? As suggested above, that’s obtained from the original data structure by replacing some subterms with the empty structure. Here I think Bird & co sell themselves a little short, because they insist that the datatype ${\mathsf{T}}$ supports empty structures, which is to say, that ${\mathsf{F}}$ is of the form ${\mathsf{F}\,\alpha\,\beta = 1 + \mathsf{F}'\,\alpha\,\beta}$ for some ${\mathsf{F}'}$. This isn’t necessary: for an arbitrary ${\mathsf{F}}$, we can easily manufacture the appropriate datatype ${\mathsf{U}}$ of “data structures in which some subterms may be replaced by empty”, by defining ${\mathsf{H}\,\alpha\,\beta = 1 + \mathsf{F}\,\alpha\,\beta}$ and ${\mathsf{U}\,\alpha = \mu(\mathsf{H}\,\alpha)}$.

As with ${\mathit{subterms}}$, the datatype-generic version of ${\mathit{inits}}$ is a bit trickier—and this time, the special case of lists is misleading. You might think that because a list has just as many initial segments as it does tail segments, so the labelled variant ought to suffice just as well here too. But this doesn’t work for non-linear data structures such as trees—in general, there are many more “initial” segments than “tail” segments (because one can make independent choices about replacing subterms with the empty structure in each child), and they don’t align themselves conveniently with the nodes of the original structure.

The approach I prefer here is just to use an unstructured collection type to hold the “initial segments”; that is, a monad. This could be the monad of finite lists, or of finite sets, or of finite bags—we will defer until later the discussion about precisely which, and write simply ${\mathsf{M}}$. We require only that it provide a ${\mathit{MonadPlus}}$-like interface, in the sense of an operator ${\mathit{mplus} :: \mathsf{M}\,\alpha \times \mathsf{M}\,\alpha \rightarrow \mathsf{M}\,\alpha}$; however, for reasons that will become clear, we will expect that it does not provide a ${\mathit{mzero}}$ operator yielding empty collections.

Now we can think of the datatype-generic version of ${\mathit{inits}}$ as nondeterministically pruning a data structure by arbitrarily replacing some subterms with the empty structure; or equivalently, as generating the collection of all such prunings.

$\displaystyle \mathit{prune} = \mathit{fold}_{\mathsf{F}}(\mathsf{M}\,\mathit{in}_{\mathsf{H}} \cdot \mathit{opt}\,\mathit{Nothing} \cdot \mathsf{M}\,\mathit{Just} \cdot \delta_2) :: \mu(\mathsf{F}\,\alpha) \rightarrow \mathsf{M}(\mu(\mathsf{H}\,\alpha))$

Here, ${\mathit{opt}}$ supplies a new alternative for a nondeterministic computation:

$\displaystyle opt\,a\,\mathit{mx} = \mathit{return}\,a \mathbin{\underline{\smash{\mathit{mplus}}}} \mathit{mx}$

and ${\delta_2 :: (\mathsf{F}\,\alpha)\mathsf{M} \mathbin{\stackrel{.}{\to}} \mathsf{M}(\mathsf{F}\alpha)}$ distributes the shape functor ${\mathsf{F}}$ over the monad ${\mathsf{M}}$ (which can be defined for all ${\mathit{Traversable}}$ functors ${\mathsf{F}\,\alpha}$). Informally, once you have computed all possible ways of pruning each of the children of a node, a pruning of the node itself is formed either as ${\mathit{Just}}$ some node assembled from arbitrarily pruned children, or ${\mathit{Nothing}}$ for the empty structure.

## Horner’s Rule, datatype-generically

As we’ve seen, the essential property behind Horner’s Rule is one of distributivity. In the datatype-generic case, we will model this as follows. We are given an ${(\mathsf{F}\,\alpha)}$-algebra ${(\beta,f)}$, and a ${\mathsf{M}}$-algebra ${(\beta,k)}$; you might think of these as “datatype-generic product” and “collection sum”, respectively. Then there are two different methods of computing a ${\beta}$ result from an ${\mathsf{F}\,\alpha\,(\mathsf{M}\,\beta)}$ structure: we can either distribute the ${\mathsf{F}\,\alpha}$ structure over the collection(s) of ${\beta}$s, compute the “product” ${f}$ of each structure, and then compute the “sum” ${k}$ of the resulting products; or we can “sum” each collection, then compute the “product” of the resulting structure. Distributivity of “product” over “sum” is the property that these two different methods agree, as illustrated in the following diagram.

For example, with ${f :: \mathsf{F}\,{\mathbb Z}\,{\mathbb Z} \rightarrow {\mathbb Z}}$ adding all the integers in an ${\mathsf{F}}$-structure, and ${k :: \mathsf{M}\,{\mathbb Z} \rightarrow {\mathbb Z}}$ finding the maximum of a (non-empty) collection, the diagram commutes. (To match up with the rest of the story, we have presented distributivity in terms of a bifunctor ${\mathsf{F}}$, although the first parameter ${\alpha}$ plays no role. We could just have well have used a unary functor, dropping the ${\alpha}$, and changing the distributor to ${\delta :: \mathsf{F}\mathsf{M} \mathbin{\stackrel{.}{\to}} \mathsf{M}\mathsf{F}}$.)

Note that ${(\beta,k)}$ is required to be an algebra for the monad ${\mathsf{M}}$. This means that it is not only an algebra for ${\mathsf{M}}$ as a functor (namely, of type ${\mathsf{M}\,\beta \rightarrow \beta}$), but also it should respect the extra structure of the monad: ${k \cdot \mathit{return} = \mathit{id}}$ and ${k \cdot \mathit{join} = k \cdot \mathsf{M}\,k}$. For the special case of monads for associative collections (such as lists, bags, and sets), and in homage to the old Squiggol papers, we will stick to reductions${k}$s of the form ${\oplus/}$ for associative binary operator ${{\oplus} :: \beta \times \beta \rightarrow \beta}$; then we also have distribution over choice: ${\oplus / (x \mathbin{\underline{\smash{\mathit{mplus}}}} y) = (\oplus/x) \oplus (\oplus/y)}$. Note also that we prohibited empty collections in ${\mathsf{M}}$, so we do not need a unit for ${\oplus}$.

Recall that we modelled an “initial segment” of a structure of type ${\mu(\mathsf{F}\,\alpha)}$ as being of type ${\mu(\mathsf{H}\,\alpha)}$, where ${\mathsf{H}\,\alpha\,\beta = 1 + \mathsf{F}\,\alpha\,\beta}$. We need to generalize “product” to work on this extended structure, which is to say, we need to specify the value ${b}$ of the “product” of the empty structure too. Then we let ${g = \mathit{maybe}\,b\,f :: \mathsf{H}\,\alpha\,\beta \rightarrow \beta}$, so that ${\mathit{fold}_{\mathsf{H}}(g) :: \mu(\mathsf{H}\,\alpha) \rightarrow \beta}$.

The datatype-generic version of Horner’s Rule is then about computing the “sum” of the “products” of each of the “initial segments” of a data structure:

$\displaystyle {\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(g)) \cdot \mathit{prune}$

We will use fold fusion to show that this can be computed as a single fold, given the necessary distributivity property.

$\displaystyle \begin{array}{ll} & \mathord{\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(g)) \cdot \mathit{prune} \cdot \mathit{in}_{\mathsf{F}} \\ = & \qquad \{ \mbox{evaluation for~} \mathit{prune} \} \\ & \mathord{\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(g)) \cdot \mathsf{M}\,\mathit{in}_{\mathsf{H}} \cdot \mathit{opt}\,\mathit{Nothing} \cdot \mathsf{M}\,\mathit{Just} \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mbox{functors; evaluation for~} \mathit{fold}_{\mathsf{H}} \} \\ & \mathord{\oplus/} \cdot \mathsf{M}(g \cdot \mathsf{H}\,\mathit{id}\,(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathit{opt}\,\mathit{Nothing} \cdot \mathsf{M}\,\mathit{Just} \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mathsf{M}\,h \cdot \mathit{opt}\,a = \mathit{opt}\,(h\,a) \cdot \mathsf{M}\,h \} \\ & \mathord{\oplus/} \cdot \mathit{opt}\,(g\,\mathit{Nothing}) \cdot \mathsf{M}(g \cdot \mathsf{H}\,\mathit{id}\,(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{M}\,\mathit{Just} \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mbox{functors;~} \mathit{Just} :: \mathsf{F}\,\alpha \mathbin{\stackrel{.}{\to}} \mathsf{H}\,\alpha \} \\ & \mathord{\oplus/} \cdot \mathit{opt}\,(g\,\mathit{Nothing}) \cdot \mathsf{M}\,g \cdot \mathsf{M}(\mathit{Just} \cdot \mathsf{F}\,\mathit{id}\,(\mathit{fold}_{\mathsf{H}}(g))) \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mbox{functors;~} \delta_2 :: (\mathsf{F}\alpha)\mathsf{M} \mathbin{\stackrel{.}{\to}} \mathsf{M}(\mathsf{F}\alpha) \} \\ & \mathord{\oplus/} \cdot \mathit{opt}\,(g\,\mathit{Nothing}) \cdot \mathsf{M}(g \cdot \mathit{Just}) \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \end{array}$

(Sadly, I have to break this calculation in two to get it through WordPress’s somewhat fragile LaTeX processor… where were we? Ah, yes:)

$\displaystyle \begin{array}{ll} & \mathord{\oplus/} \cdot \mathit{opt}\,(g\,\mathit{Nothing}) \cdot \mathsf{M}(g \cdot \mathit{Just}) \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ g = \mathit{maybe}\,b\,f \} \\ & \mathord{\oplus/} \cdot \mathit{opt}\,b \cdot \mathsf{M}\,f \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ {\oplus/} \cdot \mathit{opt}\,b = (b\oplus) \cdot {\oplus/} \} \\ & (b\oplus) \cdot {\oplus/} \cdot \mathsf{M}\,f \cdot \delta_2 \cdot \mathsf{F}\,\mathit{id}\,(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mbox{distributivity:~} {\oplus/} \cdot \mathsf{M}\,f \cdot \delta_2 = f \cdot \mathsf{F}\,\mathit{id}\,(\oplus/) \} \\ & (b\oplus) \cdot f \cdot \mathsf{F}\,\mathit{id}\,(\oplus/) \cdot \mathsf{F}\,\mathit{id}\,(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(g))) \cdot \mathsf{F}\,\mathit{id}\,\mathit{prune} \\ = & \qquad \{ \mbox{functors} \} \\ & (b\oplus) \cdot f \cdot \mathsf{F}\,\mathit{id}\,({\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(g)) \cdot \mathit{prune}) \end{array}$

Therefore,

$\displaystyle {\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot \mathit{prune} = \mathit{fold}_{\mathsf{F}}((b\oplus) \cdot f)$

(Curiously, it doesn’t seem to matter what value is chosen for ${b}$.)

## Maximum segment sum, datatype-generically

We’re nearly there. We start with the traversable shape bifunctor ${\mathsf{F}}$, a collection monad ${\mathsf{M}}$, and a distributive law ${\delta_2 :: (\mathsf{F}\,\alpha)\mathsf{M} \mathbin{\stackrel{.}{\to}} \mathsf{M}(\mathsf{F}\alpha)}$. We are given an ${(\mathsf{F}\,\alpha)}$-algebra ${(\beta,f)}$, an additional element ${b :: \beta}$, and a ${\mathsf{M}}$-algebra ${(\beta,{\oplus/})}$, such that ${f}$ and ${\oplus}$ take constant time and ${f}$ distributes over ${\oplus/}$ in the sense above. Then

$\displaystyle {\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot \mathit{segs}$

can be computed in linear time, where

$\displaystyle \mathit{segs} = \mathit{join} \cdot \mathsf{M}\,\mathit{prune} \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathit{subterms} :: \mu(\mathsf{F}\,\alpha) \rightarrow \mathsf{M}(\mu(\mathsf{H}\,\alpha))$

and where

$\displaystyle \mathit{contents}_{\mathsf{L}} :: \mathsf{L} \mathbin{\stackrel{.}{\to}} \mathsf{M}$

computes the contents of an ${\mathsf{L}}$-structure (which, like ${\delta_2}$, can be defined using the traversability of ${\mathsf{F}}$). Here’s the calculation:

$\displaystyle \begin{array}{ll} & \mathord{\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot \mathit{segs} \\ = & \qquad \{ \mbox{definition of~} \mathit{segs} \} \\ & \mathord{\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot \mathit{join} \cdot \mathsf{M}\,\mathit{prune} \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathit{subterms} \\ = & \qquad \{ \mbox{naturality of~} \mathit{join} :: \mathsf{M}\mathsf{M} \mathbin{\stackrel{.}{\to}} \mathsf{M}\mbox{; functors} \} \\ & \mathord{\oplus/} \cdot \mathit{join} \cdot \mathsf{M}(\mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot\mathit{prune}) \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathit{subterms} \\ = & \qquad \{ \oplus/ \mbox{~is an~} \mathsf{M}\mbox{-algebra; functors} \} \\ & \mathord{\oplus/} \cdot \mathsf{M}({\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot\mathit{prune}) \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathit{subterms} \\ = & \qquad \{ \mbox{naturality of~} \mathit{contents} :: \mathsf{L} \mathbin{\stackrel{.}{\to}} \mathsf{M} \} \\ & \mathord{\oplus/} \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathsf{L}({\oplus/} \cdot \mathsf{M}(\mathit{fold}_{\mathsf{H}}(\mathit{maybe}\,b\,f)) \cdot\mathit{prune}) \cdot \mathit{subterms} \\ = & \qquad \{ \mbox{Horner's Rule} \} \\ & \mathord{\oplus/} \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathsf{L}(\mathit{fold}_{\mathsf{F}}((b\oplus)\cdot f)) \cdot \mathit{subterms} \\ = & \qquad \{ \mbox{Scan Lemma} \} \\ & \mathord{\oplus/} \cdot \mathit{contents}_{\mathsf{L}} \cdot \mathit{scan}_{\mathsf{F}}((b\oplus)\cdot f) \end{array}$

The scan can be computed in linear time, because its body takes constant time; moreover, the “sum” ${\oplus/}$ and ${\mathit{contents}}$ can also be computed in linear time (and what’s more, they can be fused into a single pass).

For example, with ${f :: \mathsf{F}\,{\mathbb Z}\,{\mathbb Z} \rightarrow {\mathbb Z}}$ adding all the integers in an ${\mathsf{F}}$-structure, ${b = 0 :: {\mathbb Z}}$, and ${{\oplus} :: {\mathbb Z}\times{\mathbb Z} \rightarrow {\mathbb Z}}$ returning the greater of two integers, we get a datatype-generic version of the linear-time maximum segment sum algorithm.

As the title of their paper suggests, Bird & co carried out their development using the relational approach set out in the Algebra of Programming book; for example, their version of ${\mathit{prune}}$ is a relation between data structures and their prunings, rather than being a function that takes a structure and returns the collection of all its prunings. There’s a well-known isomorphism between relations and set-valued functions, so their relational approach roughly looks equivalent to the monadic one I’ve taken.

I’ve known their paper well for over a decade (I made extensive use of the “labelled variant” construction in my own papers on generic downwards accumulations), but I’ve only just noticed that although they discuss the maximum segment sum problem, they don’t discuss problems based on other semirings, such as the obvious one of integers with addition and multiplication—which is, after all, the origin of Horner’s Rule. Why not? It turns out that the relational approach doesn’t work in that case!

There’s a hidden condition in the calculation, which relates back to our earlier comment about which collection monad—finite sets, finite bags, lists, etc—to use. When ${\mathsf{M}}$ is the set monad, distribution over choice (${\oplus / (x \mathbin{\underline{\smash{\mathit{mplus}}}} y) = (\oplus/x) \oplus (\oplus/y)}$)—and consequently the condition ${{\oplus/} \cdot \mathit{opt}\,b = (b\oplus) \cdot {\oplus/}}$ that we used in proving Horner’s Rule—require ${\oplus}$ to be idempotent, because ${\mathit{mplus}}$ itself is idempotent; but addition is not idempotent. For the same reason, the distributivity property does not hold for addition with the set monad. But everything does work out for the bag monad, for which ${\mathit{mplus}}$ is not idempotent. The bag monad models a flavour of nondeterminism in which multiplicity of results matters—as it does for the sum-of-products instance of the problem, when two copies of the same segment should be treated differently from just one copy. Similarly, if the order of results matters—if, for example, we were looking for the “first” solution—then we would have to use the list monad rather than bags or sets. Seen from a monadic perspective, the relational approach is programming with just one monad, namely the set monad; if that monad doesn’t capture your effects faithfully, you’re stuck.

(On the other hand, there are aspects of the problem that work much better relationally. We have carefully used ${\max}$ only for a linear order, namely the usual ordering of the integers. A partial order is more awkward monadically, because there need not be a unique maximal value. For example, it is not so easy to compute a segment with maximal sum, unless we refine the sum ordering on segments to make it once more a linear order; relationally, this works out perfectly straightforwardly. We can try the same trick of turning the relation “maximal under a partial order” into the collection-valued function “all maxima under a partial order”, but I fear that the equivalent trick on the ordering itself—turning the relation “${<}$” into the collection-valued function “all values less than this one”—runs into problems from taking us outside the world of finite nondeterminism.)

Jeremy is Professor of Computing in Oxford University Department of Computer Science, and a fan of functional programming and patterns of computation.
This entry was posted in Uncategorized. Bookmark the permalink.

### 5 Responses to Horner’s Rule

1. Graham says:

Great post. Can’t wait for the book.

2. Earlier this year, I implemented a proof of the program transformation for “Maximum Segment Sum” in Isabelle/HOL. If anybody is interested in getting started with Isabelle for stuff like this, you can look into it here:
http://soren.gawis.dk/acpl/sorenh07-ACPL-final.zip (contains report and source code)
http://soren.gawis.dk/acpl/presentation.pdf

I’m confident your book will be very enlightening, and look forward to it :-). Especially the idea of using a monadic approach instead of restricting to the relational approach taken by Bird and de Moor. Maybe this will also be more amenable to implementation in a mechanized proof environment – I haven’t looked much into that yet.

3. Hm. I fear that the “strictly non-empty collections” idea doesn’t sit nicely with the use of distributivity of the shape over the monad: for shapes that allow empty structures (such as the “nil” of lists), empty collections turn up. So I need to allow empty collections (MonadZero as well as MonadPlus, if you like), and to assume an additional element e :: Beta as the result of k on the empty collection; e should be the unit of oplus, and in some suitable sense the zero of f (it’ll be the zero of otimes, in the next post.) Oh well.

4. rogushy says:

Delightful exploration of the scope of applicability of Horner’s Rule. What’s your second most favorite calculation?

• Hm… I’ll have to think about that. And then maybe write another post about it!


text:
Found 862 Documents (Results 1–100)

100
MathJax

Full Text:

A fast method for evaluating Green’s function in irregular domains with application to charge interaction in a nanopore. (English)Zbl 1475.78012

MSC:  78M99 78A30 65N80
Full Text:

Numerical method of profile reconstruction for a periodic transmission problem from single-sided data. (English)Zbl 07416251

MSC:  35R30 78A46 78M50
Full Text:

Full Text:

A direct imaging method for inverse electromagnetic scattering problem in rectangular waveguide. (English)Zbl 07415843

MSC:  65N21 78A46 78A50 35J05 35J08 35Q80
Full Text:

Full Text:

A new route to negative refractive index from topological metals. (English)Zbl 1477.82011

MSC:  82C35 78A45
Full Text:

Full Text:

Full Text:

High frequency electrical oscillations in cavities. (English)Zbl 07394616

MSC:  35Q60 78A25 78A50
Full Text:

Full Text:

Exposure-programmable CMOS pixel with selective charge storage and code memory for computational imaging. (English)Zbl 1469.94012

MSC:  94A08 78A45
Full Text:

Full Text:

Full Text:

Full Text:

Molecular dynamics simulation of Al explosive boiling and transcritical regimes in nanosecond laser ablation. (English)Zbl 07388359

Math. Montisnigri 41, 55-72 (2018); erratum ibid. 43, 136-138 (2018).
Full Text:

Full Text:

MSC:  78A30
Full Text:

On the inverse problem for Channell collisionless plasma equilibria. (English)Zbl 07383766

MSC:  76X05 78A25
Full Text:

Error control based on the novel proof of convergence of the MSMAOR methods for the LCP. (English)Zbl 1470.90141

MSC:  90C33 78A48
Full Text:

Full Text:

Automatic under-frequency load shedding mal-operation in power systems with high wind power penetration. (English)Zbl 07316190

MSC:  93C80 93C95 78A55
Full Text:

Wind power plant integration in voltage source converter HVdc grids with voltage droop control. (English)Zbl 07316189

MSC:  93C95 78A55
Full Text:

Full Text:

Breathers and rogue waves derived from an extended multi-dimensional $$N$$-coupled higher-order nonlinear Schrödinger equation in optical communication systems. (English)Zbl 1452.78022

MSC:  78A60 35Q55 35C08
Full Text:

Full Text:

Optical solitons and stability analysis in ring-cavity fiber system with carbon nanotube as saturable absorber. (English)Zbl 1451.78034

MSC:  78A60 35C08
Full Text:

Longitudinal modes competition in a micro ring laser subject to both a self and a cross optical feedback. (English)Zbl 1470.78007

MSC:  78A55 82D37
Full Text:

Full Text:

Nonlinear dynamic analysis of asymmetric tristable energy harvesters for enhanced energy harvesting. (English)Zbl 1473.70046

MSC:  70K20 78A45
Full Text:

Full Text:

Estimating the structure factors in X-ray diffraction. (English)Zbl 1445.78003

MSC:  78A45 82D25
Full Text:

Small-angle X-ray scattering tensor tomography: model of the three-dimensional reciprocal-space map, reconstruction algorithm and angular sampling requirements. (English)Zbl 1446.92209

MSC:  92C55 78A45
Full Text:

Uniform global solutions of the 3D compressible MHD system in a bounded domain. (English)Zbl 1442.76140

MSC:  76W05 35Q35 78A25
Full Text:

Full Text:

MSC:  78A45
Full Text:

Full Text:

Symmetry, invariance and the structure of matter. (English)Zbl 1453.82082

Sirakov, Boyan (ed.) et al., Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1–9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3967-3993 (2018).
Full Text:

FFT based spectral Ewald methods as an alternative to fast multipole methods. (English)Zbl 1454.65176

Sirakov, Boyan (ed.) et al., Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1–9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3691-3709 (2018).
Full Text:

Joint estimation of DOA and polarization based on phase difference analysis of electromagnetic vector sensor array. (English)Zbl 1448.94090

MSC:  94A12 78A25
Full Text:

Full Text:

Full Text:

Full Text:

Preconditioners for time-harmonic optimal control eddy-current problems. (English)Zbl 1476.65215

Lirkov, Ivan (ed.) et al., Large-scale scientific computing. 11th international conference, LSSC 2017, Sozopol, Bulgaria, June 5–9, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10665, 47-54 (2018).
Full Text:

Multivalued logic at the nanoscale. (English)Zbl 1436.68121

Stepney, Susan (ed.) et al., Computational matter. Cham: Springer. Nat. Comput. Ser., 295-318 (2018).
Full Text:

Full Text:

The analytical approach for identification of magnetically induced vibrations of working in faulty state BLDC motor. (English)Zbl 1444.78008

Awrejcewicz, Jan (ed.), Dynamical systems in theoretical perspective. Łódź, Poland, December 11–14, 2017. Based on the 14th international conference on dynamical systems: theory and applications (DSTA). Cham: Springer. Springer Proc. Math. Stat. 248, 349-362 (2018).
Full Text:

Study of the high-amplitude solutions in the system of magnetic sliding oscillator with many degrees of freedom. (English)Zbl 1444.78007

Awrejcewicz, Jan (ed.), Dynamical systems in theoretical perspective. Łódź, Poland, December 11–14, 2017. Based on the 14th international conference on dynamical systems: theory and applications (DSTA). Cham: Springer. Springer Proc. Math. Stat. 248, 295-310 (2018).
Full Text:

Integral equation based optimized Schwarz method for electromagnetics. (English)Zbl 1443.65420

Bjørstad, Petter E. (ed.) et al., Domain decomposition methods in science and engineering XXIV. Proceedings of the 24th international conference, Svalbard, Norway, February 6–10, 2017. Cham: Springer. Lect. Notes Comput. Sci. Eng. 125, 187-194 (2018).
Full Text:

A two-level domain-decomposition preconditioner for the time-harmonic Maxwell’s equations. (English)Zbl 1443.65417

Bjørstad, Petter E. (ed.) et al., Domain decomposition methods in science and engineering XXIV. Proceedings of the 24th international conference, Svalbard, Norway, February 6–10, 2017. Cham: Springer. Lect. Notes Comput. Sci. Eng. 125, 149-157 (2018).
Full Text:

The scattering of electromagnetic waves by two opposite staggered perfectly electrically conducting half-planes. (English)Zbl 1469.78005

MSC:  78A45 35J05 35P25
Full Text:

MSC:  78A45
Full Text:

High-order functional derivatives of the scattered field according to the permittivity-contrast function. (English)Zbl 1469.78004

MSC:  78A45 35Q60
Full Text:

Properties of the Poynting vector for invariant beams: negative propagation in Weber beams. (English)Zbl 1448.78029

MSC:  78A40 35J05 35Q61
Full Text:

Full Text:

MSC:  78A45
Full Text:

Full Text:

On the existence of non-polarized azimuthal-symmetric electromagnetic waves in circular dielectric waveguide filled with nonlinear isotropic homogeneous medium. (English)Zbl 07213352

MSC:  47J10 78A60
Full Text:

Full Text:

Direct and reverse problems of reconstruction of evolution operators in the analysis of the dynamics of multidimensional processes. (Russian. English summary)Zbl 1434.78014

MSC:  78A45 78A46 94A12
Full Text:

Identification of inhomogeneous characteristics of prestressed pyromaterials. (Russian. English summary)Zbl 1434.74045

MSC:  74F05 78A30 74F15
Full Text:

Full Text:

Full Text:

Full Text:

Full Text:

Full Text:

Full Text:

An edge-based smoothed finite element method for nonlinear magnetostatic and eddy current analysis. (English)Zbl 1460.78025

MSC:  78M10 78A25 78A30
Full Text:

Geometrical optics for scalar, electromagnetic and gravitational waves on curved spacetime. (English)Zbl 1430.78003

MSC:  78A05 83C35
Full Text:

Symmetry, validation, and scattering matrices for time-domain scattering in waveguides. (English)Zbl 1480.78005

MSC:  78A25 78A45
Full Text:

MSC:  78A60
Full Text:

MSC:  78A45
Full Text:

Full Text:

Asymptotically (A)dS dilaton black holes with nonlinear electrodynamics. (English)Zbl 1430.83045

MSC:  83C57 83C50 78A25
Full Text:

MSC:  78A60
Full Text:

A coupled multiphysics FEM model to investigate electromagnetic, thermal and mechanical effects in complex assemblies: the design of the high-luminosity large hadron collider beam screen. (English)Zbl 1480.78003

MSC:  78A25 81V10
Full Text:

On the existence of infinitely many nonperturbative solutions in a transmission eigenvalue problem for nonlinear Helmholtz equation with polynomial nonlinearity. (English)Zbl 1480.34113

MSC:  34L30 47J10 78A25
Full Text:

Full Text:

Full Text:

On a non-scalar damping model in micromagnetism. (English)Zbl 1442.37094

MSC:  37N15 78A30
Full Text:

The theory of closed 1-forms, levels of quasiperiodic functions and transport phenomena in electron systems. (English. Russian original)Zbl 1431.82037

Proc. Steklov Inst. Math. 302, 279-297 (2018); translation from Tr. Mat. Inst. Steklova 302, 296-315 (2018).
Full Text:

Full Text:

A finite element method for Maxwell polynomial chaos Debye model. (English)Zbl 1428.78033

MSC:  78M10 65M60 78A25
Full Text:

Full Text:

Nonlinear electrodynamics, regular black holes and wormholes. (English)Zbl 1427.83009

MSC:  83C20 78A25 83C57
Full Text:

Fractional models of lithium-ion batteries with application to state of charge and ageing estimation. (English)Zbl 1427.78017

Madani, Kurosh (ed.) et al., Informatics in control, automation and robotics. 13th international conference, ICINCO 2016, Lisbon, Portugal, July 29–31, 2016. Selected, extended and revised papers. Cham: Springer. Lect. Notes Electr. Eng. 430, 55-72 (2018).
Full Text:

Origin of the magnetic momentum for regular electrically charged objects described by nonlinear electrodynamics coupled to gravity. (English)Zbl 1425.83010

MSC:  83C20 78A25 83C22
Full Text:

Solving inverse illumination problems with Liouville’s equation. (English)Zbl 1425.78004

Radu, Florin Adrian (ed.) et al., Numerical mathematics and advanced applications. ENUMATH 2017. Selected papers based on the presentations at the European conference, Bergen, Norway, September 25–29, 2017. Cham: Springer. Lect. Notes Comput. Sci. Eng. 126, 311-319 (2018).
Full Text:

A least-squares method for a Monge-Ampère equation with non-quadratic cost function applied to optical design. (English)Zbl 07136716

Radu, Florin Adrian (ed.) et al., Numerical mathematics and advanced applications. ENUMATH 2017. Selected papers based on the presentations at the European conference, Bergen, Norway, September 25–29, 2017. Cham: Springer. Lect. Notes Comput. Sci. Eng. 126, 301-309 (2018).
Full Text:

Topologically non-trivial magnetic skyrmions in confined geometries. (English)Zbl 1425.82038

Gupta, Sanju (ed.) et al., The role of topology in materials. Springer Series in Solid-State Sciences 189. Cham: Springer. 113-140 (2018).
Full Text:

Taking control of initiated propagating wave in a neuronal network using magnetic radiation. (English)Zbl 1427.92012

MSC:  92B20 78A40 92C15
Full Text:

Induced-charge electro-osmosis in dielectric annuli. (English)Zbl 1427.78006

MSC:  78A35 76W05
Full Text:

Full Text:

Full Text:

Full Text:

Subtle structure of streamers under conditions resembling those of transient luminous events. (English)Zbl 1423.76509

MSC:  76X05 78A35
Full Text:

Stochastic theory of polarized light in nonlinear birefringent media: an application to optical rotation. (English)Zbl 1423.78016

MSC:  78A48 35Q55
Full Text:

MSC:  78A30
Full Text:

Spin-orbital momentum decomposition and helicity exchange in a set of non-null knotted electromagnetic fields. (English)Zbl 1423.78003

MSC:  78A25 35Q61
Full Text:

all top 5

all top 5

all top 3

all top 3

format: plain


text:
• •

### 中国货币政策的非对称性偏好调控模式及其演变研究

• 出版日期:2019-07-25 发布日期:2019-07-29

### Research on the Evolution of Asymmetric Preferences Regulation for China’s Monetary Policy

Chen Chuanglian et al.

• Online:2019-07-25 Published:2019-07-29

Abstract: The asymmetric policy of commodity price stability and economic growth is a general strategy for the central bank to regulate the macroeconomy. Based on the asymmetric welfare loss function, this paper firstly backsteps to estimate the model of timevarying asymmetric preferences regulation for the central bank. The estimated results show that the central bank presents a policy orientation of targeting inflation and inflation fluctuation. Furthermore, the central bank also presents an asymmetric preference of inflation aversion and economic contraction avoidance, which means the central bank has a strong motivation to maintain inflation below the targeted inflation and economic growth rate higher than the goals of economic growth. In particular, the asymmetric preference of inflation aversion and economic contraction avoidance shows a strong negative correlation. In addition, the asymmetric preference of inflation aversion becomes stronger, while the asymmetric preference of economic contraction avoidance declines in recent years, indicating that China’s monetary policy has a strong preference for controlling inflation, however the asymmetric orientation policy in maintaining economic growth rate higher than the targeted rate has weakened.


text:
### tiiooo's blog

By tiiooo, history, 2 months ago,

Given an array and a 2d matrix. You have to find if the array is present in the matrix or not.To do so, you can start from any point in the matrix and go in 4 directions that is if you are at (i,j) you can go to (i+1,j), (i-1,j), (i,j+1), (i,j-1).

Return the starting and ending pairs of indices if the array exists otherwise return false.

Suppose the given array is [ 1, 10, 22, 47, 33, 10] and the matrix is as given below..then as we can see the array exists in the matrix and the starting and ending points respectively are: (2,2) and (3,4) [ 0-based indexing]

What will be the efficient solution ,i mean what will be the time complexity ?

• +1

 » 2 months ago, # |   0 I think this may be solvable by DP.
•  » » 2 months ago, # ^ |   -11 nah its graph theory
•  » » 2 months ago, # ^ |   +5 Yeah, that is correct.Let $A$ be the matrix and $B$ be the array. Now, the DP states can be defined as follows: $\mathrm{dp}[i][j][k]$ is true if the array $B[0] \ldots B[k]$ exists in the matrix and ends at the cell $(i, j)$. The DP table can be calculated like this: $\mathrm{dp}[i][j][k]$ should be true only if $A[i][j] = B[k]$ and $\mathrm{dp}[\cdot][\cdot][k - 1]$ is true for some neighbor of $(i, j)$.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +13 what about dp[.][.][k-1] was true for some neighbour but current (i,j) was already used in making it true for that neighbour. e.g. array is [1, 2, 3, 2, 4] and matrix is [[5 4],[1 2],[6 3]]
•  » » » » 3 weeks ago, # ^ |   0 what?
•  » » » » » 3 weeks ago, # ^ |   0 (take matrix from above example if image doesn't load) for this matrix A and array B [1, 2, 3, 2, 4]. dp[2][1][2] would be true. Also A[1][1]==B[3] and (2,1) is a neighbour of (1,1), sp dp[1][1][3] will also become true which is not right. Am I missing something?
•  » » » » » » 3 weeks ago, # ^ |   0 Why is dp[1][1][3] being true not correct?
•  » » » » » » » 3 weeks ago, # ^ |   0 dp[1][1][3] being true is correct if same element in the matrix can be taken twice to form the array
•  » » » » » » » » 3 weeks ago, # ^ |   +3 Yeah, I see no constraint in the statement that forbids us from taking the same element twice so I'm going to assume that it is allowed.
 » 2 months ago, # |   0 Can you give detailed constraints of the problem? If the array length is small enough, then I can just use a simple brute-force solution.
 » 2 months ago, # |   0 dfs from every (i,j) looks like the only solution
•  » » 2 months ago, # ^ |   0 One issue there is if the array is filled with 1s except for maybe the bottom right corner is a 2, and the array is also filled with 1s except the last element is 2 then you have an exponential number of paths with only 1s to get through before you confirm that one of them ends in a 2. Obviously that particular case can be hardcoded or something but in general dfs doesn't work when a graph can have an exponential number of paths, which is true in this grid.
•  » » » 2 months ago, # ^ |   0 Agreed
 » 2 months ago, # |   0 My intuition is a BFS-ish approach where you start with a list of locations in the matrix equal to the first element in the array and for each element of the array you take the list of locations equal to the previous element and if there's an adjacent location equal to the current element add it to a new list. Then the answer would just be whether the list is non-empty. Complexity would be (elements in matrix) * (elements in array) but the approach fails if you're not allowed to go back to a square you've gone to previously.
 » 2 months ago, # |   0 I guess you can do dfs storing current cell, and position in array (dfs(x, y, pos)). Then you can save whether you was in that cell with current position in array, so complexity will be matrix size * array size, because so will visit each cell at most N (size of array) times.
 » 2 months ago, # |   0 This is acmicpc india online round 2018 grid question, if we can revisit then it's as mentioned by its-fft else is brute force, also on Leetcode there is similar question with string and trie.


text:
# Projectile Motion Problem with thrown ball off roof

1. Jun 6, 2009

### coco87

1. The problem statement, all variables and given/known data
A ball is thrown leftward from the left edge of the roof, at height $$h$$ above the ground. The ball hits

the ground $$1.50s$$ later, at distance $$d=25.0m$$ from the building and at angle $$\theta =60^ {\circ}$$ with the horizontal. (a) Find h. What are the (b) Magnitude and (c) angle relative to the horizontal

of the velocity at which the ball is thrown? (d) Is the angle above or below the horizontal?

http://lcphr3ak.is-a-geek.com/fig49.png [Broken]

$$d=25.0m$$
$$\theta=60^{\circ}$$

The answers in the back are:
a)$$32.3m$$
b)$$21.9\frac{m}{s}$$
c)$$40.4^{\circ}$$
d)below

2. Relevant equations
$$x - x_{\circ} = v_{\circ} t - \frac{1}{2} a t^2$$
$$v_{\circ x} = v_{\circ} \cos{\theta _{\circ}}$$
$$v_{\circ y} = v_{\circ} \sin{\theta _{\circ}}$$

3. The attempt at a solution

I'm missing an observation here, because I don't see enough information to solve this. This problem is suppose to

be solved with projectile motion. So first I attempt to find $$v_{fx}$$ (which is the $$x$$ component

of the vector at $$\theta$$): $$x - x_{\circ} = v_{fx} t - \frac{1}{2} a t^2$$ which is $$-25 = v_{fx} (1.50)$$. This gives me $$v_{fx} = -16.667$$. Using this, I take $$v_{fx} = v_f \cos{\theta}$$, which is: $$-16.667 = v_f \cos{60}$$, so $$v_f = -33.32$$. Using this, I find $$v_{fy}$$ by taking $$v_{fy} = v_f \sin{\theta}$$ and doing $$v_{fy} = (-33.32)\sin{60}$$ so $$v_{fy} = -28.856$$. So, to find $$h$$, we solve for $$y$$. $$y = v_{fy} t - \frac{1}{2} a t^2$$

becomes $$y = (-28.856)(1.50) - \frac{1}{2} (9.8) (1.50)^2$$ which says $$y = -54.309$$. Now, the

absolute value of $$y$$ should be the height, but this is waaaaay off from the answer. I'm practically out of

ideas.

Could anyone explain what I'm doing wrong? If I didn't provide enough info, just let me know and I'll try to

provide more.

Thanks!

Last edited by a moderator: May 4, 2017
2. Jun 6, 2009

### tiny-tim

Hi coco87!

(have a theta: θ )
Nooo … θ in your formula is the angle at the roof. not the θ (= 60º) in the diagram!

3. Jun 6, 2009

### disillusion

Take care with the sign of the acceleration.
It is often helpful to write down on your diagram which direction you are taking as positive.

4. Jun 6, 2009

### coco87

So, I'm either using the wrong formula, or I need to find the initial velocity (or angle)? I don't know of any other formulas (other than $$v = v_{\circ}+at$$), and I have no idea how I would even obtain the angle up there. Could you possibly give me a hint? (or another one )

Thanks for the responce!

5. Jun 6, 2009

### disillusion

you can use that formula to find the initial vertical velocity. Then you can work out an angle!

6. Jun 6, 2009

### coco87

What you had said triggered an idea, and after playing around with the equations, I found out that I had misunderstood the Constant Accelloration equations all along.. well, I do now

Thank you guys for your help!


text:
# Home

Score : $300$ points

### Problem Statement

You are given an integer sequence of length $n$, $a_1, ..., a_n$. Let us consider performing the following $n$ operations on an empty sequence $b$.

The $i$-th operation is as follows:

1. Append $a_i$ to the end of $b$.
2. Reverse the order of the elements in $b$.

Find the sequence $b$ obtained after these $n$ operations.

### Constraints

• $1 \leq n \leq 2\times 10^5$
• $0 \leq a_i \leq 10^9$
• $n$ and $a_i$ are integers.

### Input

Input is given from Standard Input in the following format:

$n$
$a_1$ $a_2$ $...$ $a_n$

### Output

Print $n$ integers in a line with spaces in between. The $i$-th integer should be $b_i$.

### Sample Input 1

4
1 2 3 4

### Sample Output 1

4 2 1 3

• After step 1 of the first operation, $b$ becomes: $1$.
• After step 2 of the first operation, $b$ becomes: $1$.
• After step 1 of the second operation, $b$ becomes: $1, 2$.
• After step 2 of the second operation, $b$ becomes: $2, 1$.
• After step 1 of the third operation, $b$ becomes: $2, 1, 3$.
• After step 2 of the third operation, $b$ becomes: $3, 1, 2$.
• After step 1 of the fourth operation, $b$ becomes: $3, 1, 2, 4$.
• After step 2 of the fourth operation, $b$ becomes: $4, 2, 1, 3$.

Thus, the answer is 4 2 1 3.

### Sample Input 2

3
1 2 3

### Sample Output 2

3 1 2

As shown above in Sample Output 1, $b$ becomes $3, 1, 2$ after step 2 of the third operation. Thus, the answer is 3 1 2.

### Sample Input 3

1
1000000000

### Sample Output 3

1000000000

### Sample Input 4

6
0 6 7 6 7 0

### Sample Output 4

0 6 6 0 7 7


text:
## Trigonometry (11th Edition) Clone

The positive square root should be selected. $$\tan225^\circ=\sqrt{\frac{1-\cos450^\circ}{1+\cos450^\circ}}$$
$$\tan225^\circ=\pm\sqrt{\frac{1-\cos450^\circ}{1+\cos450^\circ}}$$ Whether the positive or negative square root should be selected depends the sign of $\tan225^\circ$. $225^\circ$ lies in quadrant III. In quadrant III, both $\cos\theta\lt0$ and $\sin\theta\lt0$. Therefore, $\tan\theta=\frac{\sin\theta}{\cos\theta}\gt0$. So, $\tan225^\circ\gt0$. Thus, the positive square root should be selected. In other words, $$\tan225^\circ=\sqrt{\frac{1-\cos450^\circ}{1+\cos450^\circ}}$$


text:
0
Research Papers

# Wall Shear Stresses Remain Elevated in Mature Arteriovenous Fistulas: A Case Study

[+] Author and Article Information
G. T. Carroll

Centre for Applied Biomedical Engineering Research (CABER), Department of Mechanical and Aeronautical Engineering, and the Materials and Surface Science Institute, University of Limerick, Limerick, Irelandgrainne.carroll@ul.ie

T. M. McGloughlin

Centre for Applied Biomedical Engineering Research (CABER), Department of Mechanical and Aeronautical Engineering, and the Materials and Surface Science Institute, University of Limerick, Limerick, Irelandtim.mcgloughlin@ul.ie

P. E. Burke

Department of Vascular Surgery, HSE Midwestern Regional Hospital, Limerick, Ireland; St John’s Hospital, Limerick, Ireland

M. Egan, F. Wallis

Department of Radiology, HSE Midwestern Regional Hospital, Limerick, Ireland

M. T. Walsh

Centre for Applied Biomedical Engineering Research (CABER), Department of Mechanical and Aeronautical Engineering, and the Materials and Surface Science Institute, University of Limerick, Limerick, Irelandmichael.walsh@ul.ie

J Biomech Eng 133(2), 021003 (Jan 24, 2011) (9 pages) doi:10.1115/1.4003310 History: Received October 01, 2009; Revised December 20, 2010; Posted January 03, 2011; Published January 24, 2011; Online January 24, 2011

## Abstract

Maintaining vascular access (VA) patency continues to be the greatest challenge for dialysis patients. VA dysfunction, primarily due to venous neointimal hyperplasia development and stenotic lesion formation, is mainly attributed to complex hemodynamics within the arteriovenous fistula (AVF). The effect of VA creation and the subsequent geometrical remodeling on the hemodynamics and shear forces within a mature patient-specific AVF is investigated. A 3D reconstructed geometry of a healthy vein and a fully mature patient-specific AVF was developed from a series of 2D magnetic resonance image scans. A previously validated thresholding technique for region segmentation and lumen cross section contour creation was conducted in MIMICS 10.01 , allowing for the creation of a 3D reconstructed geometry. The healthy vein and AVF computational models were built, subdivided, and meshed in GAMBIT 2.3 . The computational fluid dynamic (CFD) code FLUENT 6.3.2 (Fluent Inc., Lebanon, NH) was employed as the finite volume solver to determine the hemodynamics and shear forces within the healthy vein and patient-specific AVF. Geometrical alterations were evaluated and a CFD analysis was conducted. Substantial geometrical remodeling was observed, following VA creation with an increase in cross-sectional area, out of plane curvature (maximum angle of curvature in $AVF=30 deg$), and angle of blood flow entry. The mean flow velocity entering the vein of the AVF is dramatically increased. These factors result in complex three-dimensional hemodynamics within VA junction (VAJ) and efferent vein of the AVF. Complex flow patterns were observed and the maximum and mean wall shear stress (WSS) magnitudes are significantly elevated. Flow reversal was found within the VAJ and efferent vein. Extensive geometrical remodeling during AVF maturation does not restore physiological hemodynamics to the VAJ and venous conduit of the AVF, and high WSS and WSS gradients, and flow reversal persist. It is theorized that the vessel remodelling and the continued non-physiological hemodynamics within the AVF compound to result in stenotic lesion development.

<>

## Figures

Figure 1

Diagrams of (a) the healthy vein geometry and (b) the patient-specific radiocephalic AV fistula geometry. A 3D image of both models is presented. Both geometries are also exhibited in the x-y and x-z planes and locations of the velocity inlet and outflow are highlighted.

Figure 2

2D images acquired from MRI scans. The series of 2D create 3D images: (a) healthy vein 2D slice and 3D image and (b) radiocephalic AV fistula 2D slice and 3D image.

Figure 3

The resting velocity inlet boundary condition used in the numerical models of the healthy vein and the radiocephalic AVF. The blood flow times of interest are also displayed, namely, the maximum acceleration velocity, the maximum velocity, the maximum deceleration velocity, and the minimum velocity.

Figure 4

(a) Healthy vein geometry. Region A: the first area of out of plane curvature. Region B: the straight section of the vein model. Region C: the second location of out of plane curvature. (b) Cross-sectional (C-S) slices illustrating velocity contours and in-plane secondary flow vectors of the healthy vein geometry within the aforementioned three regions of interest.

Figure 5

(a) Schematic of AV fistula geometry detailing specific locations of interest and of each cross-sectional slice, (b) axial velocity contours in the AV fistula, (c) velocity path-lines in the AV fistula, and (d) velocity contours and vectors at each cross-sectional slice of AVF geometry

Figure 6

(a) Graphed circumferential-WSS profiles at each of the regions of interest detailed in Fig. 4. (b) Overview of all WSS magnitudes at each circumferential point along the length of the vein geometry.

Figure 7

[(a) and (b)] The axial and circumferential direction venous floor center-line WSSs: (c) NWSS and (d) WSSG results for the AV fistula model at four time-points during the pulse cycle: t=0.8 s refers to the point of maximum acceleration and t=0.27 s is the peak velocity of the pulse. t=0.97 s and t=0.99 s refer to the maximum deceleration and minimum velocity phases of the AVF pulse cycle, respectively. (e) The fifth graph exhibits the degree to which the WSS within the VA junction of the AVF deviates from the healthy vein WSS environment over the duration of the pulse.

Figure 8

The temporal-spatial WSS distribution as a function of surface area within the patient-specific AVF model

## Discussions

Some tools below are only available to our subscribers or users with an online account.

### Related Content

Customize your page view by dragging and repositioning the boxes below.

Related Journal Articles
Related Proceedings Articles
Related eBook Content
Topic Collections


text:
# Life, 3

.

We exist in time because time is change.

Growing is part of the definition of life. Growing is a kind of change.

.

Also, without time/change, there would be no thinking and no thoughts.

— Me@2017-12-26 11:42 am

— Me@2018-05-23 10:05:03 PM

.

time ~ change

.

Time is logically necessary if change is necessary.

— Me@2018-02-04 09:07:48 PM

.

.

# The language of Change 1.2

Energy conservation, 6.2 | Energy 5.2

.

time ~ change

energy ~ the ability of _keeping_ changing

.

constant velocity ~ the amount of an object’s change of position, measured with respect to its observer’s unit of change, is constant

$s = \Delta x$

$v = \frac{s}{\Delta t} = \frac{\Delta x}{\Delta t}$

.

kinetic energy ~ the amount of the ability of keeping changing an object’s position

$\frac{1}{2} m v^2$ ~ the square of (the amount of change of position, relative to the observer’s unit of change)

.

.

Energy difference is _not_ exactly a measurement of the amount of change, time interval is.

— Me@2018-02-20 09:39:30 AM

.

.

# The language of Change

Energy conservation, 6 | Energy 5

.

time ~ change

energy ~ the ability of causing change

Assuming

1. a system of one single particle

2. has only kinetic energy

3. and that kinetic energy is conserved.

conservation of energy ~ an object’s potential amount of change of position, measured with respect to its observer’s unit of change, is constant

$s = \Delta x$

$v = \frac{s}{\Delta t} = \frac{\Delta x}{\Delta t}$

— Me@2018-02-15 02:21:20 PM

.

Note:

The above argument has a bug:

If the mass m is constant, the kinetic energy $E_K$ should be proportional to velocity squared $v^2$, instead of velocity $v$.

$E_K = \frac{1}{2} m v^2$

.

However, the above argument is still technically correct:

When $E_K$ is constant, $v^2$ is constant. In turn, the magnitude of $v$ also remains unchanged.

— Me@2018-02-19 09:37:24 PM

.

.

# Definition of Time, Prime

Energy 4

.

time ~ change

energy ~ the ability of causing change

— Me@2018-02-15 10:20:25 AM

.

.

# 生命

「生命」這個詞語很有意思。

「生」，就是指一些可改變的東西，例如，「生活」、「生氣」和「生機」等。「命」，就是指一些不可改變的東西，例如，「命運」、「命定」和「命令」等。

— Me@2015.03.20

# Energy 3

energy ~ ability of causing change

energy used ~ amount of change

— Me@2014-08-19 02:44:22 AM

# Change

By the definition of “time”, anything in time must be changing. Anything not in time, such as the dead, cannot change.

If you do not keep changing for better (improve, grow), you are effectively dead.

— Me@2011.10.10

Although this paragraph is not 100% accurate, its spirit is useful.

— Me@2014.08.09

# Energy 2

energy ~ change

time ~ change

.

If you do not change, you cannot stay in time anymore.

So the key to keep the existence of yourself is to keep changing yourself.

— Me@2014-03-27 3:34 PM

.

.

# Energy

Energy is the ability of causing change.

Change is related to time.

That’s why energy is related to time.

— Me@2012-10-22 01:45:17 PM

Application of Noether’s theorem allows physicists to gain powerful insights into any general theory in physics, by just analyzing the various transformations that would make the form of the laws involved invariant. For example:

• the invariance of physical systems with respect to spatial translation (in other words, that the laws of physics do not vary with locations in space) gives the law of conservation of linear momentum;
• invariance with respect to time translation gives the well-known law of conservation of energy

— Wikipedia on Noether’s theorem

# 時、間、時間, 2

Time is a dimension in which events can be ordered from the past through the present into the future, and also the measure of durations of events and the intervals between them.

— Wikipedia on Time

— Me@2011.09.09

— Me@2013.06.10

# 數量

Number, Time, Money, 1.2

「量」的統一標準為之「數」。

— Me@2011.09.09

# 變通

Easy 3

Easy” in Chinese is “容易”, literally meaning “able to change“.

— Me@2012-11-29 10:47:38 AM

It is not the strongest of the species that survives, nor the most intelligent, but rather the one most adaptable to change.

— Charles Darwin misquotation

The definition of insanity is doing the same thing over and over and expecting different results.

— Albert Einstein misquotation

If you are willing to change based on the feedback from the reality, many difficult things will become easy.

— Me@2012.12.17

— 系辭下

— 易經

# Easy 2

Easy” in Chinese is “容易”, literally meaning “able to change“.

— Me@2012-11-29 10:47:38 AM

# Rich Hickey, 2

Like Clojure, Datomic incorporates an explicit model of time. All data is associated with a time and new data does not replace old data, but is added to it. Returning to our previous example, if John later changes his address, a new datom would be added to the database, e.g.

John, :street, “17 Maple St.”, T43

This mirrors the real world where the fact that John has moved does not erase the fact that John once lived on Swift St. This has multiple benefits: the ability to view the database at a point in time other than the present; no data is lost; the immutability of each datom allows for easy and pervasive caching.

— rjn945 15 days ago

— Hacker News

2012.03.21 Wednesday ACHK

# Change

change = delete the old one + create a new one

— Me@2010.11.28

# Number, Time, Money, 2.7

Ideal clock 3.7 | 時間定義 13.7

— Me@2011.09.16

# Number, Time, Money, 2.6

Ideal clock 3.6 | 時間定義 13.6

（安：第二個大問題是，你剛才講過，沒有一套數字標籤系統（時間讀數）的話，有多於兩件事時，無論是

1. 要建構事件序列；

2. 要在原本的事件序列中，加插額外的另一件事；還是

3. 要把兩個事件序列，組合成一個序列，

「十分明顯」的例子有：「甲 = 入大學；乙 = 大學畢業」。因為「入大學」是「大學畢業」的先決條件，所以「入大學」一定先於「大學畢業」發生。

「不十分明顯」的例子有：「甲 = 電燈面世；乙 = 電話面世」。

「十分不明顯」的例子有：「甲 = 地球形成；乙 = 火星形成」。

— Me@2011.09.14


text:
# Rotating a PDF file by n degrees, where n is not a multiple of 90

The problem I am facing is as following. I have a source document, src.pdf.

I need to insert the contents of src.pdf into target.pdf, rotated by n degrees, where n is NOT a multiple of 90.

Any help would be appreciated, thanks.

EDIT 1:

PDF contains no annotations.

I can use any solution which relies on utilities, or write my own code, preferably in C#/Python/Ruby/Perl, but not limited to a language.

The platform is Windows Server 2008 R2, I prefer to stick to the existing server but Linux is also an option. Latest (stable) GhostScript and pdftk are already installed.

-
Do you need utility programs or are you also ready to do some coding given some helper libraries? Which platform? And does your source PDF also contain annotations, not only static page content? –  mkl Nov 27 '12 at 14:57
Hi @mkl, I've edited the question and added these details in response, thank you. –  Roman Nov 27 '12 at 15:27
add comment

## 5 Answers

If a new language is not a problem, LateX could be an option. You can include a pdf as a figure in a tex file, and you will be able to use dedicated option like rescaling and rotating function. Then, compile it to obtain a new pdf. The very simple following code works for me :

\documentclass[a4paper]{article}
\usepackage{graphicx}

\begin{document}

\includegraphics[scale=0.5,angle=10]{test.pdf}

\end{document}

From this pdf:

I get this new one:

It will however need some manual ajustements to get exactly what you want...

-
Interesting approach! –  yms Nov 27 '12 at 17:11
@yms indeed, reminds me of university days... ;) Unless Roman already uses TeX on his system, though, that looks like quite a big install given the task. –  mkl Nov 28 '12 at 9:23
I decided to go with PDFLaTeX, as it provides all the required shift, cut, convert and rotate operations in a single, free tool. Thank you very much for the tip! –  Roman Dec 6 '12 at 10:51
add comment

This is an example showing how to do that using Java and the iText library. With minimal changes that code should be usable with C# and iTextSharp, too, giving the sample @neo could not provide on short notice in his answer.

The sample takes the first page ofsource.pdfand inserts it intotarget.pdfin all multiples of 30°, i.e. of 2*pi/12, but as that angle is explicitly given in the code, you can rotate by any angle.

Document document = new Document();
PdfWriter writer = PdfWriter.getInstance(document, new FileOutputStream("target.pdf"));
document.open();

PdfReader origPdfReader = new PdfReader("source.pdf");
PdfImportedPage importedPage = writer.getImportedPage(origPdfReader, 1);

PdfContentByte canvas = writer.getDirectContent();
for (int i = 0; i < 12; i++)
{
AffineTransform transform = AffineTransform.getRotateInstance(Math.PI * i / 6.0,
importedPage.getWidth() / 2, importedPage.getHeight() / 2);
canvas.addTemplate(importedPage, transform);
document.newPage();
}
document.close();

Depending on your use case you may not only want to rotate (as you asked for) but also to scale it down to fit the page. In that case simply addtransform.scale(scaleX, scaleY)before using thetransform.

-
add comment

I wrote some software which can do this:

cpdf -rotate-contents 45 in.pdf -o out.pdf

Commercial, I'm afraid. See Chapter 3 of the manual.

-
I've tried CPDF and indeed it does the job, and does it well. Also praises and thank you for the excellent e-mail support for your tool. I am currently going forward with the PDFLaTeX solution, but your answer qualifies as well. –  Roman Dec 6 '12 at 10:54
add comment

Since you do not have to deal with annotations, you could try using any PDF library of your choice that allows you to decompose PDF dictionaries and decode the page content. Once you get the page content, you can insert a transformation matrix at the beginning of the page: [ cos θ sin θ −sin θ cos θ 0 0 ]

I would recommend taking a look at the PDF Reference Document from Adobe, specifically the section about the transformation matrix.

For example if you have the following page content object (40 0 obj):

10 0 obj % Page object
<< /Type /Page
/Parent 5 0 R
/Resources 20 0 R
/Contents 40 0 R
>>
endobj % Page content
40 0 obj
BT
/F1 1 Tf
12 0 0 12 100 600 Tm
(Hello) Tj
ET
endobj

And you want to rotate the whole page by 45 degrees, assuming cos(45)=sin(45)=0.7, your resulting page content will be:

40 0 obj
0.7 0.7 -0.7 0.7 0 0 Tm
BT
/F1 1 Tf
12 0 0 12 100 600 Tm
(Hello) Tj
ET
endobj

After you finish adding the transformation matrix, you can re-compose your PDF file. The library you have chosen should then add compression filters and encoding filters as needed.

iText for example can decompose and recompose PDF files. See the method PdfReader.getPageContent for details.

-
add comment

Look into itextsharp which is a library in C# to manipulate pdf files. You can do this task programmatically. The same library is available in Java too.

-
I can't give complete code here. It's at least a lead for the person. –  neo Nov 27 '12 at 16:14
add comment


text:
## Physics: Principles with Applications (7th Edition)

Published by Pearson

# Chapter 3 - Kinematics in Two Dimensions; Vectors - Problems: 15

#### Answer

x-component: $(4580 m)(cos 122.4 ^{\circ}) = -2845 m$ y-component: $(4580 m)(sin 122.4 ^{\circ}) = 3589 m$ The z-component was given as 2450 m. The magnitude of the displacement is $5190 m.$

#### Work Step by Step

The x component is negative and the y component is positive, because the summit is to the west of north. The angle of the displacement vector measured counterclockwise from the positive x axis is 122.4 degrees. x-component: $$(4580 m)(cos 122.4 ^{\circ}) = -2845 m$$ y-component: $$(4580 m)(sin 122.4 ^{\circ}) = 3589 m$$ The z-component was given as 2450 m. The magnitude of the displacement is obtained using the 3 components and the Pythagorean theorem, and is 5190 m.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
# Kinetic energy car

For example if a car accelerates from 0 to 10 kph it creates 50,000 joules of kinetic energy? If a car acclerates from 0 to 20 kph it creates 200,000 joules of energy. Does this mean that four times the amount of energy is required from the cars engine to go from 0 to 20 kph instead of 0 to 10 kph? Or is this kinetic energy the result of some other type of conversion?

Last edited:

Nabeshin
Not exponentially, just quadratically. And the energy obviously comes from however you doubled the car's velocity (people pushing, the engine, an explosion, etc.).

russ_watters
Mentor
And you'll notice this manifesting in a car accelerating from 30-60 much slower than from 0-30.

Not exponentially, just quadratically. And the energy obviously comes from however you doubled the car's velocity (people pushing, the engine, an explosion, etc.).

Thanks! What I am also trying to determine is all the kinetic energy that is generated by the cars movement simply a result of the acceleration (velocity) itself. I'm guessing not otherwise mass would not be part of the formula for working out the amount of kinetic energy produced?

Last edited:
The formula for KE comes from assuming that conservation of energy will be obeyed, so the work done to accelerate the car will be equal to its change in KE. Begin with this equation from kinematics: vf^2 - vi^2 = 2ax, where vi is initial velocity, vf is final velocity, a is acceleration, x is displacement. Multiply each term by the object's mass m. Replace ma by force F. Change the 2 on one side to a (1/2) on the other side. Replace Fx by work W. Now, if you define the term (1/2)mv^2 to be something called KE, your equation will say this: work done = final KE - initial KE. This was just derived only for the case where the force was constant over the displacement, making it legal to say work W = Fx instead of using calculus, but since conservation of energy is a general law, the expression for KE is general also.

Last edited: