(* 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