1

I have a problem of repeated multiplication with a fraction (strictly less than 1), until the result is greater than a given number.

For example: Let's say the given two numbers are 3 and 1.5. We have to multiply 3 repeatedly with 0.667 (say) until the result is greater than 1.5

3 * 0.667 = 2.001

2.001 * 0.667 = 1.33 (which is less than 1.5)

So the number of multiplications we made is 1 before we hit a number less than 1.5. Instead of brute-forcing the solution(the number of times we are able to multiply), is there a way that we can find it in a better way?

Raghav
  • 65

1 Answers1

3

Basically you want $n$ such that $$a\, b^n=c$$ Take logarithms and get $$n=\frac{\log(c)-\log(a)}{\log(b)}$$ So, if $$a\, b^n<c \implies n=\left\lfloor \frac{\log(c)-\log(a)}{\log(b)}\right\rfloor$$

Claude Leibovici
  • 260,315