text:
Talk:Finite difference

Better description needed
The description of finite difference methods seems somewhat muddled - there appears to be a confusion between particular finite difference methods and the general definition of the term. It seems to me that at the very least the article ought to partition itself a little better - for instance, if difference operators are mentioned, it would be nice to at least indicate that there is more than one and that all are derived from Taylor expansions. I don't necessarily feel myself qualified to make any modifications that might be necessary - if anyone is, then perhaps they could edit this topic?

If I could expand on this. "Finite Differences" is about replacing derivatives by differences, it can be applied in 1 dimension or several and to any order of derivative. Perhaps a few examples rather than one would be more informative. "Finite Difference Equation" arises when we substitute finite differences for the derivatives in a differential equation. Closely allied to this is the idea of a method of solution, by putting unknowns in terms of known quantities. In ordinary differential equations this gives a variety of solution methods. In PDEs the methods are called Finite Difference Methods.

Crank-Nicolson
(Note: Nicholson is a common misspelling of Nicolson. Refer to original paper (1947) or The Mathematics of Diffusion by John Crank.)

Regarding the Crank-Nicolson, I am pretty sure that the convergence order is $$O(h^2) \, $$ and not $$O(h^4) \, $$. The advantage over the implicit method is basically in the improvement of the convergence speed regarding the time step, which is $$O(k^2) \, $$ instead of $$O(k) \, $$ of the implicit method.

I decided to post it here so we may discuss it instead of overwriting it, just in case to be sure.

 * Volemak(talk)

I am copying the discussion from User Talk pages:

 * Hello. You wrote in finite difference that Crank-Nicolson is fourth-order in space. Could you please make sure that this is true, preferably by giving a reference? I'm pretty certain that Crank-Nicolson is second-order, but it might just be possible that it is fourth-order for this specific setting, and I won't be in my office for some time so it will be hard for me to check it. -- Jitse Niesen (talk) 22:40, 20 December 2005 (UTC)

 * I will look for a paper source.

 * But the order can be easily derived.

 * Lets take the first six members of the Tailor series of $$f(x-x_j)$$ at time t=Nk+1/2
 * $$f(x)=a0+a1x+a2x^2+a3x^3+a4x^4+a5x^5+0(x^6)$$
 * we can find the second derivative over x, then find first derivative over time from the heat transfer equation, then find the second derivative over space over df/dt and find the second derivative over time etc.

 * Thus the Tailor decomposition over x and t will look like:

 * $$f(x,t)=a0+a1x+a2x^2+a3x^3+a4x^4+a5x^5+0(x^6)+D(2a2t+6a3tx+12a3tx^2+20a5tx^3+0(tx^4))+D^2(12a4t^2+60a5t^2x+0(t^2x))+0(t^3)$$
 * where D is the thermal diffusivity.

 * if we substitute the obtained equation for x=-h,0,+h and t=-k/2 +k/2 into Crank Nicolson scheme, we will see all the terms written are cancelled and the Crank-Nicolson scheme is exact. Thus, the errors came from the terms for x^6 and t^3 and so they are proportional to h^4 and k^2 (we take 2nd order derivative over x and the first over t).

 * Obviously, to get the fourth order over h we should take care over the boundary conditions. E.g. maintaining the adiabatic b.c as $$x_N-x_{N-1}$$ would destroy the 4th order instantly, but the scheme itself is 4th order (if the coefficients are constant).

 * BTW for the explicit scheme for the special case of r=1/6, we a getting the quadratic error over t and fourth orders over x. I am not sure if we should mention it. abakharev 00:08, 21 December 2005 (UTC)

 * The easiest way of checking this is to plug the Crank-Nicolson scheme into mathematica, subtract from it the exact derivatives (heat equation that is), and expand all in Taylor series (mathematica has a command for that). One can also do Maple too I think. Symbolic calculations saved my ass a lot of times when dealing with messy finite-difference schemes. Oleg Alexandrov (talk) 16:25, 21 December 2005 (UTC)

Implicit Method (backward difference)
The recurrence equation in description of the Backward difference is incorrect. Looks like the recurrence relation of forward difference has been restated again.

Backward difference recurrence equation should be Y(x) - Y(x-1)....

 * I'm afraid I have no idea what you mean. The right-hand side of the recurrence relation for backward differences is at time n+1, and the rhs for forward difference is at time n. There is no Y defined in the article. -- Jitse Niesen (talk) 05:39, 10 April 2006 (UTC)

Reorganization
I'm proposing a reorganization of this article and finite difference schemes on Talk:Finite difference schemes. Please comment. -- Jitse Niesen (talk) 11:52, 31 July 2006 (UTC)

Mathematical analysis vs. numerical one
I think there are two different notions of finite difference in math, one is in numerical analysis and another one is in mathematical analysis.
 * 1) in the first case it is an "mathematical expression of the form f(x + b) − f(x +a)". In second it is an operator which is not a "mathematical expression".
 * 2) in the first case it is denoted as $$\Delta[f](x)$$ while in the second $$\Delta_h^m(f,x)$$. I have never seen the first notation applied to an operator.
 * 3) the mathematical books can divided in to two groups: first group books mention only forward and backward differences and say nothing about operators, while second group books work with operators only.
 * 4) $$\Delta^{n-1}(\Delta_{}^{})$$ is usual for operators but almost nonsense for numerical analysis.

It's like operators in functional analysis and algebra — much in common but different notions. Mir76 17:46, 16 March 2007 (UTC)

 * I'm not sure that I understand what you say, but I disagree with there being separate meanings in numerical and mathematical analysis:
 * 1. In my experience, in both fields "finite difference" usually refers to a "mathematical expression of the form f(x + b) − f(x + a)", with the operator being called a "finite difference operator". Can you name some books that use "finite difference" to refer to the operator?

 * Yes, it is quite common experience of specialist in numerical analysis :) Ok, here goes the first book fell into may hands: Paul L. Butzer, Hubert Berens "Semi-group of operators and approximation", Springer-Verlag, Berlin Heidelberg New York, 1967. Page 257:

Let $$\Delta^r_hf=[T(h)-I]^rf = \sum\limits_{l=0}^r (-1)^{r-l}\binom{r}{l}f(\cdot+lh)$$ be the right difference of a function f...
 * I think I have to explain something. Here $$T(h)$$ is a shift operator (f(x) –> f(x+h)) and $$I$$ is an identity operator (f(x) –> f(x)). It is the only definition of diffrencies in this book and there are no central differencies in whole book at all.

 * Next example: Charles K. Chui "An introduction to wavelets", formula (4.1.9), translated back from Russian:

We will use backward differences defined as $$(\Delta f)(x)= f(x)-f(x-1)$$; $$(\Delta^n f)(x)= (\Delta^{n-1}(\Delta f))(x)$$.
 * I'm almost sure I saw something similar in Ingrid Daubechies' "Ten lectures on wavelets" but I cannot find it right now. I can say that Berens and Chui both are very high class mathematicians.
 * Moreover every book dealing with Besov spaces will use this notation. Mir76 17:55, 18 March 2007 (UTC)

 * It seems to me that Chui's quote agrees exactly with what I said: The expression $$f(x)-f(x-1)$$ is called a "backward difference". The "backward difference operator" is Δ, and the result when you apply this operator is the "backward difference". Similarly, Butzer & Berens say that $$\Delta^r_hf$$ (the result of applying the operator to a function f) is a "right difference".
 * Now, it happens quite often that functions and their result is confused in mathematics, so people talk for instance about "the function $$f(x)$$" even though it's more precise to say "the function $$f$$". So I would argue that possible confusion between the operator and the result of applying the operator does not show that the notion of "finite difference" in mathematical analysis differs from that in numerical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)

 * 2. The notation $$L[f](x)$$ is common in numerical analysis and other branches of applied mathematics to refer to the operator L, applied to the function f, and the resulting function evaluated at x; see for instance calculus of variations. The idea is to distinguish operators (which are applied to functions) and functions (which are applied to numbers) by using square brackets [] for the former and round parentheses for the latter. However, the notation $$\Delta[f](x)$$ is by far not the only one used in numerical analysis. I've also seen $$(\Delta f)(x)$$, $$\Delta(f)(x)$$ and $$\Delta(x,x+h)(f)$$. The subscript h is also used frequently in numerical analysis.
 * I think you are right here but when I have added $$\Delta_h^n(f,x)$$ to article, Oleg Alexandrov reverted it with some edits of unknown person. That's why I have arranged separate section for analysis. Mir76 17:55, 18 March 2007 (UTC)

 * 3. It's true that some books do not look at the operator aspect. However, there are plenty of numerical analysis books that work with operators. For instance, the equation $$hD = \log(1+\Delta)$$ uses operators, yet I got this equation from a numerical analysis book.
 * Does that book work with shift operator above? Do all students of numerical analysis understand about operator's notation? I have an experience that answer is No. Mir76 17:55, 18 March 2007 (UTC)
 * Yes, it uses the shift operator. Regarding your second question, I don't know quite what you mean. I expect that all students will be able to understand the operator notation if it is explained to them. It's not a big deal after all.
 * You seem to underestimate the amount of mathematical analysis used in numerical analysis. Semi-groups of operators are used in numerical PDEs, approximation theory is a standard part of courses in numerical analysis, and wavelets are arguably as much numerical analysis and mathematical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)

 * 4. Where do you get the formula $$\Delta^{n-1}(\Delta)$$ from? That seems sloppy notation: the domain of Δ is a space of functions so you can't apply Δ to itself.
 * Surely I can. It is an operator's composition :). See, for example, Chui above. It is really very common definition. That's why I need separate section — to protect this definitions from numerical analysis students. Mir76 17:55, 18 March 2007 (UTC)
 * Well, normally composition is denoted like $$\Delta^{n-1} \circ \Delta$$. In the quote of Chui, he uses $$\Delta^{n-1}(\Delta f)$$ which is not the same as $$\Delta^{n-1}(\Delta)$$.
 * You are using expressions like $$log(1+\Delta)$$ above without any problem, but domain of $$log$$ is $$(0, \infty)$$, not $$C[a,b]$$.
 * Your last sentence is very much against the ethos here: you don't own a section but you have to allow others to edit it. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)
 * I am quite aware of this. I am happy when my contributions are improved and I am not happy when they are reverted.

 * 5. "It's like operators in functional analysis and algebra" — What do you mean with an operator in algebra?
 * Ok, it was mistranslation from Russian. I'll try explain it in another words: Consider two operators: first one is multiplication of vector to square matrix, second one is taking a value of function in one fixed point (f(x) —> f(1)). They are both operators. But one of them has eigenvalues whilst other has not. Mir76 16:37, 19 March 2007 (UTC)

 * 6. So, I still think that there are two different notions here. -- Jitse Niesen (talk) 06:45, 18 March 2007 (UTC) I wanted to say: I still don't think that there are two different notions here. Sorry about the confusion. -- Jitse Niesen (talk) 02:46, 19 March 2007 (UTC)

 * Mir76, there were several issues with your edit. Firstly, you changed the notation for central differences from δ to Δ even though this clashes with the notation for forward differences, but you didn't make this change throughout the whole article. Then you introduce your favorite notation, even though that doesn't seem to add to the article. Finally, you used your notation, instead of the notation used in the rest of the article, to define higher-order differences, writing
 * $$\Delta_h^n(f,x) = \Delta_h (\Delta_h^{n-1}(f,x))$$
 * where you should have written
 * $$\Delta_h^n(f,x) = \Delta_h (\Delta_h^{n-1}(f,x),x).$$
 * So there were plenty of reasons to revert and none of them has to do with any difference between mathematical and numerical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)

 * Never have did this. I do not know who is 80.7.146.126, he is surely not me. What I have done — added line "Sometimes this difference is denoted $$\Delta_h(f,\,x)$$" which is obviously right. After that I used this particular notation for defining higher order differences since there were no proper definition. And yes, I have made something which looks to you as an two symbols typo — omitted obvious argument. After that, instead of correcting a typo Alexandrov erased my notation and my definition of higher order differences. So I decided that he didn't recognized them (sorry for that assumption) and started another section with operator's point of view. 16:37, 19 March 2007 (UTC)

