For example, if "d" = gcd("N","M") is not small, one can perform the transposition using a small amount ("NM"/"d") of additional storage, with at most three passes over the array (Alltop, 1975; Dow, 1995). Two of the passes involve a sequence of separate, small transpositions (which can be performed efficiently out of place using a small buffer) and one involves an in-place "d"×"d" square transposition of formula_16 blocks (which is efficient since the blocks being moved are large and consecutive, and the cycles are of length at most 2). This is further simplified if N is a multiple of M (or vice versa), since only one of the two out-of-place passes is required.