(* We are looking for a more efficient method)

As a preparation for the Fast Fourier Transform, there are times when you want the number of elements in an array to be a power of two.

I will write a method to round up the number of elements to the power of 2 and fill the back with 0.

Define some functions. In addition, there are some things to check for the arguments of each function, so I will describe them as appropriate and summarize the ones including the exception `raise`

at the end of this article.

First, define a function that rounds up any positive integer to the power of 2. (Omit the negative number check)

```
import numpy as np
def round_pow2(x :int) -> int:
"""Round up x to a power of 2
60 -> 64
40000 -> 65536
"""
return 1 << x.bit_length()
```

```
print(round_pow2(1000))
# => 1024
```

This function gets the length up to the first 1 of the `x`

bit string and shifts 1 to the larger side. The bit column `1 0 0 ... 0`

is a power of 2. The same is true for `2 ** x.bit_length ()`

.

I want 0 padding, but I define it as such because the abstraction of "filling with a certain number" is possible. This function also has something to check, but I'll omit it.

```
def back_padding(xs: np.ndarray, n: int, a) -> np.ndarray:
"""Fill the back with a so that there are n elements"""
v = np.empty(n, dtype=type(a))
v[:xs.shape[0]] = xs
v[xs.shape[0]:] = a
return v
```

```
print(back_padding(np.arange(10), 15, 0))
#=> [0 1 2 3 4 5 6 7 8 9 0 0 0 0 0]
```

What you should check is that `xs`

is a one-dimensional array and that the number of elements in` xs`

is less than or equal to `n`

. You also need that the type of `a`

matches the type of the element of` xs`

(you may not need to worry too much about this).

Combine the functions defined above and you're done. This must also be a one-dimensional array like `back_padding`

, and the element type of the array and the element type of` a`

must match.

```
def to_pow2_length(xs: np.ndarray, a) -> np.ndarray:
"""Fill the back with a so that the number of elements is a power of 2."""
return back_padding(xs, round_pow2(xs.shape[0]), a)
```

If you want to arrange it, you should be able to select before and after the side to be filled, or set `a`

to` 0`

or `0.0`

as the initial value. I personally thought that this definition was sufficient, so I left it as it is.

The definition including docstring and exception is summarized below.

```
import numpy as np
def round_pow2(x :int) -> int:
"""Round up x to a power of 2
Example)
60 -> 64
40000 -> 65536
Arguments:
x (int > 0):Positive integer
Returns:
int:Integer to the power of 2
"""
if x < 1:
raise ValueError("x must be a positive integer.")
return 1 << x.bit_length()
def back_padding(xs: np.ndarray, n: int, a) -> np.ndarray:
"""Fill the back with a so that there are n elements
Arguments:
xs (np.ndarray[shape=(m,)]):Array
n (int > m):Element count
a (xs.dtype):Value to fill
Returns:
np.ndarray[shape=(n,)]:Array with extras filled with a
"""
if len(xs.shape) > 1:
raise ValueError("The array xs must be a one-dimensional array.")
if xs.shape[0] > n:
raise ValueError("n must be greater than the number of elements in the array xs.")
if xs.dtype != type(a):
raise ValueError("The type of a must match the type of the elements in the array xs.")
v = np.empty(n, dtype=type(a))
v[:xs.shape[0]] = xs
v[xs.shape[0]:] = a
return v
def to_pow2_length(xs: np.ndarray, a) -> np.ndarray:
"""Fill the back with a so that the number of elements is a power of 2.
Arguments:
xs (np.ndarray[shape=(n,)]):One-dimensional array
a (xs.dtype):Value to fill
Returns:
np.ndarray[shape=(2**p,)]:An array in which the number of elements is a power of 2 and the back is filled with a
"""
return back_padding(xs, round_pow2(xs.shape[0]), a)
```

Recommended Posts