Skip to content
Tags

Факториал 1000000

by lakmus on January 22nd, 2011

Задача: найти факториал миллиона.

Находим обычный код вычисления факториала на F#.

#light

let rec factorial n =
    match n with
    | 0 -> 1
    | _ -> n * factorial (n - 1)

printfn "%A" (factorial (17))

В примерах использования обычно берут число не больше 16. А почему? Потому что при расчёте факториала 17 произойдёт переполнение и программа выведет на экран -288522240.
Хорошо, меняем тип int на BigInteger, чтобы избежать переполнения.

#light

open System.Numerics

let rec factorial n : BigInteger =
    match n with
    | _ when n = 0I -> 1I
    | _ -> n * factorial (n - 1I)

printfn "%A" (factorial (17I))

Хорошо, факториал 17 уже считает. Но при попытке подсчитать факториал миллиона выведет на экран “Process is terminated due to StackOverflowException”. Происходит переполнение стека, потому что мы всё время тащим за собой хвост “n”. Есть решение, как избавиться от этого:

#light

open System.Numerics
open System.IO

let writer = new StreamWriter("factorial.out")

let factorial (n : BigInteger) =
    let rec fact_helper (n : BigInteger) (a : BigInteger) =
        match n with
        | _ when n = 1I -> a
        | _ -> fact_helper (n - 1I) (a * n)
    fact_helper n 1I

let value = factorial 1000000I

writer.WriteLine(value.ToString())
writer.Close()

Полученное значение слишком большое, чтобы выводить его на экран, поэтому сохраняем его в файл. В ответе больше пяти миллионов цифр, расчёты заняли около двух часов. Проверить правильность можно с помощью калькулятора.

From → F#