This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

let getFactors (value : bigint) = | |

let isFactor i pf = | |

i % pf = 0I | |

let rec potentialFactors start i = seq { | |

match start with | |

| Some v when v > 2I -> for a in v..2I..i do yield a | |

| Some _ | None -> | |

yield 2I | |

yield! potentialFactors (Some 3I) i | |

} | |

let rec loop acc lf i = | |

let findFunc = isFactor i | |

let seq = potentialFactors lf i | |

match Seq.tryFind findFunc seq with | |

| Some (f) -> loop (f::acc) (Some (f)) (i / f) | |

| None -> acc | |

if (value < 0I) then loop [-1I] None (value * –1I) | |

elif (value > 0I) then loop [] None value | |

else [] |

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.