If there's a difference between the 'mathematical' and 'numerical analytic' uses of the term finite difference, I can't see it. It doesn't matter whether one views it in terms of the f.d. operator or not. JJL 13:01, 19 March 2007 (UTC)
 * For me main difference is that one thing thing is an expression while other is an operator. Mir76 16:37, 19 March 2007 (UTC)

Summary
What I had done:

1. Added notation $$\Delta_h^m(f,x)$$.

2. Added $$\Delta_h^n = \Delta_h (\Delta_h^{n-1})$$ (I do not need an argument f(x) here, it is like f(r(t)) = f(r)).

3. Added definition of difference as an operator, not expression (I strongly believe that operator is not expression, e.g. Fourier transform is not an expression).

4. Mentioned some pages where this operator is used.

I need all these four items (and they are not my fantasies, as you can see). I do not know how to incorporate this issues (especially #3) into existing article without breaking it. It is too much biased for numerical analysis now. So I started another section which is mathematical analysis oriented. I will be really happy if somebody will merge (not simply revert) this two sections in one. Or we can separate them to different articles. Mir76 16:37, 19 March 2007 (UTC)
 * Nobody reverted your sections additions, here's the diff. I just removed the intro, which was incorrect, and renamed a section. All the other text you put in including the formulas did not change. So I had basically done the merge you are suggesting above. Oleg Alexandrov (talk) 03:02, 20 March 2007 (UTC)
 * Ok, I have to acknowledge — at that time I haven't read the diff carefully, I only saw several added by me paragraphs were removed all together. I didn't like them, but they were needed to explain splitting of the article. Let state that we both have reverted each other once (March, 12 and March, 16).
 * But this doesn't help much, since after your second edit article became really weird (see http://en.wikipedia.org/w/index.php?title=Finite_difference&oldid=115574544). There were two definitions of difference, two definitions of higher orders differences, two subsections concerning derivatives and no explanation why the article is split in such a way. And, more curious, finite difference is surely an operator, but finite difference operator is another thing, not equal to finite difference. So your new section title wasn't very good.
 * I can not say it was merging. Mir76 08:57, 20 March 2007 (UTC)
 * It was not at all a revert, and it did not have the "revert" word in the summary. Where did you get that from? I just removed the incorrect intro. Oleg Alexandrov (talk) 14:55, 20 March 2007 (UTC)

 * In numerical analysis we use the operator notation to develop new finite difference formulas. A finite difference f(x+h)-f(x) is the result of applying a finite difference operator to a function. You'll find this throughout books on the num. sol. of PDEs, for example. To me, it's like distinguishing between saying that the derivative of x^2 is an operator that acts on x^2 to produce another function and saying that the derivative of x^2 is 2x, the result of having applied that operator. I use "derivative" for both of these closely related ideas. If you're trying to distinguish here between a finite difference operator and the result of that operation from the point-of-view that you could ask questions of the operator like "Is it linear and bounded, and what is its spectrum?" then it's true that those are different perspectives on it. But I don't see two corresponding entries for theoretical vs. applied derivative, integral, etc. So, I think that this isn't a distinction worth drawing here, and I definitely feel that num. analysts view it as an operator too...a very useful one! I'm inclined to revert. JJL 17:52, 19 March 2007 (UTC)
 * "I'm inclined to revert" means erasing items 1-4 above? Mir76 08:57, 20 March 2007 (UTC)
 * Or at least integrating them into the article. I still don't believe there's a distinction here that's important at the level of this entry. There are lots of things that can be viewed as operators. Yes, del and del(f) are not the same object, but they're the same idea and don't arise from/reside in wholly separate areas of math. I think they're two closely related aspects of one thing and not two different things. Where else is a specific operator given its own page/subpage, separate from what it does? JJL 12:41, 20 March 2007 (UTC)
 * In my part of article operator is defined and clearly explained what does he do - he returns another function. In first part difference returns a number and it is also explicitly stated. Mir76 16:50, 21 March 2007 (UTC)

 * May be the main reason for me to create separate section was that I personally do not like definition

A finite difference is a mathematical expression of the form f(x+b) − f(x+a)
 * since it is only half of the truth. I do not know how to insert operators there. I cannot see that derivative or integral are defined as an expression. Mir76 08:57, 20 March 2007 (UTC)

I give up. I can not seamlessly integrate those items into the numerical analysis part of article since I am not a specialist in that field, and would do more damage than profit. I have already tried without much success, maybe you can do it better. I have tried to make the introduction softer I ask not to remove it before real merge will be done. Mir76 16:50, 21 March 2007 (UTC)

Explain 'Generaliztions' notation?
Right now I'm stealing Finite Differences for a problem, thanks to the contributors of this article. I found the article useful, helpful, understandable, and the discussion also interesting and helpful. I was especial gratified (proud) to see the quality and level of collaboration shown here in discussion. Well done. I think this collaboration illustrates that the voice and views of non-experts are an important aid to communication by experts. :)

I found a difficulty in the article, however, and hope it can be clarified. In viewing the article I found the notation in 'Generalizations' confusing where it said :$$\Delta_h^\mu[f](x) = \sum_{k=0}^N \mu_k f(x+kh),$$. The rest of the article refers to the superscript on Delta as the 'order', and it would therefore appear the mu on Delta should be N here. [also n is used throughout instead of N, so perhaps n might be regarded as more consistent?] Thank You. —Preceding unsigned comment added by 76.191.132.120 (talk) 23:04, 23 January 2008 (UTC)

 * Order of differantional operator depends on order of polynomial it annihilates. Classical finite differences of order n kills polinomials of order n-1. If you change the coefficients to $$\mu_k$$ it can kill or can kill not polynomials of particular degree — this depends upon $$\mu_k$$. Here N is a length of coefficients vector $$\mu_k$$.

 * So notion of order is not applicable here and free superscript place was used for another (but having similar meaning) parameter. This should be incorporated into main article sometime... Mir76 (talk) 09:55, 12 March 2008 (UTC)

No historical perspective
A reproach that I should make to many math entries: they seem exclusively aiming at people who already know the subject! Apart from mathematicians that do pure math for a living, there is a vast constituency of professional (millions) trained in other disciplines requiring a fair amount of math. Those "users" of math are often curious about math subjects beyond what they were taught. However, before they invest any time in additional math, they have to evaluate the pertinence of it to their core interests. How to do that if each and every subject is not presented with enough information regarding the "why" it came into existence and the "how" it was used so far. Of course, some very new subject may have little history and no immediate application, yet, most subjects deserving a wikipedia entry are not in this class. Indeed, they are in wikipedia very much because they represent something of value to many praticionners.

I suggest a brief history of the concept and a quick survey of the applications (in math and beyond) where it revealed itself as critical would do wonders for the natural readership of those articles.
 * I couldn't have said it better myself. I stumbled upon this article through a tutorial on computer graphics dealing with Particle systems. The "Description" section of this article was written in mathematical jargon way beyond my comfort level; but in no way was I able to gain any insight into why central differences might be relevant to creating a Vector field. Not that I wanted someone to necesssarily hold my hand, but the "definition" cited here is purely abstract and does not present any practical applications that I might be able to relate to my particular field of study.

Symbol definitions
What does the symbol "h" refer to in the formulae in this article? I can't find it defined in the article itself. It would be nice if it were clarified. Showeropera (talk) 18:05, 1 May 2020 (UTC)

A second (recurrent!) sore point is the matter of the local jargon. Mathematicians seemed to be the only species of scientific workers that assume their jargon (i.e their notation) does not need to be properly introduced. Sorry, if you want to be understood, you need to be precise about the conventions your are following. It happens that millions of practitioners in related fields use your beloved symbols in entirely different context, sometimes with the same meaning and sometime with a different meaning. Without an easily accessed link to the proper glossary and grammar, your brilliant demonstrations looks like as many tantalizing charades.

I suggest such math entries should always include, at the top, a link to another wiki page that would contain all the symbols used in the article and their meaning in that type of context. This glossary page could, of course, be used by many articles on related subjects, providing they do not depart from the same convention. By the way, this is what many other professions do with success (programmers among others).

I second this suggestion! Necmon (talk) 10:33, 28 October 2008 (UTC)

central difference
i am citing this from the article: "The main problem with the central difference method, however, is that oscillating functions can yield zero derivative. If h(nh)=1 for n uneven, and h(nh)=2 for n even, then f'(nh)=0 if it is calculated with the central difference scheme. This is particularly troublesome if the domain of f is discrete." can someone clarify this (messy) example? bad expression prevents me from checking if the statement is true. also the statement suggests, that there are no such problems when using the one-sided difference. i'd like to see an example that's problematic with one but not the other, also i'm interested to know how a discrete domain of a (not-yet-discretized) function is reasonable in a case where one wants to approximate the derivative. 91.15.153.48 (talk) 13:45, 16 May 2010 (UTC)

I'm pretty sure that that example is just wrong. It seems perfectly reasonable to say that the derivative is 0 everywhere and that there is only a second derivative at grid points. — Preceding unsigned comment added by 137.22.170.42 (talk) 17:27, 4 June 2018 (UTC)

Many,(eg numerical analysts), consider definition of the central difference operator to be (f(x+h) - f(x-h))/2h and not (f(x+h/2) - f(x-h/2))/h CSDarrow (talk) 16:22, 30 March 2012 (UTC)

Multivariate example
When it is first presented, the derivative of the univariate "f" is described as "f' = (f(x+h/2) - f(x-h/2))/h". In the multivariate example, it appears as "f_{x} = (f(x+h,y) - f(x-h,y))/2h" (someone compesates the "h" by dividing by "2h", seems ok...). However, for the formula of "f_{xx}" it is divided by "h^2". It seems to me that the "h" used for "f_{x}" is not the same as for "f_{xx}". The denominator for "f_{xx}" should be "4h^2" if "f_{xx}" was derived from "f_{x}" (as it seems from the context...). I am not a math person... and I may be even wrong... but I've got confused with that... Capagot (talk) 19:15, 17 September 2010 (UTC)

Accuracy
I think it would be welcome to add some info on how these formulas are affected by floating point aritmetics, e.g. the effects of cancellation and the tradeoff between truncation error and rounding error for different step-sizes. — Preceding unsigned comment added by 130.237.43.79 (talk) 14:04, 11 July 2011 (UTC)

Example using the Fibonacci Sequence
Shouldn't the canonical first few numbers (0, 1, 1, 2...) be used in the Fibonacci example, and not (2, 2, 4) as currently done? Syd Barrett (talk) 21:49, 12 May 2013 (UTC)

Actually this is not the Fibonacci sequence. This is a mistake. — Preceding unsigned comment added by 24.34.193.55 (talk) 18:04, 17 June 2014 (UTC)

This page appears to be a bit WP:OR-framed/misguided and inconsistent (with itself)
Starting with the definition, which appears hard to source as-is. The topic that can actually be found in numerous books is finite difference approximation (of derivatives). The word "approximation" is not gratuitous, because a (first-order) finite difference approximation of the derivative is indeed the difference quotient, and the symmetric difference quotient is the 2nd-order approximation of the (first) derivative etc. See   for instance. ¶ Going to the 1st section of this page, perhaps there are some sources [though none are cited inline on the page] which define the forward/backward/central different without division by h (or 2h), but those I've looked at [see links in previous sentence] don't do that. Also, this article is inconsistent with itself when it moves on to "2nd order central" [section] and so forth, where it defines them as including division by h2 [in the case of the "2nd order central"] etc. Speaking of which, the "2nd order central" is actually the difference quotient of the second symmetric derivative etc. ¶ So basically Wikipedia has two rather bad quality pages (this and difference quotient) on (more or less) the same topic [framed poorly] an no page on the real topic...  There's a bit better material at numerical differentiation, on the basics at least, but it's not broad enough. Some1Redirects4You (talk) 12:47, 27 April 2015 (UTC)

 * I am not convinced you have not misunderstood WP editorship. This is not a forum of critical discussion, but a hands-on proposed improvements venue. What, exactly, are you proposing to do to improve the article? "Unfunded mandates", asking someone else to fix this to your satisfaction are hardly constructive. I would disagree with you that this is an "off subject" article. It is distinctly not about finite differences as an approximation tool, and more pitched to umbral concepts and techniques. The introduction you are fussing about appears like a bag of definitions for the reader unfamiliar with the language. Why don't you try to rewrite difference quotient to the satisfaction of its editors, instead? Cuzkatzimhut (talk) 13:28, 27 April 2015 (UTC)
 * I am talking about this article in the paragraph above. If you reread what I wrote carefully, you might see that. Some1Redirects4You (talk) 13:31, 27 April 2015 (UTC)
 * After looking a bit at the various references, it seems the presentation here bears some resemblance to the 1939 book of Jordán Károly. Alas, that's a rather obscure book nowadays, which doesn't seem to have inspired treatment along that line in [m]any subsequent sources. Don't even get me started on the 1870 book of Boole being used as source here. Boole didn't even understand well enough the algebra that bears his name in order to use it a source for contemporary presentations, so I doubt this other books of his is much better. The calculus of finite differences (as conceived/presented in the works of Boole and Károly) doesn't seem to have much relevance today. So it should not influence the presentation outsider of that section, which might even be better to spin off to its own article owing to too numerous idiosyncrasies of little relevance except to math historians, perhaps. Some1Redirects4You (talk) 13:29, 27 April 2015 (UTC)

To summarize what I wrote above: to most [in not all] present-day sources finite difference[s] refers to finite difference approximations and not to the finite difference calculus of Boole & Károly. Some1Redirects4You (talk) 13:37, 27 April 2015 (UTC)

Gratuitous distracting Isaac Newton template
User:TonyTheTiger reinserted a gratuitous, indeed, highly inappropriate template on Isaac Newton at the bottom of the article, which I had removed, purporting not to be convinced by my explanation that the article is not a shrine to Newton. Well, it isn't! Newton's interpolation formula is properly showcased in its own section, but this technical article is not about Newton. George Boole has much more to do with it, or the umbral mathematicians mentioned---and besides, this is not a history-heavy venue.

Sticking in handles on irrelevant hero-worhip information degrades the quality of the article. The same knee-jerk abuse has been inflicted on Table of Newtonian series, Newton polynomial, etc... It looks like anything with Newton's name in it has been contaminated this way. I fear the inserter may well not care to read and understand the article in the first place. I leave it to somebody else to remove it this time, but ... Behold! Cuzkatzimhut (talk) 10:35, 15 October 2015 (UTC)
 * , what kind of hero worship do you suggest. I barely know Newton. I only have a masters in stats. I have no higher hard core degrees and have not studied physics since high school (over 30 years ago). I am just doing the template because Newton is a WP:VA subject without a template. I asked for help creating the template on a half dozen project talk pages. Since no one would step up, I did the template myself. This is a basic navbox and unless this article is malplaced on the navbox, it seems that this page is an appropriate location for the template.--TonyTheTiger (T / C / WP:FOUR / WP:CHICAGO / WP:WAWARD) 19:46, 16 October 2015 (UTC)

As I indicated, this is not an article about Newton's work, which is, of course, represented in a section of it. In that sense, it may well be placed in the navbox.

However, I don't believe this is an excuse to throw sundry unrelated Newtoniana at the hapless reader who comes to this article to learn about the calculus of finite differences and possibly the umbral marvels underlying them. As I indicated, seeing the Newton template here one might get the unsound impression that, somehow, this is about Newton's life work  and not about math, so, yet another exhibit in Newton's shrine. The template is fine in Newton's wiki, or other ones, but wildly distracting here. I appeal to the common sense of the other page watchers to remove it. If you really wished to be constructive, you might initiate merges of the Table of Newtonian series etc... into this article. Cuzkatzimhut (talk) 20:11, 16 October 2015 (UTC)

Possible Mistake
Here is The relationship of these higher-order differences with the respective derivatives is straightforward,
 * $$\frac{d^n f}{d x^n}(x) = \frac{\Delta_h^n[f](x)}{h^n}+O(h) = \frac{\nabla_h^n[f](x)}{h^n}+O(h) = \frac{\delta_h^n[f](x)}{h^n} + O(h^2).$$

Since the $$\frac{\Delta_h[f](x)}{h}=\frac{d f}{d x}(x)+O(h)\rightarrow \frac{d f}{d x}(x)<\frac{\Delta_h[f](x)}{h}$$, so in the expression $$\frac{d^n f}{d x^n}(x) = \frac{\Delta_h^n[f](x)}{h^n}+O(h) = \frac{\nabla_h^n[f](x)}{h^n}+O(h) = \frac{\delta_h^n[f](x)}{h^n} + O(h^2).$$ the plus symbol should be replaced to minus, or derivative and differnce operators places to be changed inversible. (Just my oppinion, could be wrong) --KolosovP (talk) 18:23, 4 August 2016 (UTC)

 * You appear confused about the meaning of the Big O notation. This item should have been placed at the bottom of the page as per talk page instructions.Cuzkatzimhut (talk) 16:11, 16 August 2016 (UTC)

The big O notation is limiting of the "greater" function above "smaller", so if g(x)<k(x) means k(x)=g(x)+O(x), right? The derivative in particular point always smaller then difference, its shown before in the article, so the difference no have limiting behavior by derivative or im wrong? --KolosovP (talk) 05:24, 17 August 2016 (UTC)

 * Wrong. The definition explicitly emphasizes absolute values, not signs. Please read the article and its illustrations. Cuzkatzimhut (talk) 11:26, 17 August 2016 (UTC)
 * Even that, the aboslute value of derivative taken by some set lesser then abs of differnece, so big O could be negative value ? --KolosovP (talk) 14:26, 17 August 2016 (UTC)

I am not sure you appreciate the asymptotic notation: do you agree that  $f(x)=O(g(x))$  and    $−f(x)=O(g(x))$  mean exactly the same thing? Cuzkatzimhut (talk) 16:00, 17 August 2016 (UTC)

 * Moved to bottom of the Talk page as per WP rules

What is being bounded is the differences $$\frac{d^n f}{d x^n}(x) - \frac{\Delta_h^n[f](x)}{h^n}$$, etc, so no signage is meaningful. Cuzkatzimhut (talk) 16:06, 17 August 2016 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified one external link on Finite difference. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20090419132601/http://www.stanford.edu:80/~dgleich/publications/finite-calculus.pdf to http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 19:56, 31 December 2016 (UTC)

Upper summation limit missing?
In the section "Newton's series", in the last formula, at the leftmost summation sign, should not an upper summation bound be mentioned there? I suspect an infinity sign is missing. Is that correct?Redav (talk) 08:40, 17 May 2020 (UTC)

More accurate? Or rather of higher order in h?
In the article I read: "However, the central (also called centered) difference yields a more accurate approximation."

In my view, and as explained after the cited text, given a certain mesh size $$h$$, a central difference is not necessarily more accurate than a forward or backward difference.

What seems true is that the rate of convergence to the actual derivative in the limit for small $$h$$ is faster.

The confusion seems to be as if a higher convergence rate were synonymous with higher accuracy for a fixed value of $$h$$. Does anyone disagree?Redav (talk) 10:32, 24 May 2020 (UTC)

India Education Program course assignment
This article was the subject of an educational assignment at College of Engineering, Pune supported by Wikipedia Ambassadors through the India Education Program. Further details are available on the course page.

The above message was substituted from by PrimeBOT (talk) on 19:53, 1 February 2023 (UTC)

inconsistency in higher order section
There seems to be missing denominator h terms in the higher order derivative section. It would be nice to have a citation here to look it up, but I'd guess it is h^n. 018 (talk) 23:44, 12 November 2023 (UTC)

Formula in Multivariate Finite Difference
While I have not attempted to prove this through Taylor expansions, the formula below appears to be incorrect. I say this because I have implemented both this and the other partial derivative formula in a code I've written. Since this article contains two formula for the same second-order partial derivative, it is easy to verify that the two formula give very different results. Moreover, I can reconstruct an approximation of the initial function through a two-dimensional Taylor expansion. However, when I do this using the formula below, the Taylor expansion clearly deviates from the initial function. The other formula in the article appears to work without issue. This comparison was made using the same f, h, and k.

$$ f_{xy}(x,y) \approx \frac{f(x+h, y+k) - f(x+h, y) - f(x, y+k) + 2 f(x,y) - f(x-h, y) - f(x, y-k) + f(x-h, y-k)}{2hk},$$ 73.127.166.120 (talk) 19:00, 21 June 2024 (UTC)

title: Talk:Finite difference


text:
Treeshrew

The treeshrews (also called tree shrews or banxrings ) are small mammals native to the tropical forests of South and Southeast Asia. They make up the entire order Scandentia, which split into two families: the Tupaiidae (19 species, "ordinary" treeshrews), and the Ptilocercidae (one species, the pen-tailed treeshrew).

Though called 'treeshrews', and despite having previously been classified in Insectivora, they are not true shrews, and not all species live in trees. They are omnivores; among other things, treeshrews eat fruit.

Treeshrews have a higher brain to body mass ratio than any other mammal, including humans, but high ratios are not uncommon for animals weighing less than 1 kg.

Among orders of mammals, treeshrews are closely related to primates, and have been used as an alternative to primates in experimental studies of myopia, psychosocial stress, and hepatitis.

Name
The name Tupaia is derived from tupai, the Malay word for squirrel, and was provided by Sir Stamford Raffles.

Description

Treeshrews are slender animals with long tails and soft, greyish to reddish-brown fur. The terrestrial species tend to be larger than the arboreal forms, and to have larger claws, which they use for digging up insect prey. They have poorly developed canine teeth and unspecialised molars, with an overall dental formula of

Treeshrews have good vision, which is binocular in the case of the more arboreal species.

Reproduction
Female treeshrews have a gestation period of 45–50 days and give birth to up to three young in nests lined with dry leaves inside tree hollows. The young are born blind and hairless, but are able to leave the nest after about a month. During this period, the mother provides relatively little maternal care, visiting her young only for a few minutes every other day to suckle them.

Treeshrews reach sexual maturity after around four months, and breed for much of the year, with no clear breeding season in most species.

Behavior
Treeshrews live in small family groups, which defend their territory from intruders. Most are diurnal, although the pen-tailed treeshrew is nocturnal.

They mark their territories using various scent glands or urine, depending on the particular species.

Diet
Treeshrews are omnivorous, feeding on insects, small vertebrates, fruit, and seeds. Among other things, treeshrews eat Rafflesia fruit.

The pen-tailed treeshrew in Malaysia is able to consume large amounts of naturally fermented nectar from flower buds of the bertam palm Eugeissona tristis (with up to 3.8% alcohol content) the entire year without it having any effects on behaviour.

Treeshrews have also been observed intentionally eating foods high in capsaicin, a behavior unique among mammals other than humans. A single TRPV1 mutation reduces their pain response to capsaicinoids, which scientists believe is an evolutionary adaptation to be able to consume spicy foods in their natural habitats.

Taxonomy
They make up the entire order Scandentia, split into the families Tupaiidae, the treeshrews, and Ptilocercidae, the pen-tailed treeshrew. The 20 species are placed in five genera.

Treeshrews were moved from the order Insectivora into the order Primates because of certain internal similarities to primates (for example, similarities in the brain anatomy, highlighted by Sir Wilfrid Le Gros Clark), and classified as a "primitive prosimian", however they were soon split from the primates and moved into their own clade. Taxonomists continue to refine the treeshrews' relations to primates and to other closely related clades.

Molecular phylogenetic studies have suggested that the treeshrews should be given the same rank (order) as the primates and, with the primates and the flying lemurs (colugos), belong to the grandorder Euarchonta. According to this classification, the Euarchonta are sister to the Glires (lagomorphs and rodents), and the two groups are combined into the superorder Euarchontoglires. However, the alternative placement of treeshrews as sister to both Glires and Primatomorpha cannot be ruled out. Some studies place Scandentia as sister of the Glires, which would invalidate Euarchonta: It is this organization that is shown in the tree diagram below.

Several other arrangements of these orders have been proposed in the past, and the above tree is only a well-favored proposal. Although it is known that Scandentia is one of the most basal Euarchontoglire clades, the exact phylogenetic position is not yet considered resolved: It may be a sister of Glires, Primatomorpha, or Dermoptera, or separate from and sister to all other Euarchontoglires. Shared short interspersed nuclear elements (SINEs) offer strong evidence for scandentia belonging to the euarchonta group:

Order Scandentia
The 23 species are placed in four genera, which are divided into two families. The majority are in the "ordinary" treeshrew family, Tupaiidae, but one species, the pen-tailed treeshrew, is different enough to warrant placement in its own family, Ptilocercidae; the two families are thought to have separated 60 million years ago. The former Tupaiidae genus Urogale was disbanded in 2011 when the Mindanao treeshrew was moved to Tupaia based on a molecular phylogeny.

 * Family Tupaiidae:
 * Genus Anathana
 * Madras treeshrew, A. ellioti

 * Genus Dendrogale
 * Bornean smooth-tailed treeshrew, D. melanura
 * Northern smooth-tailed treeshrew, D. murina

 * Genus Tupaia
 * Northern treeshrew, T. belangeri
 * Golden-bellied treeshrew, T. chrysogaster
 * Bangka Island treeshrew, T. discolor
 * Striped treeshrew, T. dorsalis
 * Mindanao treeshrew, T. everetti
 * Sumatran treeshrew, T. ferruginea
 * Common treeshrew, T. glis
 * Slender treeshrew, T. gracilis
 * Javan treeshrew, T. hypochrysa
 * Horsfield's treeshrew, T. javanica
 * Long-footed treeshrew, T. longipes
 * Pygmy treeshrew, T. minor
 * Mountain treeshrew, T. montana
 * Nicobar treeshrew, T. nicobarica
 * Palawan treeshrew, T. palawanensis
 * Painted treeshrew, T. picta
 * Kalimantan treeshrew, T. salatana
 * Ruddy treeshrew, T. splendidula
 * Large treeshrew, T. tana

 * Family Ptilocercidae:
 * Genus Ptilocercus
 * Pen-tailed treeshrew, P. lowii

Fossil record
The fossil record of treeshrews is poor. The oldest putative treeshrew, Eodendrogale parva, is from the Middle Eocene of Henan, China, but the identity of this animal is uncertain. Other fossils have come from the Miocene of Thailand, Pakistan, India, and Yunnan, China, as well as the Pliocene of India. Most belong to the family Tupaiidae; one fossil species described from the Oligocene of Yunnan is thought to be closer to the pen-tailed treeshrew.

Named fossil species include Prodendrogale yunnanica, Prodendrogale engesseri, and Tupaia storchi from Yunnan, Tupaia miocenica from Thailand, Palaeotupaia sivalicus from India and Ptilocercus kylin from Yunnan.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Treeshrew


text: Talk:Imagine (song)

title: Talk:Imagine (song)


text:
Free good

A free good is a good that is not scarce, and therefore is available without limit. A free good is available in as great a quantity as desired with zero opportunity cost to society.

A good that is made available at zero price is not necessarily a free good. For example, a shop might give away its stock in its promotion, but producing these goods would still have required the use of scarce resources.

Examples of free goods are ideas and works that are reproducible at zero cost, or almost zero cost. For example, if someone invents a new device, many people could copy this invention, with no danger of this "resource" running out.

Earlier schools of economic thought stated that resources that are enough for everyone to have as much as they want are free goods. Examples in textbooks included seawater and air.

Intellectual property laws such as copyrights and patents have the effect of converting some intangible goods to scarce goods. Even though these works are free goods by definition and can be reproduced at minimal cost, the production of these works does require scarce resources, such as skilled labour. Thus these laws are used to give exclusive rights to the creators, in order to encourage resources to be appropriately allocated to these activities.

Many post scarcity futurists theorize that advanced nanotechnology with the ability to turn any kind of material automatically into any other combination of equal mass will make all goods essentially free goods, since all raw materials and manufacturing time will become perfectly interchangeable.

title: Free good


text:
User:The Ostrich

The Ostrich is at this time an independent developer creating puzzles programs (sudoku, killer sudoku, hashi, crosswords, codewords) both for interactive play and for newspapers and magazines.

title: User:The Ostrich


text:
Seven deadly sins

The seven deadly sins are also known as the capital vices or cardinal sins and function as a grouping and classification of major vices within the teachings in Christianity and Islam. According to the standard list, the seven deadly sins in Christianity are pride, greed, wrath, envy, lust, gluttony and sloth. In Islam these are shirk, witchcraft, usury, disrespect of parents, fornication, unjust accusation against women and unjust murder. Generally, when it comes to the seven deadly sins, the emphasis is predominant on the idea of an afterlife of the human soul in heaven or hell, depending on the choices of the individual during his or her life. According to Christian belief, deadly sins are generally those that lead to a (mortal) afterlife in hell. Over time, there was some variation as to the actual number of deadly sins, but seven became the norm. For Islam, the sins mentioned above are the only sins which if the person dies without repenting will necessarily go to hell either permanently or temporarily.

In Christianity, the classification of deadly sins into a group of seven originated with Tertullian, and continued with Evagrius Ponticus. The concepts of the sins involved were in part based on Greco-Roman and Biblical antecedents. Later, the concept of seven deadly sins evolved further, based upon historical context based upon the Latin language of the Roman Catholic Church, though with a significant influence from the Greek language and associated religious traditions. Knowledge of the seven deadly sin concept is known through discussions in various treatises and also depictions in paintings and sculpture, for example architectural decorations on certain churches of certain Catholic parishes and also from certain older textbooks. Further information has been derived from patterns of confessions.

Subsequently, over the centuries into modern times, the idea of sins (especially seven in number) has permutated in various ways into the streams of religious and philosophical thought, fine art painting, and popular culture, including literature and new forms of media such as moving pictures and digital streaming.

Greco-Roman antecedents
Roman writers such as Horace extolled virtues, and they listed and warned against vices. His first epistles say that "to flee vice is the beginning of virtue and to have got rid of folly is the beginning of wisdom."

Origin of the currently recognized seven deadly sins
These "evil thoughts" can be categorized as follows:

 * physical (thoughts produced by the nutritive, sexual, and acquisitive appetites)
 * emotional (thoughts produced by depressive, irascible, or dismissive moods)
 * mental (thoughts produced by jealous/envious, boastful, or hubristic states of mind)

The fourth-century monk Evagrius Ponticus reduced the nine logismoi to eight, as follows:

 * 1) Γαστριμαργία  gluttony
 * 2) Πορνεία  prostitution, fornication
 * 3) Φιλαργυρία  greed
 * 4) Λύπη  sadness, rendered in the Philokalia as envy, sadness at another's good fortune
 * 5) Ὀργή  wrath
 * 6) Ἀκηδία  acedia, rendered in the Philokalia as dejection
 * 7) Κενοδοξία  boasting
 * 8) Ὑπερηφανία  pride, sometimes rendered as self-overestimation, arrogance, or grandiosity

