Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ p-adic number / Wikipedia. used in number theory. somewhat indirect, eg there is some analysis of the Collatz conjecture via p-adic theory & Collatz is considered by some to be deeply connected to TCS undecidability research. $\endgroup$– vznCommented Oct 25, 2014 at 17:19
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.
answered Oct 24, 2014 at 1:08
$\begingroup$
$\endgroup$
5
Hensel lifting is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. Hensel lifting is used in many algorithms such as factoring polynomials or doing linear algebra over $\mathbb{Z}$ (if I recall correctly Dixon has a paper on the latter).
answered Oct 24, 2014 at 0:59
-
$\begingroup$ From polynomials in $\Bbb Z_p[x]$, we cannot say anything about representation in $\Bbb R[x]$. Right? $\endgroup$– TurboCommented Oct 26, 2014 at 4:52
-
1$\begingroup$ @J.A: Unlikely (I assume here by $\mathbb{Z}_p$ you mean the $p$-adic integers). Perhaps some relationship between $\mathbb{Q}_p[x]$ and $\mathbb{R}[x]$ (especially if one considers questions over all $p$) or between $\mathbb{Z}_p[x]$ and $\mathbb{Z}[x]$... See the Hasse principle: en.wikipedia.org/wiki/Hasse_principle $\endgroup$ Commented Oct 26, 2014 at 13:52
-
-
$\begingroup$ Has the relation between $\Bbb Q_p[x]$ and $\Bbb R[x]$ been ever used? say in size of circuits and polynomials and rational functions or rank in communication complexity? $\endgroup$– TurboCommented Oct 26, 2014 at 17:16
-
$\begingroup$ @J.A: I don't know - if you find a use or a reference to a use, please let us know! $\endgroup$ Commented Oct 26, 2014 at 20:31
$\begingroup$
$\endgroup$
There are also some computational models:
Here is the first paper: Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112
answered Oct 26, 2014 at 9:54
$\begingroup$
$\endgroup$
2
here is a nice general survey with a brief overview of diverse (recent) CS applications for p-adic theory, p3
What are p-Adic Numbers? What are They Used for? / Rozikov
Here are areas where p-adic dynamics proved to be effective: computer science (straight line programs), numerical analysis and simulations (pseudorandom numbers), uniform distribution of sequences, cryptography (stream ciphers, T- functions), combinatorics (Latin squares), automata theory and formal languages, genetics. The monograph [9] contains the corresponding survey. For a newer results see recent papers and references therein: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Moreover, there are studies in computer science and cryptography which along with mathematical physics stimulated in 1990th intensive research in p-adic dynamics since it was observed that major computer instructions (and therefore programs composed of these instructions) can be considered as continuous transformations with respect to the 2-adic metric, see [11, 12].
