Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Categories:

Количество цифр в факториале 100000.

fact1 n = product [1..n]

reduceProduct [] = []
reduceProduct [x] = [x]
reduceProduct (a:b:xs) = (a*b) : reduceProduct xs

product' [] = 1
product' [x] = x
product' xs = product' (reduceProduct xs)

fact2 n = product' [1..n]
Вот время вычисления для разных величин n:
*Main> length $ show $ fact1 10000
35660
(0.80 secs, 90772044 bytes)
*Main> length $ show $ fact2 10000
35660
(0.05 secs, 4062092 bytes)
*Main> length $ show $ fact1 30000
121288
(7.86 secs, 789229120 bytes)
*Main> length $ show $ fact2 30000
121288
(0.27 secs, 11794628 bytes)
Вот, в чём прикол:
*Main> map (map (length . show)) $ take 3 $ reverse
      $ takeWhile ((>2) . length) $ iterate reduceProduct [1..10000]
[[13020,15484,7157],[5895,7126,7591,7893,7157],
 [2640,3255,3488,3639,3751,3841,3915,3979,4035,3123]
]
Логарифмы перемножаемых на одной итерации reduceProduct чисел примерно равны, что позволяет использовать быстрое умножение.

Обнаружилось случайно. Коллега вывел на экран fact 100000 и сказал, что там очень много цифр. Нам стало интересно, сколько же их там, мы посчитали length $ show $ fact 100000. Мне стало неинтересно ждать долго (я прождал целых 15 секунд) и я переписал алгоритм произведения списка на приведённый выше. Мы тут же посчитали число цифр в fact 1000000. Потом стало интересно, почему же происходит такое ускорение. vshabanov посчитал и сказал, что число умножений будет всего вдвое меньше, мы пообсуждали, поизучали вопрос и пришли к выводу, что умножение больших чисел выгодней, когда они примерно равны по размеру. Что и получается в случае рекурсивного произведения.
Tags: Хаскель, разное
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 28 comments