Есть ли эффективная реализация тетратации? - PullRequest
Новая
       15

Есть ли эффективная реализация тетратации?

5 голосов
/ 08 июня 2009

После недавнего ответа на вопрос, касающийся функции Аккермана, часть которой включала функцию для вычисления тетратации числа. Что заставило меня задуматься, есть ли более эффективный способ сделать это. Я провел некоторое тестирование самостоятельно, но я ограничен главным образом тем, что даже число, такое как 5 ^^ 3 = 5 ^ 3125 при 5 ^ 3, примерно равно 10 ^ 2, что означает 5 ^ 3125 ~ = 10 ^ (3125 * 2/3) около 2000 цифр.

Функция не подходит для разделения и завоевания методов из-за характера возведения в степень, т. Е.:

2 ^^ 5 = 2 ^ (2 ^ (2 ^ (2 ^ 2)))) = 2 ^ (2 ^ (2 ^ 4)) = 2 ^ (2 ^ 16) = 2 ^ 65536 ~ = 10 ^ (65536 * 3/10), около 20 тыс. Цифр ...

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

В случае, если кому-то неясно, о чем я говорю, вот статья вики , по сути, хотя тетрация это:

a ^^ b = a ^ a ^ a .... ^ a, b раз, а затем начинаем возведение в степень в верхнем элементе дерева сил и спускаемся вниз.

Алгоритм, который я сейчас использую, будет (хотя я использую версию ruby, если мне действительно нужны значения): 

long int Tetration(int number, int tetrate)
{
    long int product=1;
    if(tetrate==0)
        return product;
    product=number;
    while(tetrate>1)
    {
        product=FastPower(number,product);
        tetrate--;
    }
    return product;
}

Любые мысли приветствуются.

Ответы [ 3 ]

4 голосов
/ 09 июня 2009

При тетратации, если окончательный ответ состоит из d цифр, то все промежуточные результаты являются O (log d) цифрами, а не O (d) цифрами с возведением в степень. Поскольку промежуточные результаты для тетратации настолько малы по сравнению с конечным результатом, нет никакой экономии, которая может быть достигнута через разделяй и властвуй. Также маловероятно, что существует полезный способ сохранить операции возведения в степень в ОЗУ с удельной стоимостью, поскольку возведение в степень не является ассоциативным.

0 голосов
/ 08 декабря 2016

Я не думаю, что есть простой способ тетратации, Итак, я сделал это: 

<!DOCTYPE html>
    <html>
        <head>
            <script>
                var x = 1
                //That is ▽ The Number You Are Powering//
                var test = 3
                var test2 = test
                setInterval (function () {
                    // that is  ▽ How many times you power it so this would be 3 tetra 3      which is 7625597484987//
                    if (x < 3) {
                        document.getElementById('test').innerHTML = test=test2**test
                        x++
                    }
                }, 1);
            </script>
            <p id="test">0</p>
0 голосов
/ 13 ноября 2016

Быстрый тест подтверждает, что вы можете использовать тот же тип ускорения, что и для алгоритма питания:

a ↑↑ 2b = (a ^ a)

и даже более общее: a ⁿ ⁿ 2b = (a ↑ ⁿ⁻¹ a) ↑ ⁿ b

код, используемый для подтверждения этого: 

for(long a = 2; a < 5; a++) {
        for(long b = 2; b < 5; b++) {
            if(b%2 == 0) {
                System.out.println(a+"↑↑"+b+"="+tetration(BigInteger.valueOf(a), BigInteger.valueOf(b)));
                long pow = (long) Math.pow(a, a); // pow = tetration(a,2)
                System.out.println(pow+"↑↑"+b/2+"="+tetration(BigInteger.valueOf(pow), BigInteger.valueOf(b/2)));
            }
        }
    }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...