What properties should a supercomputer have that is particularly fast? How should its memory be structured? To what extent does it differ from conventional computer architectures? How can this be illustrated using the examples of basic arithmetic operations and matrix multiplication?

In the following, a bit length of 64 is used for calculation. In practice, however, this can be higher. The basis are i. a. particularly fast counting lines that are used bit by bit for addition. A counting line is run through e. g. of particles such as photons or electrons in a suitable medium, which is not important here, since only the theoretical concept is described. These count the number of set bits of equal value from several adjacent binary numbers.

The decisive factor is the high speed of the particles. The 64 numbers per bit are again stored as binary numbers and added (bitwise shifted). Since this happens in parallel, an addition speed of \(2^{32}\) binary numbers with bit length 32 is achieved in \(\mathcal{O}(1)\). Subtractions are implemented using the two's complement. Continued addition enables multiplication and, via forming the inverse, division. A hierarchical memory enables quick comparisons (see Radio Computing).

For fast multiplication of two wlog. square matrices, each with \(2^n\) entries for \(n \in {}^{\nu}\mathbb{N}\), these are written into a memory ball by simultaneous replication (i. e. simultaneous sending and storing). The multiplication in \(\mathcal{O}(1)\) takes place in its nodes, in which both entries of one matrix are stored. Then the entries of a row are added in parallel in \(\mathcal{O}(1)\) as described above via counting lines, which calculates the result matrix.

Here, the root is in the innermost shell, its leaves in the next outer shell, etc. The shells are rotatably mounted to prevent the innermost nodes from being fret or overused. The contacts (pins) are in their own rotatable shells. The memory addresses are managed like in a virtual memory, which mathematically can also correspond to a memory cube. From time to time the shells are rotated, also if there are failures.

The memory concept presented is also suitable for other hardware components such as hard disks. It enables shorter distances than the conventional one. This is beneficial for indexing database tables, swarm exploration, and threads. The replaceable spherical root unit is designed with multiple redundancies to have a reasonable failure concept. To get to them from the outside, the memory unit can be swung out. A memory tree starts from each root.

Overall, a single memory tree can be (virtually) addressed (so-called *memory duality*). This allows fast sorting methods such as Bitsort (see Theoretical Informatics). For this purpose, the memory cells can possibly be implemented as simpler processor units with their own intelligence. For technical or computational reasons, they can also be designed twice. This concept can be used in a reduced form with PCs. In any case, there is a clear gain in speed.

© 2023 by Boris Haase

]]>The following section presupposes Set Theory and Nonstandard Analysis.

Remarks: If the moduli of \(x \in \mathbb{C}\), \({\downarrow}x\) or \(\widetilde{{\downarrow}x}\) have different orders of magnitude, the identity\[{{s}^{(0)}}(x):={\pm}_{m=0}^{n}{x^m}=(1-{{(-x)}^{\grave{n}}})/\grave{x}\]yields by differentiating\[{{s}^{(1)}}(x)={\mp}_{m=1}^{n}{m{x^{\acute{m}}}}=(\grave{n}{{(-x)}^{n}}-n{{(-x)}^{\grave{n}}}-1)/{{{\grave{x}}^{2}}}.\]The formulas above were sometimes miscalculated. For sufficiently small \(x\), and sufficiently, but not excessively large \(n\), the latter can be further simplified to \({-\grave{x}}^{-2}\), and remains valid when \(x \ge 1\) is not excessively large. By successively multiplying \({s}^{(j)}(x)\) by \(x\) for \(j \in {}^{\omega}\mathbb{N}^{*}\) and subsequently differentiating, other formulas can be derived for \({s}^{(j+1)}(x)\), providing an example of divergent series. However, if \({s}^{(0)}(-x)\) is integrated from 0 to 1 and set \(n := \omega\), an integral expression for \({_e}\omega + \gamma\) is obtained for Euler's constant \(\gamma\).