Evagrius's list was translated into the Latin of Western Christianity in many writings of John Cassian, thus becoming part of the Western tradition's spiritual pietas or Catholic devotions as follows:
 * 1) Gula (gluttony)
 * 2) Luxuria/Fornicatio (lust, fornication)
 * 3) Avaritia (greed)
 * 4) Tristitia (sorrow/despair/despondency)
 * 5) Ira (wrath)
 * 6) Acedia (sloth)
 * 7) Vanagloria (vainglory)
 * 8) Superbia (pride, hubris)

In AD 590, Pope Gregory I revised the list to form a more common list. Gregory combined tristitia with acedia and vanagloria with superbia, adding envy, which is invidia in Latin. (It is interesting to note that Pope Gregory's list corresponds exactly to the traits described in Pirkei Avot as "removing one from the world." See Pirkei Avot 2:16, 3:14, 4:28 and the Vilna Gaon's commentary to Aggadot Berakhot 4b.) Thomas Aquinas uses and defends Gregory's list in his Summa Theologica, although he calls them the "capital sins" because they are the head and form of all the other sins. Christian denominations, such as the Anglican Communion, Lutheran Church, and Methodist Church, still retain this list, and modern evangelists such as Billy Graham have explicated the seven deadly sins.

Historical and modern definitions, views, and associations
According to Catholic prelate Henry Edward Manning, the seven deadly sins are seven ways of eternal death. The Lutheran divine Martin Chemnitz, who contributed to the development of Lutheran systematic theology, implored clergy to remind the faithful of the seven deadly sins.

