# Problem 38

The application below measures the time to calculate phi of 10090 using the algorithms from Problem 34 and Problem 37. Because it uses the Elm Architecture it will not run on elm.org/try. Instead, install Elm, compile and run this application on your local machine. See https://guide.elm-lang.org/install.html.

.

``````import Html exposing (div, button, p, program, text)
import Html.Events exposing (onClick)
import Time exposing (Time)

{- ======================================================
Test 1
-}

test1 : Int -> Int
test1 n =
test totient n

totient : Int -> Int
totient n =
List.length <| List.filter (\x -> coprime n x) (1..n)

coprime : Int -> Int -> Bool
coprime a b =
gcd a b == 1

gcd : Int -> Int -> Int
gcd a b =
if b == 0 then
abs a
else
gcd b (a % b)

{- ======================================================
Test 2
-}

test2 : Int -> Int
test2 n =
test phi n

phi : Int -> Int
phi n =
if n < 1 then
0
else
List.product
<| List.map (\( p, m ) -> (p - 1) * p ^ (m - 1))
<| primeFactorsM n

primeFactorsM : Int -> List ( Int, Int )
primeFactorsM n =
toTuples <| primeFactors n

primeFactors : Int -> List Int
primeFactors n =
if n < 2 then
[]
else
let
prime =
Maybe.withDefault 0
<| dropWhile (\x -> n % x /= 0) (2..n)
in
prime :: (primeFactors <| n // prime)

dropWhile : (a -> Bool) -> List a -> List a
dropWhile predicate list =
case list of
[] ->
[]

x :: xs ->
if (predicate x) then
dropWhile predicate xs
else
list

takeWhile : (a -> Bool) -> List a -> List a
takeWhile predicate xs =
case xs of
[] ->
[]

hd :: tl ->
if (predicate hd) then
hd :: takeWhile predicate tl
else
[]

toTuples : List a -> List ( a, Int )
toTuples fs =
case fs of
[] ->
[]

x :: xs ->
( x, List.length (takeWhile (\y -> y == x) fs) )
:: toTuples (dropWhile (\y -> y == x) fs)

{- ======================================================
Timing test app
-}

test : (Int -> Int) -> Int -> Int
test f n =
List.length
<| List.map f (1..n)

main =
Html.program
{ init = init
, view = view
, update = update
, subscriptions = (\_ -> Sub.none)
}

view model =
div []
[ button [ onClick (ExecuteTest 1) ] [ text "Test 1" ]
, div []
[ text
<| case Tuple.first model.testTimes1 of
Err msg ->
msg

Ok s ->
case Tuple.second model.testTimes1 of
Err msg ->
msg

Ok e ->
("totient completed in " ++ toString (e - s) ++ " milliseconds.")
, p [] []
, text
<| case Tuple.first model.testTimes2 of
Err msg ->
msg

Ok s ->
case Tuple.second model.testTimes2 of
Err msg ->
msg

Ok e ->
("phi completed in " ++ toString (e - s) ++ " milliseconds.")
]
, button [ onClick (ExecuteTest 2) ] [ text "Test 2" ]
]

type Msg
= NoOp
| ExecuteTest Int
| GetTimeFailure String
| StartTime Int Time
| RunTest Int Time
| EndTest Int Time

type alias TestTimes =
( TestTime, TestTime )

type alias TestTime =
Result String Time

type alias Model =
{ testReps :
Int
-- don't hard code this or Elm will memoize the test functions
, testTimes1 : TestTimes
, testTimes2 : TestTimes
}

init : ( Model, Cmd Msg )
init =
( { testReps = 1000
, testTimes1 = ( Err "Please Run Test 1", Err "No end time yet!" )
, testTimes2 = ( Err "Please Run Test 2", Err "No end time yet!" )
}
, Cmd.none
)

update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
case msg of
EndTest n time ->
( case n of
1 ->
{ model | testTimes1 = ( Tuple.first model.testTimes1, Ok time ) }

2 ->
{ model | testTimes2 = ( Tuple.first model.testTimes2, Ok time ) }

_ ->
model
, Cmd.none
)

ExecuteTest n ->
( model
)

GetTimeFailure msg ->
( { model | testTimes1 = ( Err "No start time yet!", Err "No end time yet!" ) }
, Cmd.none
)

NoOp ->
( model, Cmd.none )

RunTest n time ->
( case n of
1 ->
{ model
| testTimes1 = ( Ok time, Err "No end time yet!" )
, testReps = always model.testReps (test1 model.testReps)
}

2 ->
{ model
| testTimes2 = ( Ok time, Err "No end time yet!" )
, testReps = always model.testReps (test2 model.testReps)
}

_ ->
model
)

StartTime n time ->
( model