L'Hôpital's rule solves the case of \(x = -1\). Substituting \(y := -\acute{x}\), by the binomial series a series is obtained with infinite coefficients (if \({_e}\omega\) is also expressed as a series, even an expression for \(\gamma\) is obtained). If the numerator of \({s}^{(0)}(x)\) is illegitimately simplified, finding incorrect results is risked, especially when \(|x| \ge 1\). So \({s}^{(0)}(-{e}^{\pi i})\) is e.g. 0 for odd \(n\), and 1 for even \(n\), but not \(\tilde{2}\).

Definition: Let \(f_n^*(z) = f(\eta_nz)\) *sisters* of the TS \(f(z) \in \mathcal{O}(D)\) centred on 0 on the domain \(D \subseteq {}^{\omega}\mathbb{C}\) where \(m, n \in {}^{\omega}\mathbb{N}^{*}\) and \(\eta_n^m := i^{2^{\lceil m/n \rceil}}\). Then let \(\delta_n^*f = \tilde{2}(f - f_n^*)\) the *halved sister distances* of \(f\). Let \(\mu_n^m := m!n!/(m + n)!\) and \(\widetilde{(-n)!} := 0\). For \(j, k \in {}^{\omega}\mathbb{N}, f \in \mathcal{C}_{\pi}^{j+2}\) and *Fourier coefficients* \(c_k := \tilde{\hat{\pi}}{\uparrow}_{-\pi}^{\pi}{f(t)\tilde{e}^{ikt}{\downarrow t}}\)*Analysis 2*; 5., erw. Aufl.; 2002; Springer; Berlin, p. 358 ff.*Fourier series*.\(\triangle\)

Remark: A conversion to other period lengths than \(\hat{\pi }\) is easily possible*Funktionentheorie 1*; 3., verb. Aufl.; 1992; Springer; Berlin, p. 165 f.

