0
$\begingroup$

Given a positive real number $z=\sum_{i=1}^P n_i \log p_i$ where $p_i$ are given, known, unique prime numbers and $n_i$ unknown positive integers. Assume $10^z$ is too large to be represented as an integer in a computer, and is instead approximately encoded as $z$ which is a, say, 64bit float. $z$ and $p_i$ are given by a black box with finite precision. The prime numbers $p_i$ are, say, the smallest 100000 primes. $n_i$ are in the order of millions.

How, if possible, does one determine $n_i$ without exponentiating $z$ or $p_i$ (unless it can be done in a numerically stable way, i.e., guaranteed to not overflow)? Alternatively, how do I determine whether a number $10^a$ is an integer without evaluating the exponential ($a$ is a positive real number)?

$\endgroup$
9
  • $\begingroup$ Can you give typical values of the $n_i$? (i.e., "order of magnitude") $\endgroup$ Commented Aug 2, 2024 at 17:28
  • $\begingroup$ Do you want to (a) test whether there is any way to express the 64bit float as such a sum, or (b) find such a sum if it exists, or (c) check whether the true real number can be expressed in that form, based on a 64bit float approximation to that true real number? $\endgroup$ Commented Aug 2, 2024 at 19:25
  • $\begingroup$ What is the context and motivation for this question? In what context did you encounter it, or what application might it have? Why might it be relevant to others? $\endgroup$ Commented Aug 2, 2024 at 19:26
  • $\begingroup$ I noticed you reverted my edit to the title. But this is not what p-adic means. Also, your edit claims that $10^z$ is approximated as $z$, which I doubt is what you mean. I still don't see an answer to my question about whether you want (a), (b), or (c). Your question seems to use $z$ both to represent some real number and a 64-bit floating point approximation to that number, so I find it confusing precisely what you are asking. $\endgroup$ Commented Aug 4, 2024 at 17:01
  • 2
    $\begingroup$ Thank you for explaining the typical size of $n_i$. Please include that information in the question. Comments should not be used to provide additional information. Instead, please revise the question to include all relevant information, so people don't have to read the comments to understand what is being asked. $\endgroup$ Commented Aug 5, 2024 at 3:42

1 Answer 1

4
$\begingroup$

($\log$ here means base-$10$ as in the OP.)

This is, as far as I know, not possible. Here's a simple example of what can go wrong: if $10^z = 2^{10} = 1024 \approx 10^3$ then $z = 3.0\color{red}{103} \dots $ is close to $3$ and it's not so easy to tell whether $10^z = 2^{10}$ or $10^z = 2^3 5^3$, we already need $3$ digits of accuracy to distinguish them.

The issue gets much worse if the $n_i$ are large and there are many primes $p_i$. As a heuristic calculation, if we fix the number of primes $P$ (and allow the $n_i$ to be any non-negative integers) we can estimate the number of tuples $(n_i)$ such that $|z - n_i \log p_i| \le \frac{1}{2}$; this is roughly the difference between the volumes of two simplices with side lengths $\frac{z-\frac{1}{2}}{\log p_i}$ and $\frac{z+\frac{1}{2}}{\log p_i}$, which is roughly

$$N(z, P) = \frac{1}{P!} \frac{P z^{P-1}}{\prod_{i=1}^P \log p_i}$$

(if $z$ is much larger than $P$ which it sounds like is the case here). We have an easy upper bound $\prod_{i=1}^P \log p_i \le (\log p_P)^P \approx (\log P + \log \ln P)^P$ using the known asymptotic $p_i \sim i \ln i$ and this is pretty negligible compare to how large $z^{P-1}$ is. The significance of this number $N(z, P)$ is that if we assume, heuristically, that the values of the tuples $(n_i)$ satisfying $|z - n_i \log p_i| \le \frac{1}{2}$ are roughly uniformly distributed in $[z-\frac{1}{2}, z+\frac{1}{2}]$, then the tuple which best approximates $z$ approximates it to within an error of $\frac{1}{N(z, P)}$, and is also highly non-unique; there should be many tuples which approximate $z$ to within an error of $O \left( \frac{1}{N(z, P)} \right)$.

And $N(z, P)$ is large. It sounds like in your application $P \approx 10^5$ and you mentioned $n_i \approx 10^6$ so we can expect something like $z \approx 10^{11}$. In that case

$$\log N(z, P) \approx P \log z - P \log P - P \log \log P \approx P (\log z - \log P - \log \log P) \approx 10^5$$

which means we would need to know about $10^5$ digits of $z$ to uniquely recover the $n_i$; there's just no chance if $z$ is only a $64$-bit float.

We could also demonstrate the issue more forcefully by explicitly writing down large powers of primes which are very close to each other; the above example of $2^{10} \approx 10^3$ generalizes to any pair of primes $p, q$, via using the continued fraction of $\log_p q$ or $\log_q p$ to find best rational approximations to it. For example, WolframAlpha will happily compute that the continued fraction of $\log_2 3$ begins

$$\log_2 3 = [1; 1, 1, 2, 2, 3, 1, 5, 2, 23, \dots]$$

and taking the terms up to $23$ gives the rational approximation $\log_2 3 \approx \frac{24727}{15601}$, meaning that

$$3^{15601} \approx 2^{24727}.$$

These two numbers are very close; after taking logarithms we get $15601 \log 3 = 7443.568\color{red}{69} \dots$ and $24727 \log 2 = 7443.568\color{red}{70} \dots $ which require $9$ digits of accuracy to distinguish. And this is only using two primes! It should be possible to write down examples which require more than $20$ digits of accuracy to distinguish (which is more than $64$ bits) using only three or four primes and exponents less than $10^6$, and we could lower the exponents using a few more primes.

$\endgroup$
1
  • $\begingroup$ those examples are illuminating to just how big of an ask this problem is. great explanation! $\endgroup$ Commented Aug 4, 2024 at 22:12

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.