Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1from functools import update_wrapper, lru_cache 

2 

3from ._pocketfft import helper as _helper 

4 

5 

6def next_fast_len(target, real=False): 

7 """Find the next fast size of input data to ``fft``, for zero-padding, etc. 

8 

9 SciPy's FFT algorithms gain their speed by a recursive divide and conquer 

10 strategy. This relies on efficient functions for small prime factors of the 

11 input length. Thus, the transforms are fastest when using composites of the 

12 prime factors handled by the fft implementation. If there are efficient 

13 functions for all radices <= `n`, then the result will be a number `x` 

14 >= ``target`` with only prime factors < `n`. (Also known as `n`-smooth 

15 numbers) 

16 

17 Parameters 

18 ---------- 

19 target : int 

20 Length to start searching from. Must be a positive integer. 

21 real : bool, optional 

22 True if the FFT involves real input or output (e.g., `rfft` or `hfft` but 

23 not `fft`). Defaults to False. 

24 

25 Returns 

26 ------- 

27 out : int 

28 The smallest fast length greater than or equal to ``target``. 

29 

30 Notes 

31 ----- 

32 The result of this function may change in future as performance 

33 considerations change, for example, if new prime factors are added. 

34 

35 Calling `fft` or `ifft` with real input data performs an ``'R2C'`` 

36 transform internally. 

37 

38 Examples 

39 -------- 

40 On a particular machine, an FFT of prime length takes 17 ms: 

41 

42 >>> from scipy import fft 

43 >>> min_len = 93059 # prime length is worst case for speed 

44 >>> a = np.random.randn(min_len) 

45 >>> b = fft.fft(a) 

46 

47 Zero-padding to the next regular length reduces computation time to 

48 1.3 ms, a speedup of 13 times: 

49 

50 >>> fft.next_fast_len(min_len) 

51 93312 

52 >>> b = fft.fft(a, 93312) 

53 

54 Rounding up to the next power of 2 is not optimal, taking 1.9 ms to 

55 compute; 1.3 times longer than the size given by ``next_fast_len``: 

56 

57 >>> b = fft.fft(a, 131072) 

58 

59 """ 

60 pass 

61 

62 

63# Directly wrap the c-function good_size but take the docstring etc., from the 

64# next_fast_len function above 

65next_fast_len = update_wrapper(lru_cache()(_helper.good_size), next_fast_len) 

66next_fast_len.__wrapped__ = _helper.good_size 

67 

68 

69def _init_nd_shape_and_axes(x, shape, axes): 

70 """Handle shape and axes arguments for N-D transforms. 

71 

72 Returns the shape and axes in a standard form, taking into account negative 

73 values and checking for various potential errors. 

74 

75 Parameters 

76 ---------- 

77 x : array_like 

78 The input array. 

79 shape : int or array_like of ints or None 

80 The shape of the result. If both `shape` and `axes` (see below) are 

81 None, `shape` is ``x.shape``; if `shape` is None but `axes` is 

82 not None, then `shape` is ``scipy.take(x.shape, axes, axis=0)``. 

83 If `shape` is -1, the size of the corresponding dimension of `x` is 

84 used. 

85 axes : int or array_like of ints or None 

86 Axes along which the calculation is computed. 

87 The default is over all axes. 

88 Negative indices are automatically converted to their positive 

89 counterparts. 

90 

91 Returns 

92 ------- 

93 shape : array 

94 The shape of the result. It is a 1-D integer array. 

95 axes : array 

96 The shape of the result. It is a 1-D integer array. 

97 

98 """ 

99 return _helper._init_nd_shape_and_axes(x, shape, axes)