What is the sum of the digits of the number 2

^{1000}?

module Problem16 = let sumOfDigits n = let rec loop m acc = if m = 0I then acc else loop (m/10I) (acc + (m%10I)) loop n 0I let ans = 2I**1000 |> sumOfDigits

The naive solution works well enough, but when IntelliSense revealed that bigint has a DivRem method, I had to try that.

let rec sumOfDigits n = let rec loop m acc = if m = 0I then acc else let div,rem = bigint.DivRem (m,10I) loop div (acc + rem) loop n 0I

It’s twice as fast as the original solution, but a bit messier. This seems like the kind of thing that could be done automatically by a compiler optimization.

module Problem16 =

let originalSumOfDigits n =

let rec loop m acc =

if m = 0I then acc

else loop (m/10I) (acc + (m%10I))

loop n 0I

let originalSumOfDigits n =

let rec loop m acc =

if m = 0I then acc

else loop (m/10I) (acc + (m%10I))

loop n 0I

let rec sumOfDigits n =

let rec loop m acc =

if m = 0I then acc

else

let div,rem = bigint.DivRem (m,10I)

loop div (acc + rem)

loop n 0I

let ans = 2I**1000 |> sumOfDigits

Advertisements

[…] much to do here, after having solved problem 16. Comments RSS […]

[…] seeing how explicitly calling DivRem sped up problem 16, I wondered if explicitly saving the sum would speed this […]