Arithmetic operations on numbers represented by prime factors (optimizing calculations)

Question

Shortly, I'm asking for ideas on how to do 2 things:

1. Given the prime factors of two numbers $x,y$, find the prime factors of $x+y$ without finding $x+y$ and factoring it.
2. Given the prime factors of two numbers, determine which number is bigger, or at least find a partial check that will determine the answer for a significant amount of the possible cases.

If you're interested in the long story and the bigger picture of what I'm playing with, read on. This is just for fun, I am not doing this with any particular practical applications in mind, but who knows maybe it will turn out to be useful. To speed up calculations with very big numbers and many operations, I was thinking about representing rational numbers by prime factors. I defined some arithmetic operations that are indeed faster with this representation, but I failed defining addition and also failed finding a way to compare numbers without converting them back into standard representation.

---

First, the representation:

Let $x$ be an infinite ordered tuple of whole numbers, and $p(n)$ be the $n$th prime number. $x$ represents the following number:

$$\prod_{n=1}^{\infty} p(n)^{x_n}$$

For example:

$$(1,1,-2,0,0,0,...) = 2^1 \cdot 3^1 \cdot 5^{-2}$$

But this represents only positive numbers, so let's add another number (a "sign number") to the beginning of the tuple ($0$th position - $x_0$) that must be in $\{-1,0,1\}$. Now the tuple represents the number:

$$x_0\prod_{n=1}^{\infty} p(n)^{x_n}$$

This is the final definition. So now that we have a way to represent all rational numbers, let's look at the arithmetic with this representation.

---

Let $x,y$ be rational numbers, and $x_i,y_i$ the $i$th digits in the infinite ordered tuples representing these numbers.

Multiplication is easy:

$$x\cdot y = (x_0 \cdot y_0, x_1 + y_1, x_2 + y_2, ..., x_i + y_i, ...)$$

The first numbers are multiplied together, and the rest are summed.

Division is the same but with subtraction instead of addition:

$$\frac{x}{y} = (x_0 \cdot y_0, x_1 - y_1, x_2 - y_2, ..., x_i - y_i, ...)$$

Powers are also easy:

$$x^n = (x_0^{|n|}, nx_1, nx_2, ..., nx_i, ...)\\ n\in \Bbb{Z}$$

---

Addition is where I'm stuck (I don't want to calculate the actual numbers, add them and then factor, this would defeat the purpose of representing numbers by their prime factors). I guess this is an unsolved problem because solving it would provide an easy way to find all the prime numbers, but I would appreciate any pointers to potentially useful directions.

I did find a way to at least somewhat optimize the calculation when I convert them to standard representation.

First I'll define something that will be useful here and also later on. Let's say I want to get a more convenient representation of $x$ and $y$ (still with tuples). The first thing I'll do is factor out the greatest common divisor, and then I'll also factor out the smallest number that is required to turn both numbers into integers. This leaves me with two integers that have no common factors, and the number I factored out to get these integers.

For example if:

$$x=(1,2,5,4,0,4,0,...)\\ y=(1,3,3,4,-2,4,0,...)$$

I can divide both of them by $(1,2,3,4,-2,4,0,...)$ and get:

$$\frac{(1,2,5,4,0,4,0,...)}{(1,2,3,4,-2,4,0,...)}=(1,0,2,0,2,0,0,...)\\ \frac{(1,3,3,4,-2,4,0,...)}{(1,2,3,4,-2,4,0,...)}=(1,1,0,0,0,0,0,...)$$

It's easy to find this convenient common factor, for every $i>0$, the $i$th number in the tuple representing the common factor is $\min(x_i,y_i)$. I have no better name for it, so let's just call it Convenient Common Factor (CCF for short).

Back to the topic of addition when using the tuple representation. I said I found a way to optimize the calculation despite the need to convert the numbers into standard representation. The idea is to factor out the CCF before the conversion from tuples to standard representation, so I can perform the conversion and addition on only the convenient integers, and once I convert their sum back into tuples I can multiply it by the CCF. This process makes both the addition and the conversion easier, including the factoring to convert back to tuples (simply because the number is smaller), but it's still going to be a ridiculously slow process because big numbers take a long time to factor (at least without quantum computers).

---

I'm also interested in comparing the size of two numbers. If $a>b$ then dividing or multiplying both of them by the same positive number doesn't change the inequality. This means that I can factor out the CCF and then compare the more convenient numbers. Using the numbers from the CCF example:

