Одна из проблем программирования, с которой я столкнулся, включает вычисление факториалов больших чисел (чисел до 10 ^ 5). Я видел простой код Haskell, который выглядит следующим образом
factorial :: (Eq x, Num x) => x -> x
factorial 0 = 1
factorial a = a * factorial (a - 1)
который неявно обрабатывает огромные числа и как-то работает быстрее даже без кэширования, которое задействовано в коде.
Когда я попытался решить проблему с использованием Java, мне пришлось использовать BigInteger для хранения огромных чисел, а также использовать итеративную версию factorial
public static BigInteger factorialIterative(int n)
{
if(n == 0 || n == 1) return BigInteger.valueOf(1);
BigInteger f = BigInteger.valueOf(1);
for(int i = 1 ; i <= n ;i++)
f = f.multiply(BigInteger.valueOf(i));
return f;
}
Вышеприведенный код превысил установленный срок выполнения программы. Я также пробовал кэшированную рекурсивную версию factorial
public static BigInteger factorial(int n)
{
if(cache[n] != null)
return cache[n];
else if(n == 0)
return new BigInteger("1");
else {
cache[n] = n* factorial(n - 1);
return cache[n];
}
}
который дал мне ошибку из памяти (вероятно, из-за рекурсии).
Мой вопрос: почему языки функционального программирования, такие как Haskell, лучше справляются с этими проблемами, связанными с огромными числами? (несмотря на отсутствие очевидного кэширования). Есть ли способ, чтобы код java выполнялся так же быстро, как код Haskell?