Skip to main content
Code Golf

Return to Question

added 50 characters in body
Source Link
Aiden Chow
Aiden Chow
  • 14.2k
  • 1
  • 17
  • 55

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\ne-1\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]
   2, 30    -> [1073741824, 32768, 128, 8, 2, 1]

This is , so shortest code in bytes wins!

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\ne-1\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]

This is , so shortest code in bytes wins!

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\ne-1\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]
   2, 30    -> [1073741824, 32768, 128, 8, 2, 1]

This is , so shortest code in bytes wins!

added 4 characters in body
Source Link
Aiden Chow
Aiden Chow
  • 14.2k
  • 1
  • 17
  • 55

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the baseexponent reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\$\$x\ne-1\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]

This is , so shortest code in bytes wins!

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the base reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]

This is , so shortest code in bytes wins!

Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \$x\$ and a non-negative exponent \$n\$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches \$0\$. If the exponent is initially \$0\$, then just return \$1\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on \$x=3,n=21\$.

  1. \$n=21\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \$\sqrt{\frac{3^{21}}3}=3^{10}\$.
  2. \$n=10\$ is even and non-zero, so we simply take the square root. \$\sqrt{3^{10}}=3^5\$.
  3. \$n=5\$ is odd and non-zero, so we divide by the base, then square root. \$\sqrt{\frac{3^5}3}=3^2\$.
  4. Continuing the process, we get \$3^1\$ then \$3^0\$, after which the recursion stops.

Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \$x\ne-1\$ and a non-negative integer exponent \$n\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]

This is , so shortest code in bytes wins!

Became Hot Network Question
edited tags
Link
naffetS
naffetS
  • 12.8k
  • 2
  • 20
  • 53
Tweeted twitter.com/StackCodeGolf/status/1543429667780272135
Source Link
Aiden Chow
Aiden Chow
  • 14.2k
  • 1
  • 17
  • 55