Fractions Cont’d, Factoring a Number

As we last spoke about Fractions, we had a simple task after getting a Fraction object. We wanted to reduce them. I was taught to rit educe a fraction by factorizing the numerator and denominator, and then crossing out the common factors. Then, multiplying the numbers together to get the reduced value. E.G.

 60        2 * 2 * 3 * 5        2 * 2 * 3 * 5       2 
----  =  -----------------  =  ---------------  =  ---
 90        2 * 3 * 3 * 5        2 * 3 * 3 * 5       3

The example above is a simple one.

So the question is, how do we best factor a number?

First, we define the mechanisms we require.  We need a way to define that a number is a factor of another.

let isFactor i pf =
    i % pf = 0I

What does this method buy us? First, it gives us a simple True/False flag defining whether or not a number is a factor of another. Namely, if the module of i and pf is 0I  (specifically, zero, as a System.Numerics.BigInteger), then we know that pf is a factor of i.

Next, we define a recursive function that takes two parameters, start and i. The idea of this function is to return a sequence of numbers from start to i, counting by twos. The start value is an option type, so if not present, it assumes 2 is a valid option, and starts the sequence there, then goes with every odd number. Note: I’m accepting as a given that this will do some checks against numbers it’s unnecessary to do that against.

Finally, I define my internal recursive loop to accumulate the resulting found factors. An interesting thing we’ve got here is some issues of partial application for function calls. The “findFunc” function is a partially applied isFactor call, with the i value already passed in. The reason I did this was to make the Seq.tryFind call easy to use, because the Seq.tryFind call is shaped like this:

('a -> bool) -> seq 'a -> Option 'a

But to get to my “bool”, I needed more than just a single ‘a parameter.  That’s why partial application was so valuable here! Instead of changing the function signature to meet my needs, I simply made a quick, easy to reference function by supplying some arguments ahead of time.

The rest of the function is fairly apparent. The loop recurses over the sequence, finding factors and then appending them to as the head of the accumulator (f::acc), until the Seq.tryFind call eventually returns None, and the accumulated list of factors is returned.

The last bits of the function just wrap up return values. In this case, we check for negative numbers, or a 0I being passed in.  Negative numbers are fairly easy to factor as they only require normal factorization of the inverse with -1I appended, and 0I simply returns an empty list.

With that, we get our results (mapped to ints, for ease of readability.)

getFactors 64000I |> List.map int;;
val it : int list = [5; 5; 5; 2; 2; 2; 2; 2; 2; 2; 2; 2]

getFactors 6423453000I |> List.map int;;
val it : int list = [8599; 83; 5; 5; 5; 3; 3; 2; 2; 2]

getFactors 9536923853063I |> List.map int64;;
val it : int64 list = [354041L; 178393L; 151L]

getFactors 953692385306332I |> List.map int64;;
// this one's still chugging.

The last thing to do here is to figure out how to avoid unnecessary iterations but that’s a topic for another blog.