Set the number of elements in a NumPy one-dimensional array to a power of 2 (0 padded)

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

Round up a positive integer to a power of 2.

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 ().

Expand the NumPy array and fill it with a number

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).

Fill the back with a number so that the number of elements is a power of 2.

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.

Summary

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

Set the number of elements in a NumPy one-dimensional array to a power of 2 (0 padded)
How to count the number of elements in Django and output to a template
Get the number of specific elements in a python list
I want to judge the authenticity of the elements of numpy array
Find a guideline for the number of processes / threads to set in the application server
[Python] Precautions when finding the maximum and minimum values in a numpy array with a small number of elements
[Python] Let's reduce the number of elements in the result in set operations
How to sort by specifying a column in the Python Numpy array.
Find the number of days in a month
The shape of the one-dimensional array of numpy was complicated
Output in the form of a python array
Save an array of numpy to a wav file using the wave module
I want to set a life cycle in the task definition of ECS
Various ways to extract columns in a NumPy array
How to get the number of digits in Python
Get the size (number of elements) of UnionFind in Python
Convert elements of numpy array from float to int
How to identify the element with the smallest number of characters in a Python list?
How to check in Python if one of the elements of a list is in another list
Define a task to set the fabric env in YAML
How to find the optimal number of clusters in k-means
I want to align the significant figures in the Numpy array
How to get a quadratic array of squares in a spiral!
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
Create a 2D array by adding a row to the end of an empty array with numpy
Let's see how to count the number of elements in an array in some languages [Go, JavaScript, PHP, Python, Ruby, Swift]
How to determine the existence of a selenium element in Python
How to check the memory size of a variable in Python
How to check the memory size of a dictionary in Python
How to get the vertex coordinates of a feature in ArcPy
Create a function to get the contents of the database in Go
Find all patterns to extract a specific number from the set
Get the number of readers of a treatise on Mendeley in Python
[Python] A program that calculates the number of socks to be paired
Generate a list packed with the number of days in the current month.
[Python] How to put any number of standard inputs in a list
Check the in-memory bytes of a floating point number float in Python
Click the Selenium links in order to get the elements of individual pages
[Linux] Command to get a list of commands executed in the past
4 methods to count the number of occurrences of integers in a certain interval (including imos method) [Python implementation]
[Question] In sk-learn random forest regression, an error occurs when the number of parallels is set to -1.
I want to sort a list in the order of other lists
How to put a line number at the beginning of a CSV file
I made a program to check the size of a file in Python
I tried to display the altitude value of DTM in a graph
How to play a video while watching the number of frames (Mac)
Create a bot that posts the number of people positive for the new coronavirus in Tokyo to Slack
A story about creating a program that will increase the number of Instagram followers from 0 to 700 in a week
[Python] Combine all the elements in the array
I made a function to see the movement of a two-dimensional array (Python)
I wanted to know the number of lines in multiple files, so I tried to get it with a command
Various ways to read the last line of a csv file in Python
How to pass the execution result of a shell command in a list in Python
Feel free to write a test with nose (in the case of + gevent)
A collection of Numpy, Pandas Tips that are often used in the field
How to mention a user group in slack notification, how to check the id of the user group
To output a value even in the middle of a cell with Jupyter Notebook
[python] How to sort by the Nth Mth element of a multidimensional array
Test the number of times you have thrown a query (sql) in django
I made an appdo command to execute a command in the context of the app
Set an upper limit on the number of recursive function iterations in Python