2

I do not know how to properly formulate this question, but I am trying to find the best algorithm to get the nearest integer number where every set of numbers (including decimals) give an integer number when doing multiplication. Example:

Assuming:

X = 232
Y = [2, 5, 1, 0.1, 0.0625]

The final number will depend on both 0.1 and 0.0625 (given that integer multiplication will always be another integer):

232 * 0.1 = 23.2

232 * 0.0625 = 14.5
  • 232 can't be, both results still have decimal.

Now we can assume using 230 will work for 0.1, but:

230 * 0.1 = it works, it is a proper integer.
230 * 0.0625 = 14.375 but not really because it still has a decimal when multiplied by 0.0625.

The number that actually works is 160 (every number ending with 0 will suit 0.1, but not 0.0625):

160 * 0.1 = 16
160 * 0.0625 = 10
  • 160 suits both perfectly, so this is the number we were looking for (notice we began with 232 and went all the way back to find the nearest integer that suits every number in Y).

What will be the correct algorithm to determine this faster and efficiently independently of how many numbers with decimals I may have?

1
  • "Nearest" to what? Or do you mean "smallest" (= nearest to zero)? "Independently of how many numbers with decimals" makes obviously no sense, since for processing N numbers, the minimum processing time cannot be less than O(N). Please edit the question and clarify. – Doc Brown Oct 8 '20 at 10:16
1

Multiply by 10^x so that all numbers are integers and then divide by the greatest common divisor (gcd). There are plenty of answers which describe how to find the latter. The resulting ratio 10^x/gcd is your multiple. If you want to ensure that the ratio is also an integer, include 10^x as one of the numbers that you are finding the gcd of.

1

If you can get your decimals less than zero into integer reciprocals, then this is Least Common Multiple, and factors of that.  (Integers greater than 1 already yield integers).

The reciprocal of 0.1 is 10, and of 0.0625 is 16. (160/10 is the same as 160*0.1)

LCM of 10 and 16 is 80, so 80, 160, 240, all will work.

To get a number like 0.4's reciprocal into an integer, multiply as needed: 1/0.4 = 2.5, so you can multiply by 2 to get 5 — then also multiply the other number's reciprocal by the same value.  In general, need to find one multiplier that works to making both reciprocals into an integer.

Programming approaches for LCM are fairly well published.

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.