3
$\begingroup$

Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$. Required is their quotient $$ \frac a b = \frac {a_1 \cdots a_n} {b_1 \cdots b_m} $$ of which is also known that it is a (positive) integer.

More formally: $A$ is supposed to be an algorithm with the following properties:

Input: $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$, $a_1, \dots, a_n, b_1, \dots, b_m \in \mathbb N$.

Output: $\frac a b$ of which we know $\frac a b \in \mathbb N$.

Desired is an algorithm with good asymptotic run time.


Answers to the comment section:

  • We know that $b > 1$ and that the quotient $\frac a b$ is a natural number, therefore there are common factors somewhere. Unfortunately I have no precise answer.

  • Regarding the (previously existing) algorithm idea: Even if none of the pairs are divisible, then one can still multiply up all numbers in the numerator and divide by the product of all numbers in the denominator. In other words, looking for pairs is supposed to simplify the computations. In particular if the product of the numbers $a_1 \cdots a_n$ is very large, one might not be able to store these numbers in a, say, 32-bit integer.

$\endgroup$
5
  • $\begingroup$ Can we assume that there are common factors ? Or that the factors have themselves common factors ? $\endgroup$
    – user16034
    Commented Sep 15, 2023 at 13:23
  • $\begingroup$ I hope I made my problem more clear. If you still think it is insufficient, then I am happy if you remove the question @D.W. $\endgroup$ Commented Sep 17, 2023 at 6:02
  • $\begingroup$ Thanks, that helped a lot. Now what would help is a definition of "good". What's the asymptotic running time of the best algorithm you can think of? e.g., of multiplying all numbers in the numerator and dividing by the product of all numbers in the denominator? $\endgroup$
    – D.W.
    Commented Sep 17, 2023 at 6:09
  • $\begingroup$ The complexity of a brute-force division is $O(n \log n)$, just like multiplication. Granted an algorithm that achieves that is not practical as of yet. But more generally, the complexity of division is $O(M(n))$, where $M(n)$ is the complexity of multiplication. Schönhage–Strassen for multiplication is practical and has complexity $O(n \cdot \log n\cdot \log \log n)$. How much of an improvement are you looking for by exploiting the knowledge of some (a few) factors? $\endgroup$
    – njuffa
    Commented Sep 17, 2023 at 8:38
  • $\begingroup$ That last sentence is suggestive. Are we suggesting that $a_1,\ldots,a_n,b_1,\ldots,b_m$ might individually fit in machine words? $\endgroup$
    – Pseudonym
    Commented Sep 17, 2023 at 13:07

1 Answer 1

1
$\begingroup$

Here is a suggestion for an algorithm that might satisfy your constraints.

First, we'll come up with an upper bound $M$ for the quotient $a_1a_2\dots a_n/b_1b_2\dots b_m$. There are many acceptable ways to do this: the first way that comes to mind is round each $a_i$ up to the next largest power of two and round each $b_i$ down to the next smallest power of $2$. This will give you an upper bound $M$ which is at most $2^{n+m}$ times larger than the product. Of course, you can get a tighter approximation by taking logarithms (and you may wish to, if your goal to work entirely with machine-word arithmetic).

The next step is to choose a set of primes $\{p_k\}$ with the property that $\prod_k p_k \geq M$. It should be sufficient to take the first $\log M$ primes here (if you really want to optimize things, you can take the first $O(\log M / \log \log M)$ primes -- see https://en.wikipedia.org/wiki/Primorial).

The strategy is now as follows. We will compute the value $v_k$ of this quotient modulo each prime $p_k$. We will then use the Chinese Remainder Theorem to find the unique integer $v$ in the range $[1, M]$ congruent to $v_k$ modulo $p_k$ (if the quotient $a/b$ is indeed an integer, it must equal $v$).

How do we compute the value $v_k = (a/b) \bmod p_k$? This is fairly standard modular arithmetic -- the trick is to first factor out all factors of $p_k$ in the $a_i$ and $b_j$. If there are more factors in the numerator than denominator then $v_k = 0$. Otherwise, you can just reduce each of the $a_i$ and $b_j$ modulo $p_k$, take the modular inverses of the $b_j$, and multiply them all together.

There are a couple of ways to implement the Chinese remainder theorem part. One very explicit way to do this is to just compute

$$v = \sum_{k} v_k \left(\prod_{k' \neq k} p_{k'}\right) w_k \bmod P$$

where $P = \prod p_k$, and $w_{k} = \left(\prod_{k' \neq k} p_{k'}\right)^{-1} \bmod p_k$. Note that the total number of primes you have will be small (logarithmic in your total answer) so this is a small computation.

So, this gives an algorithm to recover $v$ only using arithmetic between small numbers (if $P$ fits in a machine word, all these operations can be done with machine-word arithmetic). Is it more efficient than the naive approach? If you end up using $\ell$ primes here, your total complexity is on the order of $O(\ell(n + m))$ (assuming all primes stay machine-word-size). And as stated, we can take $\ell$ to be $\log M$, for a complexity of $O((n+m)\log M)$, where $M$ is any upper bound on the quotient.

Now, if you naively multiply the numbers in e.g. the numerator together it might take $O(n^2)$ time to complete the computation of the numerator (if each multiplicand fits in a word, the $i$th multiplication is between an $i$-word number and a $1$-word number, which takes time $O(i)$; summing from $i = 1$ to $n$ gives $O(n^2)$). But you can also reduce this to something closer to $O(n \mathrm{poly}\log n)$ by i. using the FFT-based multiplication algorithms mentioned in the comments and ii. repeatedly multiplying the two smallest numbers you have in the numerator. So you can also get this idea to work in quasi-linear time with some effort.

Edit:

Actually, I just realized that this is probably overkill for what you want to do. You can also just repeatedly take GCDs of each term $b_j$ in the denominator with each $a_i$ in the numerator, cancelling out common factors. This is probably the fastest way to solve your type of problem, and will have equally good time complexity. I'll leave the CRT-based write-up here for now though, since it is often a useful tool for these sorts of questions.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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