1
$\begingroup$

Say we have a set $S$ of $n$ irrational numbers $\left\{a_1, ..., a_n\right\}$.

Are there any known algorithms that can determine a scaling factor $s \in \mathcal{R}$ such that $s * a_i \in \mathcal{N} \;\forall a_i \in S$, assuming that such factor exists? If multiple exist, how about the smallest one?

Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can't (or can) return a valid scaling factor?

$\endgroup$
5
  • 2
    $\begingroup$ Algorithms involving general irrationals will probably mean little without specifying how those irrationals are represented and computed. That is, a model of computation for irrationals has to be specified. For example, an oracle could be used to tell the ratio of two irrationals is rational or not and, if rational, a representation of it as a ratio of two integers. Without such an oracle, imagine what happens if we are computing the ratio of Euler's constant to 1. It is an open problem whether it is rational or not. $\endgroup$
    – John L.
    Apr 9, 2020 at 0:34
  • 1
    $\begingroup$ Thanks @JohnL. Totally fair - I thought about that when writing the Q and was honestly hoping that someone would bring that up in one of the answers as a conditional assumption on the representation, or e.g. as a set of requirements on the input or the types of operations or checks the algorithm must be able to run in e.g. O(1) or bounded time for a given input number. $\endgroup$ Apr 9, 2020 at 0:43
  • $\begingroup$ Without a proper model of computation for irrational specified, answers to this question will bound to treat the irrationals in the input more or less as rationals. For example, Steven's answer below is basically about rational numbers. $\endgroup$
    – John L.
    Apr 9, 2020 at 0:43
  • $\begingroup$ Thanks @JohnL since you bring this up, I wonder, are you aware of any representation that could make problem viable for any class of algorithms? $\endgroup$ Apr 9, 2020 at 0:52
  • $\begingroup$ Once there was a situation where the given numbers could be approximated by floating numbers to arbitrary precision (easily), and it was guaranteed that there is a scaling factor less than ${10}^9$ such that every given number will, once multiplied by that factor, become an integer. To find the least such factor, I used continued fraction. $\endgroup$
    – John L.
    Apr 9, 2020 at 5:56

1 Answer 1

4
$\begingroup$

I'm assuming that $0 \not \in \mathbb{N}$, otherwise $s=0$ is a trivial solution.

If you input numbers contain at least one positive and one negative number there is no solution. If your input numbers are all negative, either there is a solution but no smallest solution, or there is no solution at all. You can decide which of the two is the case by solving the same problem on with the numbers multiplied by $-1$.

Assume then that all input numbers are positive.

If $s a_1 = c$ and $s a_2 = c'$ for $c,c' \in \mathbb{N}$, then $c' = s a_2 = c \frac{a_2}{a_1}$, i.e., $\frac{a_2}{a_1}= \frac{c'}{c}$. This shows that you can only find a solution if all your irrational numbers can be obtained by multiplying $a_1$ by some rational factor.

In this case you can consider the set of numbers $\{1, \frac{a_2}{a_1}, \frac{a_3}{a_1}, \dots, \frac{a_n}{a_1}\}$ instead. Since they are all rationals you can write them as $\{1, \frac{b_2}{c_2}, \frac{b_3}{c_3}, \dots, \frac{b_n}{c_n}\}$, where $b_i,c_i \in \mathbb{N}$ and $gcd(b_i,c_i)=1$. You can then find the minimum common multiple of the denominators and multiply it by $a_1^{-1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.