Representation theorem for integrals: The TS (see below) \(f(z) \in \mathcal{O}(D)\) centred on 0 on \(D \subseteq {}^{\omega}\mathbb{C}\) gives for \(\grave{m}, n \in {}^{\omega}\mathbb{N}^*\)\[{\uparrow}_0^z...{\uparrow}_0^{\zeta_2}{f(\zeta_1){\downarrow}\zeta_1\;...\;{\downarrow}\zeta_n} = \widetilde{n!} f(z\mu_n) z^n.\square\]Example: For the TS \(f(x), g(x) \in {}^{\omega}\mathbb{R}\), it holds that\[{\uparrow}_0^x{f(v){\downarrow}v}{\uparrow}_0^x{\uparrow}_0^{y}{g(v){\downarrow}v{\downarrow}y} = \tilde{2}f(x\mu_1)g(x\mu_2)x^3.\]Representation theorem for derivatives: For \(\mathbb{B}_{\tilde{\nu}}(0) \subset D \subseteq {}^{\omega}\mathbb{C}, n\)-th unit roots, TS\[f(z):=f(0) + {+}_{m=1}^{\omega }{\widetilde{m!}\,{{f}^{(m)}}(0){z^m}},\]\(b_n := \tilde{\varepsilon}^{n}\,\acute{n}! = 2^j, j, n \in {}^{\omega}\mathbb{N}^{*}, \varepsilon \in ]0, r[, u := e^{\tilde{n}\hat{\pi}i}\) and \(f\)'s radius of convergence \(r \in {}^{\nu}{\mathbb{R}}_{>0}\) imply\[{{f}^{(n)}}(0)=b_n{+}_{k=1}^{n}{\delta_n^* f(\varepsilon u^k)}.\]Universal multistep theorem: For \(n \in {}^{\nu}\mathbb{N}_{\le p}, k, m, p \in {}^{\nu}\mathbb{N}^{*}, d_{\curvearrowright B} x \in\, ]0, 1[, x \in [a, b] \subseteq {}^{\omega}\mathbb{R}, y : [a, b] \rightarrow {}^{\omega}\mathbb{R}^q, f : [a, b]\times{}^{\omega}\mathbb{R}^{q \times n} \rightarrow {}^{\omega}\mathbb{R}^q, g_k(\curvearrowright B x) := g_{\acute{k}}(x)\), and \(g_0(a) = f((\curvearrowleft B)a, y_0, ... , y_{\acute{n}})\), the TS of the initial value problem \(y^\prime(x) = f(x, y((\curvearrowright B)^0 x), ... , y((\curvearrowright B)^{\acute{n}} x))\) of order \(n\) implies\[y(\curvearrowright B x) = y(x) + {\downarrow}_{\curvearrowright B}x{\pm}_{k=1}^{p}{\left (g_{p-k}((\curvearrowright B) x){+}_{m=k}^{p}{\widetilde{m!}\tbinom{\acute{m}}{\acute{k}}}\right )} + \mathcal{O}(({\downarrow}_{\curvearrowright B} x)^{\grave{p}}).\square\]Theorem for (anti-) derivatives of TS: For \(j \in {}^{\omega}\mathbb{Z}\), \(q = \tilde{\varepsilon}(z-a)\), \(a \in D\) and \(k, m \in \mathbb{N}_{<n}\), modular arithmetic*The Art of Computer Programming Volume 2*; 3rd Ed.; 1997; Addison Wesley; Reading, p. 302 - 311*DFT form*:\[{\updownarrow}^jf_n(z) := \tilde{n}(q^k)^T(\delta_{km}\widetilde{\varepsilon q}^j\widetilde{(k-j)!}k!)({\tilde{u}}^{km})(f({\varepsilon u}^m+a))+\mathcal{O}(\varepsilon^n).\square\]Conclusion: DFT-zero methods iterate zeros \(a \in {}^{\omega}\mathbb{C}\) for every function \(f(z) \in {}^{\omega}\mathbb{C}\) that can be developed into a TS at defaults \(z_0 \in {}^{\omega}\mathbb{C}\) with each time the same convergence as in methods similar to Simpson’s, if \({\updownarrow}^0f_n(z)\) is differentiated (several times) for sufficiently precise \(|z_{\grave{m}} - z_m|\) and \(m \in {}^{\omega}\mathbb{N}.\square\)

Remark: The identity instead of \(\delta_n^*\) provides arbitrarily precise approximations for the \(f^{(n)}\). The theorem is exceptionally advantageous for functions given by products. The last theorems are equally valid for multidimensional TS (with several sums) and Laurent series. The error is \(\mathcal{O}(\varepsilon^n)\) instead of \(\mathcal{O}(\varepsilon)\) for analogously defined \(m\)-dimensional DFT forms of the TS with \(\binom{m+n}{n}\) derivatives where the effort is comparable. A good choice is \(\varepsilon = \tilde{2}\) and \(n = 64\) resp. \(n = 16\) in the previous conclusion.

Theorem for derivatives of Fourier series: For \(f \in \mathcal{C}_{\pi}^{j+2}\), \(j \in {}^{\omega}\mathbb{N}, k \in [-\acute{n}, n] \cap \mathbb{Z}, t \in [-\pi, \pi]\) and \(m \in \mathbb{N}_{<\hat{n}}\), \(\hat{n}\)-th unit roots result in the following DFT form:\[{\downarrow}^jf_n(t):=(u^{\tilde{\pi}knt})^T(\delta_{(k+\acute{n})m}(ik)^j)(\tilde{u}^{km})(f(\pi m/n - \pi))/{\hat{n}}+\mathcal{O}(\tilde{n}).\square\]Conclusion: Supporting points \(mr := \pi m/n\) of the smooth \(f(mr)\) yield for \(k\) like \(m\) interpolating in \(\mathcal{O}(_en n)\):\[{\downarrow}^jf_n(t):=(u^{\tilde{r}kt})^T(\delta_{km}(ik)^j)(\tilde{u}^{km})(f(mr))/{\hat{n}}.\square\]Theorem (DFT fixed-point method): Every \(z \in {}^{\omega}\mathbb{C}\) of an arbitrary \(m\)-polynomial \(p(z) = 0\) with \(m \in [2, n] \cap \mathbb{N}\) for \(n := 2^r, r \in {}^{\nu}\mathbb{N}^*\) and coefficients from \({}^{\nu}\mathbb{C}\) can be (initiating) determined also in \(\mathcal{O}(_en n)\).