Listed in order of increasing severity as per Pope Gregory I, 6th-century A.D., the seven deadly sins are as follows:

Lust
Lust or lechery (luxuria "(sexual) excess/dissipation") is intense longing. It is usually thought of as intense or unbridled sexual desire, which may lead to fornication (including adultery), rape, bestiality, and other sinful and sexual acts; oftentimes, however, it can also mean other forms of unbridled desire, such as for money, or power. Henry Edward Manning explains that the impurity of lust transforms one into "a slave of the devil".

Lust is generally thought to be the least serious capital sin. Thomas Aquinas considers it an abuse of a faculty that humans share with animals and sins of the flesh are less grievous than spiritual sins.

Gluttony

Gluttony (gula) is the overindulgence and overconsumption of anything to the point of waste. The word derives from the Latin gluttire, meaning to gulp down or swallow. One reason for its condemnation is that the gorging of the prosperous may leave the needy hungry.

Medieval church leaders such as Thomas Aquinas took a more expansive view of gluttony, arguing that it could also include an obsessive anticipation of meals and overindulgence in delicacies and costly foods. Aquinas also listed five forms of gluttony:

 * Laute – eating too expensively
 * Studiose – eating too daintily
 * Nimis – eating too much
 * Praepropere – eating too soon
 * Ardenter – eating too eagerly

