Knuth’s Up-Arrow Notation For Exponentiation

Team 1 - Programming
Published: February 13, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

Knuth’s up-arrow notation, also known as Knuth’s arrow notation, is a mathematical notation for exponentiation that was introduced by Donald Knuth in his book “Concrete Mathematics”. It uses a sequence of up-arrows (↑) to represent exponentiation with various bases and exponents.

Approach: Exponentiation depends on the number of arrows used in the notation. Here is a general approach for each type of exponentiation represented by the up-arrow notation.

  • One Arrow (a↑b): For this type of exponentiation, the approach is to multiply the base a by itself b times. This is equivalent to a * a * a * … * a where there are b a‘s. .000000000000000000000000000For Example, 5↑4 is represented as 5↑4 = 5^4 = 625
  • Two Arrows (a↑↑b): For this type of exponentiation, the approach is to raise the base a to the power of a b times. This is equivalent to a^(a^(a^(…))) where there are b a‘s inside the parentheses. For Example, 3↑↑4 is represented as 3↑↑3 = 3^(3^3) = 3^27 = 7625597484987.
  • Three or More Arrows: For this type of exponentiation, the approach is to perform the exponentiation operation b times, with each exponentiation operation taking the previous result as its base. The first exponentiation is performed using the base a. For Example, 2↑↑↑3 is represented as 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2^2) = 2↑↑4 = (2^(2^(2^2))) = 2^16 = 65536

Below is the implementation of Knuth’s up-arrow notation:

C++

#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

  

lli knuth_arrow(int a, int k, int b)

{

  

    

    if (b == 0)

        return 1;

    if (k == 1)

        return pow(a, b);

  

    return knuth_arrow(a, k - 1, knuth_arrow(a, k, b - 1));

}

  

int main()

{

  

    

    cout << knuth_arrow(5, 1, 4) << endl;

  

    

    cout << knuth_arrow(3, 2, 3) << endl;

  

    

    

    cout << knuth_arrow(2, 3, 3) << endl;

    return 0;

}

Java

public class GFG {

    public static long knuth_arrow(int a, int k, long b)

    {

        

        if (b == 0)

            return 1;

        if (k == 1)

            return (long)Math.pow(a, b);

        return knuth_arrow(a, k - 1,

                           knuth_arrow(a, k, b - 1));

    }

  

    

    public static void main(String[] args)

    {

        

        System.out.println(knuth_arrow(5, 1, 4));

  

        

        System.out.println(knuth_arrow(3, 2, 3));

  

        

        

        System.out.println(knuth_arrow(2, 3, 3));

    }

}

Python3

  

  

def knuth_arrow(a, k, b):

        

    if b == 0:

        return 1

    if k == 1:

        return a**b

    return knuth_arrow(a, k-1, knuth_arrow(a, k, b-1))

  

  

print(knuth_arrow(5, 1, 4))

  

print(knuth_arrow(3, 2, 3))

  

print(knuth_arrow(2, 3, 3))

Output

625
7625597484987
65536

Time Complexity: O(K)
Auxiliary Space: O(K)

Source: www.geeksforgeeks.org