[FIXED] How to find an integer multiplier to get to a power of 10?

Issue

I'm trying to create an exact decimal numeric type. I was storing it as a rational p/q where q is always as power of 10.

Now if I try to divide one of these numbers, I need to see if the result is representable as a finite decimal expansion. For example 10.2 / 80 => 0.1275 is okay, but 10 / 3 = 3.333... is not okay.

It boils down to looking at an integer q and asking: is there an integer m such that:

q * m = 10 ^ n    (q, m, n are all integers)

I can write a loop to search for it, testing n=0,1,2,3,...? But is there a more direct way? I don't know how to solve that little equation algebraiclly.

Solution

First, you need to see whether q can be written as the product of 2s and 5s; if it can, there will be an integer solution for m and n. Otherwise, there will not be.

We can find integers a, b and c such that q = (2^a)(5^b)c and c is not divisible by 2 or 5. Do this by repeatedly dividing q by 2 as long as q is still divisible by 2, incrementing a each time; then, divide by 5 and increment b as long as q is still divisible by 5; then, c will be whatever the value of q remains after this process of dividing by 2 and 5 repeatedly.

At this point, if c = 1, we can find a solution; otherwise, there is no integer m that works. Assuming c = 1, check a and b:

• if a = b, q was a power of 10 already; choose m = 1
• if a < b, choose m = 2^(b-a)
• if a > b, choose m = 5^(a-b)

Answered By - Patrick87

Answer Checked By - Clifford M. (PHPFixing Volunteer)