Greed
In the words of Henry Edward Manning, avarice "plunges a man deep into the mire of this world, so that he makes it to be his god".

As defined outside Christian writings, greed is an inordinate desire to acquire or possess more than one needs, especially with respect to material wealth. Aquinas considers that, like pride, it can lead to evil.

Sloth
Sloth (tristitia, or acedia "without care") refers to a peculiar jumble of notions, dating from antiquity and including mental, spiritual, pathological, and physical states. It may be defined as absence of interest or habitual disinclination to exertion.

In his Summa Theologica, Saint Thomas Aquinas defined sloth as "sorrow about spiritual good".

The scope of sloth is wide. Spiritually, acedia first referred to an affliction attending religious persons, especially monks, wherein they became indifferent to their duties and obligations to God. Mentally, acedia has a number of distinctive components; the most important of these is affectlessness, a lack of any feeling about self or other, a mind-state that gives rise to boredom, rancor, apathy, and a passive inert or sluggish mentation. Physically, acedia is fundamentally associated with a cessation of motion and an indifference to work; it finds expression in laziness, idleness, and indolence.

Sloth includes ceasing to utilize the seven gifts of grace given by the Holy Spirit (Wisdom, Understanding, Counsel, Knowledge, Piety, Fortitude, and Fear of the Lord); such disregard may lead to the slowing of spiritual progress towards eternal life, the neglect of manifold duties of charity towards the neighbor, and animosity towards those who love God.

Unlike the other seven deadly sins, which are sins of committing immorality, sloth is a sin of omitting responsibilities. It may arise from any of the other capital vices; for example, a son may omit his duty to his father through anger. The state and habit of sloth is a mortal sin, while the habit of the soul tending towards the last mortal state of sloth is not mortal in and of itself except under certain circumstances.

Emotionally, and cognitively, the evil of acedia finds expression in a lack of any feeling for the world, for the people in it, or for the self. Acedia takes form as an alienation of the sentient self first from the world and then from itself. The most profound versions of this condition are found in a withdrawal from all forms of participation in or care for others or oneself, but a lesser yet more noisome element was also noted by theologians. Gregory the Great asserted that, "from tristitia, there arise malice, rancour, cowardice, [and] despair". Chaucer also dealt with this attribute of acedia, counting the characteristics of the sin to include despair, somnolence, idleness, tardiness, negligence, laziness, and wrawnesse, the last variously translated as "anger" or better as "peevishness". For Chaucer, human's sin consists of languishing and holding back, refusing to undertake works of goodness because, they tell themselves, the circumstances surrounding the establishment of good are too grievous and too difficult to suffer. Acedia in Chaucer's view is thus the enemy of every source and motive for work.

Sloth subverts the livelihood of the body, taking no care for its day-to-day provisions, and slows down the mind, halting its attention to matters of great importance. Sloth hinders the man in his righteous undertakings and thus becomes a terrible source of human's undoing.

Wrath
Wrath (ira) can be defined as uncontrolled feelings of anger, rage, and even hatred. Wrath often reveals itself in the wish to seek vengeance.

According to the Catechism of the Catholic Church, the neutral act of anger becomes the sin of wrath when it is directed against an innocent person, when it is unduly strong or long-lasting, or when it desires excessive punishment. "If anger reaches the point of a deliberate desire to kill or seriously wound a neighbor, it is gravely against charity; it is a mortal sin." (CCC 2302) Hatred is the sin of desiring that someone else may suffer misfortune or evil and is a mortal sin when one desires grave harm (CCC 2302–03).

People feel angry when they sense that they or someone they care about has been offended, when they are certain about the nature and cause of the angering event, when they are certain someone else is responsible, and when they feel that they can still influence the situation or cope with it.

Henry Edward Manning considers that "angry people are slaves to themselves".

Envy
Envy (invidia) is characterized by an insatiable desire like greed and lust. It can be described as a sad or resentful covetousness towards the traits or possessions of someone else. It comes from vainglory and severs a man from his neighbor.

According to St. Thomas Aquinas, the struggle aroused by envy has three stages: during the first stage, the envious person attempts to lower another's reputation; in the middle stage, the envious person receives either "joy at another's misfortune" (if he succeeds in defaming the other person) or "grief at another's prosperity" (if he fails); and the third stage is hatred because "sorrow causes hatred".

Bertrand Russell said that envy was one of the most potent causes of unhappiness, bringing sorrow to committers of envy, while giving them the urge to inflict pain upon others.

Pride
Pride (superbia), also known as hubris (from Ancient Greek ) or futility. It is considered the original and worst of the seven deadly sins on almost every list, the most demonic. It is also thought to be the source of the other capital sins. Pride is the opposite of humility.

Pride has been labeled the mother of all sins and has been deemed the devil's most essential trait. C. S. Lewis writes in Mere Christianity that pride is the "anti-God" state, the position in which the ego and the self are directly opposed to God: "Unchastity, anger, greed, drunkenness and all that, are mere fleabites in comparison: it was through Pride that the devil became the devil: Pride leads to every other vice: it is the complete anti-God state of mind." Pride is understood to sever the spirit from God, as well as His life-and-grace-giving Presence.