$$(1,2,5,4,0,4,0,...) - (1,3,3,4,-2,4,0,...) = (1,2,3,4,-2,4,0,...) \cdot \big( (1,0,2,0,2,0,0,...) - (1,1,0,0,0,0,0,...) \big)$$

While in this example it's obvious that the first number is bigger, I didn't find an algorithm that will give the correct answer in every case without multiplying some numbers in the tuple by their corresponding primes. Intuitively it seems like this problem is easier than the addition problem and might have an easier solution or at least a decent partial solution to narrow down the cases that require conversion into standard representation (by performing a relatively quick check to see if the answer can be found without conversion, like "are $x$'s factors bigger than all of $y$'s factors and at least as numerous?" but hopefully something that covers more cases).

Another way to look at the problem is to divide the numbers by each other and compare the result to 1, in the case of this example we get $(1,-1,2,0,2,0,0,...) > 1$. Not sure if it's helpful, just throwing ideas.

Answer 1

Answer to question 2 - a check that always works which doesn't involve calculating the actual numbers (nor multiplying any primes together).

Instead of comparing the numbers, compare their logarithms.

With very close numbers, their logarithms are also very close, so using calculations of limited precision is doomed to fail. The solution is to calculate the logarithms iteratively with ever increasing precision, and at the same time also calculate the error range, and as soon as the sum of logarithms exits the error range I can be certain about the answer.

I chose to use base 2 logarithm because it's convenient for a computer to work with base 2. This Wikipedia article explains how to calculate $log_2$ iteratively.

I wrote a program that uses this method and in each iteration chooses the logarithm with (approximately) worst precision and increases it's precision in the way the Wikipedia article describes, until the overall precision is enough. It works, and it works much faster than calculating the actual numbers. In fact, it worked even with such big numbers that my computer couldn't calculate their exact value within a reasonable amount of time at all! But of course I can go even bigger until this algorithm will become slow too.

Also, the answer for most numbers (at least for the random numbers my computer program generated) can be found using the check I described in my previous answer, so I get great speed gains by trying it first and using the logarithms as a plan B.

Answer 2

Question 2: partial answer.

I'll start with an example (using the tuple notation described in the question, but without the "sign number", assuming both numbers are positive), let's say I'm trying to figure out which number is bigger:

$$x=(2,4,2,4,0,...)\\ y=(4,2,3,3,0,...) $$

$x>y \iff \frac xy > 1$

$$\frac{x}{y}=(2-4, 4-2, 2-3, 4-3, 0-0, ...)=(-2,2,-1,1,0,...)$$

I can split this number into numbers that are all obviously greater than 1, and therefore their product is also greater than one, showing that $x>y$:

$$\frac xy = (-2,2,-1,1,0,...) = (-2,2,0,0,0,...) \cdot (0,0,-1,1,0,...) = \left(\frac{3}{2}\right)^2 \cdot \frac{7}{5}$$

The trick is to find for each negative number in the tuple, positive numbers to it's right that will at least match it in value (a positive number can be shared with multiple negative numbers to it's left, as long as it's big enough to be split between them).

The algorithm is:

1. Let $d=0$.
2. Start at the first negative number in the tuple.
3. Let $c$ be the number in the current position.
4. Set $d$ to $\max(d+c,0)$.
5. If there are more non zero numbers in the tuple, advance to the next number in the tuple and repeat steps 3-5.
6. If you finished with $d=0$ then certainly $x>y$, otherwise it is uncertain.

Here's another example:

$$\frac xy = (1,10,-1,3,-2,1,-2,0,4,0,...)$$

Starting from the left, the first negative is -1 so $d=-1$. Next is 3, we add it to $d$ and because $d$ became positive we make it 0. Next we have -2 followed by a 1 so we are now at $d=-1$. The next number is -2, so $d=-3$. The 0 makes no difference, and finally the 4 is big enough to get us back to $d=0$. We finished with $d=0$, so $x>y$.

And a similar check can be done to see if $x<y$, with the negatives and positives switching roles and $d≥0$.

This covers an infinite number of cases, but there is also an infinite number of cases that it won't solve, I'm not sure which kind of case is more common in practice (it also depends on the situation), but this check is very fast compared to calculating $x$ and $y$ by multiplying the prime factors, so when this check works it helps a lot, and when it doesn't it's a negligibly small waste of time (for a computer).

More rules can be added to the check to make it cover more cases (for example a negative 1 preceded immediately by a positive 1 and has another positive 1 anywhere before it, also make a positive fraction), but I'm not sure if any of these rules are worth adding, because they might be useful in relatively few cases and unnecessarily slow down the simple check.

I still didn't find a check that works in all cases.