factors.lhs

Practical 1: Factoring Numbers

Here is a simple method for finding the smallest prime factor of a positive
integer:

> factor :: Integer -> (Integer, Integer)
> factor n = factorFrom 2 n

> factorFrom :: Integer -> Integer -> (Integer, Integer)
> factorFrom m n | r == 0    = (m,q)
>                | otherwise = factorFrom (m+1) n
>    where (q,r) = n `divMod` m

for example

*Main> factor 7654321
(19,402859)

because 

*Main> 19 * 402859
7654321

Repeatedly extracting tyhe smallest factor will return a list
of prime factors:

> factors :: Integer -> [Integer]
> factors n = factorsFrom 2 n

> factorsFrom :: Integer -> Integer -> [Integer]
> factorsFrom m n | n == 1    = []
>                 | otherwise = p:factorsFrom p q
>    where (p,q) = factorFrom m n

for example

*Main> factor 123456789
(3,41152263)
*Main> factors 123456789
[3,3,3607,3803]

Exercise 1:
factor 0 = (2,0)
factor 1 does not end 

Exercise 2:
Both were correct

Exercise 3:
If the smallest [prime] factor of n is bigger than sqrt(n) then the accomanying factor (i.e. what it is multiplied with) must also be greater than sqrt(n), however their product will exceed n, hence it cannot exist.

> factor1 :: Integer -> (Integer,Integer)
> factor1 n = factorFrom1 2 n

> factorFrom1 :: Integer -> Integer -> (Integer, Integer)
> factorFrom1 m n | r == 0    = (m,q)
>                 | n <= m*m  = (n,1)
>                 | otherwise = factorFrom1 (m+1) n
>     where (q,r) = n `divMod` m

The order does matter for cases such as 9, where the smallest prime factor is the square root of n, as both n <= m*m would be fulfilled as well as r == 0 (i.e. n is not prime), hence we can't assume that n is a prime as we do otherwise when n <= m*m is satisfied and r == 0 is not. 

Roughly sqrt(n) are needed to evaluate factor1 in the worst case scenario (i.e. that it is prime).

Exercise 4:

n `divMod` m is already calculated and executed as it is in the where statement, hence it does not require the further multiplication stage that m*m would, thereby removing a step and making the function more efficient.

n <= m*m
n = q * m + r
q * m + r <= m*m
q + r / m <= m 
r / m < 1
therefore q < m

> factor2 :: Integer -> (Integer,Integer)
> factor2 n = factorFrom2 2 n

> factorFrom2 :: Integer -> Integer -> (Integer, Integer)
> factorFrom2 m n | r == 0    = (m,q)
>                 | q < m     = (n,1)
>                 | otherwise = factorFrom2 (m+1) n
>     where (q,r) = n `divMod` m

Exercise 5:

> factor3 :: Integer -> (Integer,Integer)
> factor3 n | d2        = factorFrom3 2 n
>           | otherwise = factorFrom3 3 n
>       where d2 = n `mod` 2 == 0

> factorFrom3 :: Integer -> Integer -> (Integer, Integer)
> factorFrom3 m n | r == 0    = (m,q)
>                 | q < m     = (n,1)
>                 | otherwise = factorFrom3 (m+2) n
>     where (q,r) = n `divMod` m

factor3 ought to use less space than factor2 and factor1.

Exercise 6:
*Main> factor3 (32452843*49979687)
(32452843,49979687)
(28.87 secs, 9,086,897,672 bytes)

*Main> factor2 (32452843*49979687)
(32452843,49979687)
(58.83 secs, 18,173,692,192 bytes)

Exercise 7:

> factor4 :: Integer -> (Integer,Integer)
> factor4 n | d2        = factorFrom4 2 n 2
>           | d3        = factorFrom4 3 n 2
>           | otherwise = factorFrom4 5 n 2
>       where d2 = n `mod` 2 == 0
>             d3 = n `mod` 3 == 0

> factorFrom4 :: Integer -> Integer -> Integer -> (Integer, Integer)
> factorFrom4 m n s | r == 0    = (m,q)
>                   | q < m     = (n,1)
>                   | otherwise = factorFrom4 (m+s) n (6-s)
>     where (q,r) = n `divMod` m

*Main> factor4 (32452843*49979687)
(32452843,49979687)
(21.30 secs, 7,096,457,360 bytes)

Exercise 8:
Finding prime numbers has a high cost in terms of speed and space, so although the number of stages of recursion is reduced, the overhead is increased and therefore the process is not particularly more efficient for smaller numbers. 

Exercise 9:

Testing `factors`:

*Main> factors 55421
[157,353]
(0.00 secs, 269,688 bytes)
*Main> factors 245
[5,7,7]
(0.00 secs, 98,048 bytes)
*Main> factors 19
[19]
(0.00 secs, 97,336 bytes)

Modifying `factors`, using the enhancements from question 7.

> factors2 :: Integer -> [Integer]
> factors2 n = factorsFrom2 2 n

Although this does not use the variable m, it proves to be a lot more efficient.

> factorsFrom2 :: Integer -> Integer -> [Integer]
> factorsFrom2 m n | n == 1    = []
>                  | q < m     = []
>                  | otherwise = p:factorsFrom2 p q
>    where (p,q) = factor4 n

Exercise 10: Comparing factors to factors2

Test #1
*Main> factors (32452897*4979687*15485867)
[109,173,1721,4979687,15485867]
(20.09 secs, 7,681,122,216 bytes)

*Main> factors2 (32452897*4979687*15485867)
[109,173,1721,4979687,15485867]
(3.40 secs, 1,077,013,632 bytes)

Test #2
*Main> factors (32452867*4979687*15485867)
[4979687,15485867,32452867]
(41.64 secs, 16,534,941,928 bytes)

*Main> factors2 (32452867*4979687*15485867)
[4979687,15485867,32452867]
(14.21 secs, 4,567,968,200 bytes)

Jevon's Problem

*Main> factors 8616460799
[89681,96079]
(0.14 secs, 47,751,208 bytes)
*Main> factors2 8616460799
[89681]
(0.07 secs, 19,528,608 bytes)