One can be prideful for different reasons. Author Ichabod Spencer states that "spiritual pride is the worst kind of pride, if not worst snare of the devil. The heart is particularly deceitful on this one thing." Jonathan Edwards said: "remember that pride is the worst viper that is in the heart, the greatest disturber of the soul's peace and sweet communion with Christ; it was the first sin that ever was and lies lowest in the foundation of Satan's whole building and is the most difficultly rooted out and is the most hidden, secret and deceitful of all lusts and often creeps in, insensibly, into the midst of religion and sometimes under the disguise of humility."

The modern use of pride may be summed up in the biblical proverb, "Pride goeth before destruction, a haughty spirit before a fall" (abbreviated "Pride goeth before a fall", Proverbs 16:18). The "pride that blinds" causes foolish actions against common sense. In political analysis, "hubris" is often used to describe how leaders with great power over many years become more and more irrationally self-confident and contemptuous of advice, leading them to act impulsively.

Throughout history, artists have found inspiration in the timeless themes of morality and human nature, and the seven deadly sins have been a particularly fertile subject for exploration. These sins, traditionally categorized as pride, envy, wrath, sloth, avarice, gluttony, and lust, have been depicted in a variety of ways, from allegorical representations to satirical observations of human behavior.

One of the most notable artists to tackle this subject was Pieter Bruegel the Elder, a Flemish painter of the Renaissance. His 1557 series of woodcuts, known as the "Seven Deadly Sins", vividly captures the essence of each sin through a series of grotesque and comical scenes. In "Sloth", a group of slovenly individuals sleep soundly, oblivious to the world around them. "Avarice" depicts a miser counting his coins with a miserly expression, while "Gluttony" shows a gluttonous man consuming an enormous meal, oblivious to his surroundings.

Other notable artists who have explored the seven deadly sins include:

 * Lucas Cranach the Elder: German painter of the Renaissance, known for his religious paintings and sensual portraits. His portrayals of Adam and Eve often emphasize their nakedness and vulnerability, reflecting the concept of lust.
 * Peter Paul Rubens: Flemish painter of the Baroque period, known for his dynamic compositions and vibrant colors. His painting "The Wrath of Achilles" depicts the Greek hero in a rage, his face contorted in anger as he prepares to slay a Trojan prisoner.
 * William Hogarth: English painter and printmaker of the 18th century, known for his satirical social commentary. His series of paintings "Marriage A-la-Mode" satirizes the follies and vices of the upper classes, with each panel depicting a different stage of a marriage that eventually ends in ruin.
 * Paul Cadmus: American painter of the 20th century, known for his social realist paintings. His series of paintings "The Seven Deadly Sins" depicts the sins in a more contemporary setting, using exaggerated figures and satirical humor to critique modern society.
 * Chris Ofili: British painter of the 21st century, known for his use of unconventional materials such as elephant dung and glitter. His series of paintings "The Seven Deadly Sins" utilizes these materials to create a visually striking and often disturbing depiction of the sins.
 * Yves Decadt: a Flemish artist, has created a series of artworks titled "Falling Angels: Allegories about the 7 Sins and 7 Virtues for Falling Angels and other Curious Minds". The series explores the topic of morality, sins, and virtues, which have dominated Western cultures for more than 2000 years. In this work, Decadt follows in the footsteps of Pieter Breughel, who made a series of sketches on the 7 sins and 7 virtues about 500 years ago. The work takes the viewer on an adventurous trip through time and across the barriers and edges of reality, mythology, religion, and culture.

Acedia
Acedia (Latin, acedia "without care"; from Greek ἀκηδία) is the neglect to take care of something that one should do. It is translated to apathetic listlessness; depression without joy. It is related to melancholy; acedia describes the behaviour and melancholy suggests the emotion producing it. In early Christian thought, the lack of joy was regarded as a willful refusal to enjoy the goodness of God. By contrast, apathy was considered a refusal to help others in times of need.

Acēdia is the negative form of the Greek term κηδεία, which has a more restricted usage. "Kēdeia" refers specifically to spousal love and respect for the dead.

Pope Gregory combined this with tristitia into sloth for his list. When Thomas Aquinas described acedia in his interpretation of the list, he described it as an "uneasiness of the mind", being a progenitor for lesser sins such as restlessness and instability.

Acedia is currently defined in the Catechism of the Catholic Church as spiritual sloth, believing spiritual tasks to be too difficult. In the fourth century, Christian monks believed that acedia was primarily caused by a state of melancholia that caused spiritual detachment instead of laziness.

Vainglory
Vainglory (Latin, vanagloria) is unjustified boasting. Pope Gregory viewed it as a form of pride, so he folded vainglory into pride for his listing of sins. According to Aquinas, it is the progenitor of envy.

The Latin term gloria roughly means boasting, although its English cognate glory has come to have an exclusively positive meaning. Historically, the term vain roughly meant futile (a meaning retained in the modern expression "in vain"), but by the fourteenth century had come to have the strong narcissistic undertones which it still retains today.

Confession patterns
According to a 2009 study by the Jesuit scholar Fr. Roberto Busa, the most common deadly sin confessed by men is lust and the most common deadly sin confessed by women is pride. It was unclear whether these differences were due to the actual number of transgressions committed by each sex or whether differing views on what "counts" or should be confessed caused the observed pattern.

title: Seven deadly sins


text:
User:Firepink

firepink is an over-educated over-30 female from Columbus, Ohio. I chose the nickname because (1) I love wildflowers and (2) "fire" and "pink" seem to be nearly antonyms...which is true of my changing moods.

Interests:
 * wildflowers and nature
 * reading (esp. mysteries, e.g. Dorothy Sayers)
 * cats (I have a twenty-pounder)
 * puzzles (crossword, logic, & jigsaw)
 * collecting teapots and stamps

Sorry if my initial entries weren't Wikified... I'm still learning! It's also hard sometimes for me to stay NPOV...I tend to get a bit over-enthusiastic sometimes!

Ever since the big change-over, I haven't been able to stay logged in. Still trying to fix this without adding cookies. I added "wikipedia.com" to a list of "trusted sites" that WILL accept cookies...but it's not working yet!!

title: User:Firepink


text:
Toltec

The Toltec culture was a pre-Columbian Mesoamerican culture that ruled a state centered in Tula, Hidalgo, Mexico, during the Epiclassic and the early Post-Classic period of Mesoamerican chronology, reaching prominence from 950 to 1150 CE. The later Aztec culture considered the Toltec to be their intellectual and cultural predecessors and described Toltec culture emanating from Tōllān (Nahuatl for Tula) as the epitome of civilization. In the Nahuatl language the word Tōltēkatl (singular) or Tōltēkah  (plural) came to take on the meaning "artisan". The Aztec oral and pictographic tradition also described the history of the Toltec Empire, giving lists of rulers and their exploits.

Modern scholars debate whether the Aztec narratives of Toltec history should be given credence as descriptions of actual historical events. While all scholars acknowledge that there is a large mythological part of the narrative, some maintain that, by using a critical comparative method, some level of historicity can be salvaged from the sources. Others maintain that continued analysis of the narratives as sources of factual history is futile and hinders access to learning about the culture of Tula.

Other controversies relating to the Toltec include the question of how best to understand the reasons behind the perceived similarities in architecture and iconography between the archaeological site of Tula and the Maya site of Chichén Itzá. Researchers are yet to reach a consensus in regards to the degree or direction of influence between these two sites.

Origins of society at Tula
While the exact origins of the culture are unclear, it likely developed from a mixture of the Nonoalca people from the southern Gulf Coast and a group of sedentary Chichimeca from northern Mesoamerica. The former of these is believed to have composed the majority of the new culture and were influenced by the Mayan culture. During Teotihuacan's apogee in the Early Classic period, these people were tightly integrated into the political and economic systems of the state and formed large settlements in the Tula region, most notably Villagran and Chingu.

Beginning around 650 CE, the majority of these settlements were abandoned as a result of Teotihuacan's decline. The Coyotlatelco rose as the dominant culture in the region. It is with the Coyotlatelco that Tula, as it relates to the Toltec, was founded along with a number of hilltop communities.

Tula Chico, as the settlement is referred to during this phase, grew into a small regional state out of the consolidation of the surrounding Coyotlatelco sites. The settlement was roughly three to six square kilometers in size with a gridded urban plan and a relatively large population. The complexity of the main plaza was especially distinct from other Coyotlatelco sites in the area, as it had multiple ball courts and pyramids. The Toltec culture, as it is understood during its peak, can be tied directly to Tula Chico; after the site was burned and abandoned at the end of the Epiclassic period, Tula Grande was soon constructed bearing strong similarities 1.5 kilometers to the south. It is during the Early Postclassic period that Tula Grande and its associated Toltec culture would become the dominant force in the broader region.

Archaeology

Some archaeologists, such as Richard Diehl, argue for the existence of a Toltec archaeological horizon characterized by certain stylistic traits associated with Tula, Hidalgo and extending to other cultures and polities in Mesoamerica. Traits associated with this horizon are include the Mixtec-Puebla style of iconography, Tohil plumbate ceramic ware, and Silho or X-Fine Orange Ware ceramics. The presence of stylistic traits associated with Tula in Chichén Itzá is also taken as evidence for a Toltec horizon. The nature of interaction between Tula and Chichén Itzá has been especially controversial, with scholars arguing for either military conquest of Chichén Itzá by the Toltec, Chichén Itzá establishing Tula as a colony, or only loose connections between the two. Whether the Mixteca-Puebla art style has any meaning is also disputed.

A contrary viewpoint is argued in a 2003 study by Michael E. Smith and Lisa Montiel, who compare the archaeological record related to Tula Hidalgo to those of the polities centered in Teotihuacan and Tenochtitlan. They conclude that relative to the influence exerted in Mesoamerica by Teotihuacan and Tenochtitlan, Tula's influence on other cultures was negligible and was probably not deserving of being defined as an empire, but more of a kingdom. While Tula does have the urban complexity expected of an imperial capital, its influence and dominance were not very far reaching. Evidence for Tula's participation in extensive trade networks has been uncovered; for example, the remains of a large obsidian workshop.