Proof and algorithm: Let \(U = (\tilde{u}^{jk})\) for \(j, k \in \mathbb{N}_{<n}, u :=e^{\tilde{n} \hat{\pi} i}, q := 2z\) and \(s_k := p(\tilde{2}u^k)\). A simple transform achieves \(|q| < \tilde{2}\) for all zeros \(\zeta\) of \(p(z)\) and \(p(0) = 1\). It follows from \(p(z) = \tilde{n}(q^j)^TUs = \tilde{n}\mu^Ts = 0\) the simplified iteration \(\mu^* = U_{1}^{-T}\mu U((\delta_{jk}\tilde{u}^j)U^{-1}\mu-(U_{\acute{n}}^{-T}\mu+\beta s^T\mu, \beta s^T\mu, ..., \beta s^T\mu)^T)\) with Kronecker delta \(\delta_{jk}\), starting point \(q := \tilde{2}\) and \(\beta \in {}^{\nu}\mathbb{C}^*\) such that each time \(||\mu^*-\mu||\) is roughly halved and \(\mu^Ts = 0\) holds. Finish by polynomial division where \(m > 2.\square\)

Series theorem for integrals: DFT forms of TS show for \(c, x \in [0, a], f \in {}^{\nu}\mathcal{C}^{n}\) and \(n, \hat{p}, r = 2^p \in {}^{\nu}2\mathbb{N}^*\)\[{\uparrow}_0^1 g(y){\downarrow}y = 2{+}_{\check{q}=1}^{\check{r}}{{+}_{\check{m}=0}^{\check{n}-1}{\widetilde{\grave{m}!}g^{(m)}\left (\tilde{r}\acute{q} \right){\tilde{r}}^{\grave{m}}}}+\mathcal{O}\left(\widetilde{\grave{n}!}g^{(n)}(\tilde{a}c){\tilde{r}}^n\right).\square\]Remarks: DFT equivalents may replace any \(g^{(m)}\) for \(g(y) := af(ay)\) and \(a > 0\). Transforming \(z := e^{\pm x}\) makes here infinite bounds of integration finite. A finite integral decreases the remainder’s modulus sufficiently. The midpoint rule is more advantageous than the trapezoidal rule.

Example: Complete elliptic integrals of the first and second kind are for \(g(\vartheta) := \check{\pi}(1 - {\varepsilon}^2 {\sin}^2(\check{\pi}\vartheta))^{\mp\tilde{2}}\) and \(\varepsilon \in \; ]0, 1[\)\[{\uparrow}_0^{1} g(\vartheta) {\downarrow}\vartheta = g(\check{1}) + \widetilde{24} g^{(2)}(\check{1}) + \widetilde{1920} g^{(4)}(\check{1}) + \mathcal{O}\left(\widetilde{9!}g^{(6)}(\check{1})\right).\]Second Euler-Maclaurin formula: The preceding theorem yields in \(\mathcal{O}(_en n)\) for \(f(\check{q}) = g(\tilde{r}\acute{q})\) and \(k = \grave{a} = \grave{r}\)\[{+}_{\check{q}=1}^{\check{r}} f(\check{q}) = {\uparrow}_{\check{1}}^{\check{k}} f(x){\downarrow}x + {+}_{\check{m}=1}^{\check{n}-1} H_m \left (f^{(\acute{m})}(\check{k}) - f^{(\acute{m})}(\check{1}) \right ) + \mathcal{O}\left (H_n \left (f^{(\acute{n})}(\check{k}) - f^{(\acute{n})}(\check{1}) \right )\right ).\]Proof: For \(h(x)=x/\sin x\) and \(H_m := {i}^m\widetilde{m!}h^{(m)}(0)=\widetilde{m!}B_m(2-2^m) \rightarrow 2(i\tilde{\pi})^m\),\[{+}_{\check{q}=1}^{\check{r}} g(\tilde{r}\acute{q}) = \tilde{2}r{\uparrow}_0^1 g(y){\downarrow}y - {+}_{\check{q}=1}^{\check{r}}{+}_{\check{m}=1}^{\check{n}-1} {\widetilde{\grave{m}!}g^{(m)}\left (\tilde{r}\acute{q} \right)} + \mathcal{O}\left(\widetilde{\grave{n}!}g^{(n)}(\tilde{a}c){\tilde{r}}^n\right)\]results in the claim by inserting and combining the factorials that are counted depending on partitions where \(B_m\) are Bernoulli numbers and \(B_{\grave{m}} = 0, B_0=1\) as well as \(B_1=-\tilde{2}.\square\)

