CODEWITHSUNDEEP
functional-programmingocamlprimesprime-factoring
Addem
Addem

Reputation: 3919

Prime factorization in a functional language

I'm writing in OCaml, trying to give a (somewhat) efficient implementation of prime factorization. I figure the best representation of a number 2 or more is in a list of exponents. For simplicity with consing I'll do it in decreasing order of primes. So 2 would be [1] and 3 would be [1;0] and 4 would be [2], and 5 [1;0;0].

I was thinking of using the sieve idea to take a number n and look for all possible divisors between 2 and sqrt(n). Then divide by any divisor and recurse. However, every implementation that I can think of seems to involve repeatedly searching over a list and that seems just unnecessarily inefficient. The outline of my solution is best stated in this code

let rec pf n =
  if (n=2) then ([1], 0)
  else let sq = int_of_float ( (float_of_int n) ** 0.5 ) in
  let primes = getPrimes sq in
  match earliestDiv n primes with
  | None -> n::(zero_list (n-1))
  | Some (x, i) -> let subproblem pf (n/x) in
              increment subproblem i

The helper functions here would be:

All of these helper functions keep making lists, and passing through lists, and so on. And in fact, I often feel like I'm doing this in functional programming. I often have the sense that I'm unnecessarily iterating over lists whereas in imperative languages I would be writing code that is more efficient. Perhaps it's just in my head, and when writing in imperative languages I less often notice how many resources are going into some of the list operations I use. But if I'm missing some important technique that could prevent repeatedly scanning lists, I'd be curious to hear it.

The question: Is it necessary to repeatedly make and iterate over lists in order to write this function?

Upvotes: 3

Views: 724

Answers (1)

octachron
octachron

Reputation: 18902

If you end up indexing a list, or filling a list with default elements up to a fixed size, lists are most probably the wrong data structure. For prime factorisation, you probably want an implementation of a sparse array. Maps would be a better (if not optimal) implementation than fixed-size lists.

Upvotes: 2

Related Questions