3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You might do better asking this on cs.stackexchange.com - this is actually more a CS question than a mathematics one. For pairs of small(ish) numbers the multiplication is so inexpensive that it seems unlikely you could do much better, but for arbitrary n-tuples I think it becomes a lot more interesting... $\endgroup$ – Steven Stadnicki Apr 10 '14 at 22:43
  • $\begingroup$ @StevenStadnicki: ok, CS might a good place as well. Personally I like solving puzzles on Math side first, that's why I asked it here. Math has already helped me optimize performance of my application a lot of times. $\endgroup$ – Thomas Weller Apr 10 '14 at 23:04
  • $\begingroup$ Here is the math side: math.stackexchange.com/a/342664/423130 ; since your question was answered there, you could migrate your question to CS asking for an efficient algorithm implementing that solution (or another), or close it as duplicate. $\endgroup$ – CidTori Nov 18 '18 at 14:42
  • $\begingroup$ Possible duplicate of How to Compare two multiplications without multiplying? $\endgroup$ – CidTori Nov 18 '18 at 14:47
  • $\begingroup$ Just a little example from yours: 101*101-100*102=(101-100)*101-100*(102-101)=1*101-100*1=101-100=1>0 so 101*101>100*102 $\endgroup$ – CidTori Nov 19 '18 at 9:19

Your Answer

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

Browse other questions tagged or ask your own question.