共查询到20条相似文献,搜索用时 31 毫秒
1.
Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length Cn of the longest carry chain satisfies Cn = log2n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for Cn. Third, we give an elementary derivation of an asymptotic formula due to Knuth, Cn = log2n + Φ(log2 n) + O((logn)4/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance Vn of the length of the longest carry chain: Vn = Ψ(log2 n) + O((logn)5/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues. 相似文献
2.
David Paget 《Journal of Approximation Theory》1988,54(3)
Let f ε Cn+1[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials qk associated with a distribution dα on [−1, 1]. It is shown that if qn+1/qn max(qn+1(1)/qn(1), −qn+1(−1)/qn(−1)), then f − H[f] fn + 1 · qn+1/qn + 1(n + 1), where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)α (1 + t)β dt, α, β > −1, the condition on qn+1/qn is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2. 相似文献
3.
Yu. N. Skiba 《Journal of Mathematical Analysis and Applications》2004,290(2):686-701
Stability of the Rossby–Haurwitz (RH) wave of subspace H1Hn in an ideal incompressible fluid on a rotating sphere is analytically studied (Hn is the subspace of homogeneous spherical polynomials of degree n). It is shown that any perturbation of the RH wave evolves in such a way that its energy K(t) and enstrophy η(t) decrease, remain constant or increase simultaneously. A geometric interpretation of variations in the perturbation energy is given. A conservation law for arbitrary perturbations is obtained and used to classify all the RH-wave perturbations in four invariant sets M−n, M+n, Hn and M0n−Hn depending on the value of their mean spectral number χ(t)=η(t)/K(t). The energy cascade of growing (or decaying) perturbations has opposite directions in the sets M−n and M+n due to a hyperbolic dependence between K(t) and χ(t). A factor space with a factor norm of the perturbations is introduced using the invariant subspace Hn of neutral perturbations as the zero factor class. While the energy norm controls the perturbation part belonging to Hn, the factor norm controls the perturbation part orthogonal to Hn. It is shown that in the set M−n (χ(t)<n(n+1)), any nonzonal RH wave of subspace H1Hn (n2) is Liapunov unstable in the energy norm. This instability has nothing in common with the orbital (Poincaré) instability and is caused by asynchronous oscillations of two almost coinciding RH-wave solutions. It is also shown that the exponential instability is possible only in the invariant set M0n−Hn. A necessary condition for this instability is given. The condition states that the spectral number χ(t) of the amplitude of each unstable mode must be equal to n(n+1), where n is the RH-wave degree. The growth rate is estimated and the orthogonality of the unstable normal modes to the RH wave is shown. The instability in the invariant set M+n of small-scale perturbations (χ(t)>n(n+1)) is still open problem. 相似文献
4.
The number Nn of non-crossing trees of size n satisfies Nn+1=Tn where Tn enumerates ternary trees of size n. We construct a new bijection to establish that fact. Since
, it follows that 3(3n−1)(3n−2)Tn−1=2n(2n+1)Tn. We construct two bijections “explaining” this recursion; one of them easily extends to the case of t-ary trees. 相似文献
5.
Let Xn, n
, be i.i.d. with mean 0, variance 1, and E(¦Xn¦r) < ∞ for some r 3. Assume that Cramér's condition is fulfilled. We prove that the conditional probabilities P(1/√n Σi = 1n Xi t¦B) can be approximated by a modified Edgeworth expansion up to order o(1/n(r − 2)/2)), if the distances of the set B from the σ-fields σ(X1, …, Xn) are of order O(1/n(r − 2)/2)(lg n)β), where β < −(r − 2)/2 for r
and β < −r/2 for r
. An example shows that if we replace β < −(r − 2)/2 by β = −(r − 2)/2 for r
(β < −r/2 by β = −r/2 for r
) we can only obtain the approximation order O(1/n(r − 2)/2)) for r
(O(lg lgn/n(r − 2)/2)) for r
). 相似文献
6.
M. A. Botto 《Journal of Approximation Theory》1976,16(4):347-365
We investigate two sequences of polynomial operators, H2n − 2(A1,f; x) and H2n − 3(A2,f; x), of degrees 2n − 2 and 2n − 3, respectively, defined by interpolatory conditions similar to those of the classical Hermite-Féjer interpolators H2n − 1(f, x). If H2n − 2(A1,f; x) and H2n − 3(A2,f; x) are based on the zeros of the jacobi polynomials Pn(α,β)(x), their convergence behaviour is similar to that of H2n − 1(f;, x). If they are based on the zeros of (1 − x2)Tn − 2(x), their convergence behaviour is better, in some sense, than that of H2n − 1(f, x). 相似文献
7.
Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D0(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q0(n) to be the minimum of D0(G) over all graphs G of order n.We prove that for all n we have
log*n−log*log*n−2≤q0(n)≤log*n+22,