Conclusion: It holds \(n! \sim (\hat{\pi} - \widetilde{3k}\pi)^{\tilde{2}}(\tilde{e}\check{k})^{\check{k}}\) for \(f(n) = {}_en\) and \(r = \hat{n}\).

Proof: Regard \((1+\tilde{r})^{\check{k}} \sim e^{\tilde{2}}\) and \((1-\tilde{n})^{\tilde{2}} \sim 1-\tilde{r}\) (cf. Nonstandard Analysis) as well as\[\begin{aligned}{}_en! &={\uparrow}_{\check{3}}^{\check{k}} f(x){\downarrow}x + {+}_{\check{m}=1}^{\check{n}} H_m \left (f^{(\acute{m})} (\check{k}) - f^{(\acute{m})} (\check{3}) \right ) + \mathcal{O}\left( H_{n+2} \left (f^{(\grave{n})} (\check{k}) - f^{(\grave{n})} (\check{3})\right)\right) \\ &= \check{k}\left (_e{\check{k}} - 1 \right ) - \check{3}\left (_e{\check{3}} - 1 \right ) - \left (\tilde{k} - \tilde{3} \right )/12 + 7\left (\tilde{k}^3 - \widetilde{27} \right )/360 \mp \cdots .\square\end{aligned}\]First Euler-Maclaurin formula: Mathematical induction for \(n\) shows that\[+_{\check{q}=0}^{\check{r}}f(\check{q})=\uparrow_0^{\check{r}}{f\left(x\right){\downarrow}x}+\tilde{2}(f(\check{r})+f(0))++_{\check{m}=1}^{\check{n}-1}{\widetilde{m!}}B_m\left(f^{(\acute{m})}\left(\check{r}\right)-f^{(\acute{m})}\left(0\right)\right)+\mathcal{O}\left({\widetilde{n!}}B_n\left(f^{(\acute{n})}\left(\check{r}\right)-f^{(\acute{n})}\left(0\right)\right)\right).\square\]

© 2010-2022 by Boris Haase

]]>A • B • C • D • E • F • G • H • I • J • K • L • M • N • O • P • Q • R • S • T • U • V • W • X • Y • Z

A | |

AD | antiderivative |

AN | algebraic number |

C | |

CP | closed path |

G | |

GPC | greatest-prime criterion |

GS | geometric series |

L | |

LI | line integral |

LP | linear programme |

N | |

NR | neighbourhood relation |

T | |

TS | Taylor series |

© 2021 by Boris Haase

]]>[WPSM_AC id=1171]

© 2020 by Boris Haase

]]>A • B • C • D • E • F • G • H • I • J • K • L • M • N • O • P • Q • R • S • T • U • V • W • X • Y • Z

© 2008-2022 by Boris Haase

]]>