Material culture at Tula Grande
At its height, Tula Grande had an estimated population of as many as 60,000 and covered 16 square kilometers of hills, plains, valleys, and marsh. Some of the most prominent examples of the Toltec material culture at the site include pyramids, ball-courts, and the Atlantean warrior sculptures on top of Pyramid B. Various civic buildings surrounding a central plaza are especially distinctive, as excavations show the use of columns inside these buildings and in surrounding colonnades. One of these buildings, known as Building 3, is argued to have been a symbolically powerful building for the Toltec due to its reference in architecture to the historic and mythic homes of the people's ancestors.

The physical layout of the broader plaza also partakes in referencing a shared past; its sunken colonnaded hall units are incredibly similar to those at cities of Tula's ancestral peoples. Importantly, these halls are known to have served as places to engage with both regional and long-distance trade networks and were possibly also used for diplomatic relations, suggesting that Tula Grande used these structures for a similar end. To that point, imported goods at Tula Grande shows that the Toltecs indeed interacted commercially with sites throughout Mesoamerica; shared ceramic and ritual figurine styles between Tula and regions such as Socunusco supplement this idea.

Additionally, surveys of Tula Grande have suggested the existence of an "extensive and highly specialized workshop-based obsidian industry," at the site that could have been one of the sources of the city's economic and political power, taking on Teotihuacan's previous role as the region's distributor. A survey done by Healan et al. recovered roughly 16,000 pieces of obsidian from the site's urban zone and over 25,000 from its surrounding residential areas. Tula's involvement in obsidian trade is also evidence for the city's interaction with another powerful city in the region, Chichén Itzá, as the vast majority of obsidian at both sites comes from the same two geological sources.

History of research
One of the earliest historical mentions of Toltecs was in the 16th century by the Dominican friar Diego Durán, who was best known for being one of the first westerners to study the history of Mesoamerica. Durán's work remains relevant to Mesoamerican societies, and based on his findings Durán claims that the Toltecs were disciples of the "High Priest Topiltzin." Topiltzin and his disciples were said to have preached and performed miracles. "Astonished, the people called these men Toltecs," which Duran says, "means Masters, or Men Wise in Some Craft." Duran speculated that this Topilzin may have been the Thomas the Apostle sent to preach the Christian Gospel among the "Indians", although he provides nothing more than circumstantial evidence of any contact between the hemispheres.

The later debate about the nature of the Toltec culture goes back to the late 19th century. Mesoamericanist scholars such as Mariano Veytia, Manuel Orozco y Berra, Charles Etienne Brasseur de Bourbourg, and Francisco Clavigero all read the Aztec chronicles and believed them to be realistic historic descriptions of a pan-Mesoamerican empire based at Tula, Hidalgo. This historicist view was first challenged by Daniel Garrison Brinton who argued that the "Toltecs" as described in the Aztec sources were merely one of several Nahuatl-speaking city-states in the Postclassic period, and not a particularly influential one at that. He attributed the Aztec view of the Toltecs to the "tendency of the human mind to glorify the good old days" and the confounding of the place of Tollan with the myth of the struggle between Quetzalcoatl and Tezcatlipoca. Désiré Charnay, the first archaeologist to work at Tula, Hidalgo, defended the historicist views based on his impression of the Toltec capital, and was the first to note similarities in architectural styles between Tula and Chichén Itza. This led him to posit the theory that Chichén Itzá had been violently taken over by a Toltec military force under the leadership of Kukulcan. Following Charnay the term Toltec has since been associated with the influx of certain Central Mexican cultural traits into the Maya sphere of dominance that took place in the late Classic and early Postclassic periods; the Postclassic Mayan civilizations of Chichén Itzá, Mayapán and the Guatemalan highlands have been referred to as "Toltecized" or "Mexicanized" Mayas.

The historicist school of thought persisted well into the 20th century, represented in the works of scholars such as David Carrasco, Miguel León-Portilla, Nigel Davies and H. B. Nicholson, which all held the Toltecs to have been an actual ethnic group. This school of thought connected the "Toltecs" to the archaeological site of Tula, which was taken to be the Tollan of Aztec myth. This tradition assumes that much of central Mexico was dominated by a Toltec Empire between the 10th and 12th century AD. The Aztecs referred to several Mexican city states as Tollan, "Place of Reeds", such as "Tollan Cholollan". Archaeologist Laurette Séjourné, followed by the historian Enrique Florescano, have argued that the "original" Tollan was probably Teotihuacán. Florescano adds that the Mayan sources refer to Chichén Itzá when talking about the mythical place Zuyua (Tollan).

Many historicists such as H. B. Nicholson (2001 (1957)) and Nigel Davies (1977) were fully aware that the Aztec chronicles were a mixture of mythical and historical accounts; this led them to try to separate the two by applying a comparative approach to the varying Aztec narratives. For example, they seek to discern between the deity Quetzalcoatl and a Toltec ruler often referred to as Topiltzin Ce Acatl Quetzalcoatl.

Toltecs as myth

Since the 1990s, the historicist position has fallen out of favor for a more critical and interpretive approach to the historicity of the Aztec mythical accounts based on the original approach of Brinton. This approach applies a different understanding of the word Toltec to the interpretation of the Aztec sources, interpreting it as largely a mythical and philosophical construct by either the Aztecs or Mesoamericans generally that served to symbolize the might and sophistication of several civilizations during the Mesoamerican Postclassic period. The Nahuatl word for 'Toltec', for example, can mean 'master artisan' as well as 'inhabitant of Tula, Hidalgo', and the word Tollan (known as Tula in modern times) can refer specifically to Tula, Hidalgo, or more generally to all great cities through meaning 'place of the reeds'.

Much of the questioning of these Aztec narratives is due to the lack of archaeological evidence to support them. Aztec accounts tell that the Toltec discovered medicine, designed the calendar system, created the Nahuatl language. More broadly, the Aztec traced most of their own societal achievements to the Toltec and their city Tollan, which was idolized as the epitome of state civilization with an enormous influence in the surrounding region. However, Tula—the site attributed with this Tollan—lacks much of the splendor that the Aztecs describe. For example, Tula was mainly built out of the relatively soft and unimpressive adobe brick, and while Tula certainly was a major regional city in its time, it was minuscule both in population and in influence in comparison to both its predecessor, Teotihuacan, and its Aztec descendant, Tenochtitlan. Additional material remains at Tula, such as the destruction of Toltec buildings and monumental art coinciding with the arrival of Aztec ceramics, suggest that the Aztecs' reverence of the Toltec might have been mostly propagandistic, intentionally overexaggerating the previous culture to use it as a steppingstone for their own.

Scholars such as Michel Graulich (2002) and Susan D. Gillespie (1989) maintained that the difficulties in salvaging historic data from the Aztec accounts of Toltec history are too great to overcome. For example, there are two supposed Toltec rulers identified with Quetzalcoatl: the first ruler and founder of the Toltec dynasty and the last ruler, who saw the end of the Toltec glory and was forced into humiliation and exile. The first is described as a valiant triumphant warrior, but the last as a feeble and self-doubting old man. This caused Graulich and Gillespie to suggest that the general Aztec cyclical view of time, in which events repeated themselves at the end and beginning of cycles or eras was being inscribed into the historical record by the Aztecs, making it futile to attempt to distinguish between a historical Topiltzin Ce Acatl and a Quetzalcoatl deity. Graulich argued that the Toltec era is best considered the fourth of the five Aztec mythical "Suns" or ages, the one immediately preceding the fifth Sun of the Aztec people, presided over by Quetzalcoatl. This caused Graulich to consider that the only possibly historical data in the Aztec chronicles are the names of some rulers and possibly some of the conquests ascribed to them.

Furthermore, among the Nahuan peoples the word Tolteca was synonymous with artist, artisan or wise man, and Toltecayotl, literally 'Toltecness', meant art, culture, civilization, and urbanism and was seen as the opposite of Chichimecayotl ('Chichimecness'), which symbolized the savage, nomadic state of peoples who had not yet become urbanized. This interpretation argues that any large urban center in Mesoamerica could be referred to as Tollan and its inhabitants as Toltecs – and that it was a common practice among ruling lineages in Postclassic Mesoamerica to strengthen claims to power by asserting Toltec ancestry. Mesoamerican migration accounts often state that Tollan was ruled by Quetzalcoatl (or Kukulkan in Yucatec and Q'uq'umatz in Kʼicheʼ), a godlike mythical figure who was later sent into exile from Tollan and went on to found a new city elsewhere in Mesoamerica. According to Patricia Anawalt, a professor of anthropology at UCLA, assertions of Toltec ancestry and claims that their elite ruling dynasties were founded by Quetzalcoatl have been made by such diverse civilizations as the Aztec, the Kʼicheʼ and the Itza' Mayas.

While the skeptical school of thought does not deny that cultural traits of a seemingly central Mexican origin have diffused into a larger area of Mesoamerica, it tends to ascribe this to the dominance of Teotihuacán in the Classic period and the general diffusion of cultural traits within the region. Recent scholarship, then, does not see Tula, Hidalgo as the capital of the Toltecs of the Aztec accounts. Rather, it takes Toltec to mean simply an inhabitant of Tula during its apogee. Separating the term Toltec from those of the Aztec accounts, it attempts to find archaeological clues to the ethnicity, history and social organization of the inhabitants of Tula.

title: Toltec


text:
Talk:Free good

