I have some numbers n in range 100 ... 999 and some other numbers m also in range 100 ... 999. Is it possible to sort all the product m*n without calculating the actual product?
Sorry, my English for mathematical terms is limited. Feel free to edit the post. I'll give an example for better understanding.
First of all, it's obvious that 100*100 will be the lowest possible product and 999*999 is the highest product. Therefore I can start sorting the products, without actually knowing that 100*100 is 10000 and 999*999 is 998001.
At this point in time the sorted list of products is
100*100, ..., 999*999
Next, I can tell that there is no other lower value than 100*101 and 101*100 and there is no higher value than 999*998 and 998*999, so my list is now
100*100, 100*101, 101*100, ..., 999*998, 998*999, 999*999
From now on, things are no so easy any more (at least for me). Is 100*102 the next lowest number or is it 101*101? On the highest side: will it be 999*997 or 998*998?
Is there a way to continue sorting products like this? I'm trying to find an algorithm for that to implement it in software.
PCs are probably very fast in calculating products, but there are limitations: we may run into overflows so that we end up with non-native datatypes like BigInteger, which have worse performance. Since I need only the top 100 of largest products, I could save ~800000 multiplications if I sort the numbers in advance and then calculate only the 100 needed results.
I hope the question became clear. Of course the algorithm should also work for other ranges than 100 ... 999 and even different ranges for n and m. Those are just examples.