I'm not happy with the classification here: is this really how free goods are classified in some particular economics text, and if so, which text? I'm sure there are other ways they could be classified, and this article ought to reflect a real academic consensus, or at least accurately describe the different academic views. --Lee Daniel Crocker

 * What is/are the other classifications? -- Sam

 * In deciding whether to classify reclaimed waste products as a free good, would the cost of recycling or reusing be a factor? I think there are some cases where sending a product to the landfill or other disposal facility is cheaper than the recycling costs, at least in terms of immediate cash expenditure. Wesley

 * Recycling, really, is a production process (or a re-production process, if you like; though that wouldn't be the right word..). It incurs costs, and so is not a free good. Even if there was no need to recycle, the process of production would incur costs (even if that process is one of consumption).

 * However, the recycling of air, for example, is a free process (until we kill all the trees). So air is usually considered a free good; it incurs no cost to the supplier. (But I could be wrong.) -- Sam

title: Talk:Free good


text:
Pseudorandom number generator

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed.

Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."

Potential issues
In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical pattern-detection tests. These include:

 * Shorter-than-expected periods for some seed states (such seed states may be called "weak" in this context);
 * Lack of uniformity of distribution for large quantities of generated numbers;
 * Correlation of successive values;
 * Poor dimensional distribution of the output sequence;
 * Distances between where certain values occur are distributed differently from those in a random sequence distribution.

Defects exhibited by flawed PRNGs range from unnoticeable (and unknown) to very obvious. An example was the RANDU random number algorithm used for decades on mainframe computers. It was seriously flawed, but its inadequacy went undetected for a very long time.

In many fields, research work prior to the 21st century that relied on random selection or on Monte Carlo simulations, or in other ways relied on PRNGs, were much less reliable than ideal as a result of using poor-quality PRNGs. Even today, caution is sometimes required, as illustrated by the following warning in the International Encyclopedia of Statistical Science (2010).

As an illustration, consider the widely used programming language Java. Up until 2020, Java still relied on a linear congruential generator (LCG) for its PRNG, which is of low quality (see further below). Java support was upgraded with Java 17.

One well-known PRNG to avoid major problems and still run fairly quickly is the Mersenne Twister (discussed below), which was published in 1998. Other higher-quality PRNGs, both in terms of computational and statistical performance, were developed before and after this date; these can be identified in the List of pseudorandom number generators.

Generators based on linear recurrences
In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators. The quality of LCGs was known to be inadequate, but better methods were unavailable. Press et al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist."

A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the two-element field; such generators are related to linear-feedback shift registers.

The 1997 invention of the Mersenne Twister, in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 219 937 − 1 iterations (≈ 4.3), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and at the time of its introduction was running faster than other statistically reasonable generators.

In 2003, George Marsaglia introduced the family of xorshift generators, again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests.

In 2006, the WELL family of generators was developed. The WELL generators in some ways improves on the quality of the Mersenne Twister, which has a too-large state space and a very slow recovery from state spaces with a large number of zeros.

Cryptographic PRNGs
A PRNG suitable for cryptographic applications is called a cryptographically-secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed. Though a proof of this property is beyond the current state of the art of computational complexity theory, strong evidence may be provided by reducing to the CSPRNG from a problem that is assumed to be hard, such as integer factorization. In general, years of review may be required before an algorithm can be certified as a CSPRNG.

Some classes of CSPRNGs include the following:

 * stream ciphers
 * block ciphers running in counter or output feedback mode
 * PRNGs that have been designed specifically to be cryptographically secure, such as Microsoft's Cryptographic Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X and FreeBSD), and Fortuna
 * combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any detectable non-randomness
 * special designs based on mathematical hardness assumptions: examples include the Micali–Schnorr generator, Naor-Reingold pseudorandom function and the Blum Blum Shub algorithm, which provide a strong security proof (such algorithms are rather slow compared to traditional constructions, and impractical for many applications)
 * generic PRNGs: while it has been shown that a (cryptographically) secure PRNG can be constructed generically from any one-way function, this generic construction is extremely slow in practice, so is mainly of theoretical interest.

It has been shown to be likely that the NSA has inserted an asymmetric backdoor into the NIST-certified pseudorandom number generator Dual_EC_DRBG.

Most PRNG algorithms produce sequences that are uniformly distributed by any of several tests. It is an open question, and one central to the theory and practice of cryptography, whether there is any way to distinguish the output of a high-quality PRNG from a truly random sequence. In this setting, the distinguisher knows that either the known PRNG algorithm was used (but not the state with which it was initialized) or a truly random algorithm was used, and has to distinguish between the two. The security of most cryptographic algorithms and protocols using PRNGs is based on the assumption that it is infeasible to distinguish use of a suitable PRNG from use of a truly random sequence. The simplest examples of this dependency are stream ciphers, which (most often) work by exclusive or-ing the plaintext of a message with the output of a PRNG, producing ciphertext. The design of cryptographically adequate PRNGs is extremely difficult because they must meet additional criteria. The size of its period is an important factor in the cryptographic suitability of a PRNG, but not the only one.

BSI evaluation criteria
The German Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik, BSI) has established four criteria for quality of deterministic random number generators. They are summarized here:

 * K1 – There should be a high probability that generated sequences of random numbers are different from each other.
 * K2 – A sequence of numbers is indistinguishable from "truly random" numbers according to specified statistical tests. The tests are the monobit test (equal numbers of ones and zeros in the sequence), poker test (a special instance of the chi-squared test), runs test (counts the frequency of runs of various lengths), longruns test (checks whether there exists any run of length 34 or greater in 20 000 bits of the sequence)—both from BSI and NIST, and the autocorrelation test. In essence, these requirements are a test of how well a bit sequence: has zeros and ones equally often; after a sequence of n zeros (or ones), the next bit a one (or zero) with probability one-half; and any selected subsequence contains no information about the next element(s) in the sequence.
 * K3 – It should be impossible for an attacker (for all practical purposes) to calculate, or otherwise guess, from any given subsequence, any previous or future values in the sequence, nor any inner state of the generator.
 * K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

For cryptographic applications, only generators meeting the K3 or K4 standards are acceptable.

Mathematical definition
Given:

 * $$P$$ – a probability distribution on $$\left(\mathbb{R},\mathfrak{B}\right)$$ (where $$\mathfrak{B}$$ is the standard Borel set on the real line)
 * $$\mathfrak{F}$$ – a non-empty collection of Borel sets $$\mathfrak{F}\subseteq\mathfrak{B}$$, e.g. $$\mathfrak{F}=\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}$$. If $$\mathfrak{F}$$ is not specified, it may be either $$\mathfrak{B}$$ or $$\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}$$, depending on context.
 * $$A\subseteq\mathbb{R}$$ – a non-empty set (not necessarily a Borel set). Often $$A$$ is a set between $$P$$'s support and its interior; for instance, if $$P$$ is the uniform distribution on the interval $$\left(0,1\right]$$, $$A$$ might be $$\left(0,1\right]$$. If $$A$$ is not specified, it is assumed to be some set contained in the support of $$P$$ and containing its interior, depending on context.

We call a function $$f:\mathbb{N}_1\rightarrow\mathbb{R}$$ (where $$\mathbb{N}_1=\left\{1,2,3,\dots\right\}$$ is the set of positive integers) a pseudo-random number generator for $$P$$ given $$\mathfrak{F}$$ taking values in $$A$$ if and only if:

 * $$f\left(\mathbb{N}_1\right)\subseteq A$$
 * $$\forall E\in\mathfrak{F} \quad \forall \varepsilon>0 \quad \exists N\in\mathbb{N}_1 \quad \forall n\geq N, \quad \left|\frac{\#\left\{i\in\left\{1,2,\dots, n\right\} : f(i)\in E\right\}}{n}-P(E)\right|< \varepsilon$$

($$\#S$$ denotes the number of elements in the finite set $$S$$.)

It can be shown that if $$f$$ is a pseudo-random number generator for the uniform distribution on $$\left(0,1\right)$$ and if $$F$$ is the CDF of some given probability distribution $$P$$, then $$F^*\circ f$$ is a pseudo-random number generator for $$P$$, where $$F^*:\left(0,1\right)\rightarrow\mathbb{R}$$ is the percentile of $$P$$, i.e. $$F^*(x):=\inf\left\{t\in\mathbb{R} : x\leq F(t)\right\}$$. Intuitively, an arbitrary distribution can be simulated from a simulation of the standard uniform distribution.

Early approaches
An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method. The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which can be written as "01234321", an 8-digit number being the square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on. Von Neumann used 10 digit numbers, but the process was the same.

A problem with the "middle square" method is that all sequences eventually repeat themselves, some very quickly, such as "0000". Von Neumann was aware of this, but he found the approach sufficient for his purposes and was worried that mathematical "fixes" would simply hide errors rather than remove them.

Von Neumann judged hardware random number generators unsuitable, for, if they did not record the output generated, they could not later be tested for errors. If they did record their output, they would exhaust the limited computer memories then available, and so the computer's ability to read and write numbers. If the numbers were written to cards, they would take very much longer to write and read. On the ENIAC computer he was using, the "middle square" method generated numbers at a rate some hundred times faster than reading numbers in from punched cards.

The middle-square method has since been supplanted by more elaborate generators.

A recent innovation is to combine the middle square with a Weyl sequence. This method produces high-quality output through a long period (see middle-square method).

Non-uniform generators
Numbers selected from a non-uniform probability distribution can be generated using a uniform distribution PRNG and a function that relates the two distributions.

First, one needs the cumulative distribution function $$F(b)$$ of the target distribution $$f(b)$$:

 * $$F(b)=\int_{-\infty}^b f(b') \, db'$$

Note that $$0=F(-\infty)\leq F(b) \leq F(\infty)=1$$. Using a random number c from a uniform distribution as the probability density to "pass by", we get

 * $$F(b)=c$$

so that

 * $$b=F^{-1}(c)$$

is a number randomly selected from distribution $$f(b)$$. This is based on the inverse transform sampling.

For example, the inverse of cumulative Gaussian distribution $$\operatorname{erf}^{-1}(x)$$ with an ideal uniform PRNG with range (0, 1) as input $$x$$ would produce a sequence of (positive only) values with a Gaussian distribution; however

 * When using practical number representations, the infinite "tails" of the distribution have to be truncated to finite values.
 * Repetitive recalculation of $$\operatorname{erf}^{-1}(x)$$ should be reduced by means such as ziggurat algorithm for faster generation.

Similar considerations apply to generating other non-uniform distributions such as Rayleigh and Poisson.

title: Pseudorandom number generator


text:
User:Enchanter

I'm 41 and live near London, England. My main interest is in economics, although I tend to absorb information on just about any subject, in particular history, mathematics, geography, psychology and languages.

I discovered Wikipedia in March 2002. I was really impressed with the amount of hard work going into it and the number of well informed people involved. At the time I thought the project had really great potential to grow ever faster as more people are attracted to it. It's been fantastic to watch what once seemed like a crazy vision become the reality of the huge encyclopedia we have here today.

title: User:Enchanter