Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Space-filling curves (SFC) are interesting and useful tools, which can serve for space indexing, dimension reduction or fast optimization of complex problems. As a typical problem, which can be solved using SFC can be considered a traveling salesman problem to find the shortest path through a series of nodes [15] or neighbor-finding [5].

In 1968, a conjunction of space-filling curves and mathematical programming was described in [3]. There were some limits in comparison with the convex programming techniques such as smaller tolerance of errors.

During the next years, many space-filling curves approaches was designed, such as Hilbert’s [4] space-filling curves with quantification of the locality and locality boundary of multidimensional SFC [6] with four alternative patterns [12]. The comparison of SFC used for mapping the multi-dimensional space into the one-dimensional space was presented by Mokbel et al. [14].

It was proposed the usage of SFC in such areas as compressing the bandwidth of waveforms [2]. SFC can also be implemented for a location of basis function centers in radial basis function networks serving for an evolutionary neural network training algorithm [19]. The 6-D SFC is proposed for the transformation of six number parameters on the unit circle [17]. SFC are also suggested for a design of geometric data structures [1], easy representation of two-dimensional space [8], for genetic string generation [10] or for path planning of cooperative mobile robots [21] and robotic data collection [20]. Very interesting approach, proposed by Wang et al. [18], is based on an expert system for SFC creating. Hilbert SFC can also be determined for lossless compression of the medical images [11]. Unfortunately, there does not exist face-continuous SFC constructed by reptilings of acute triangles [7]. The idea based on Morton SFC is chosen for crystal structure modelling used in solving of chemical problems [9].

The paper is organized as follows. The following section describes the necessary background theory about Residue Number System and space-filling curves. Moreover, the section contains a definition of the novel SFC. The last section discusses the pros and cons of the novel approach.

2 Space-Filling Curves Based on Residue Number System

The main benefit of this paper is the definition of the new type of SFC that is based on the special number representation called Residue Number System (RNS). Both areas have to be defined before algorithm for the RNS-based curves is going to be suggested.

2.1 Space-Filling Curves

Space-filling curves are special types of curves that are able to cover a constrained space. Some curves are designed for two-dimensional spaces, but others are generalizable to three or even more dimensions. The most popular curves Z-curve and Hilbert curve are depicted in Fig. 1. Both of them can be generalized to higher dimensions. The usage of the SFC was described above.

Fig. 1.
figure 1

Examples of two space-filling curves.

Full size image

2.2 Residue Number Systems

Residue number systems [13, 16] provide means for an alternative representation of integers that do not rely on the correspondence between sequences of digits and numbers in the usual sense [16]. RNSs is based on the congruence relation and represent numbers by sets of remainders (residues) after integer division by a fixed set of divisors (moduli). Suppose q and r are the quotient and remainder of integer division and \(a = q\cdot m + r.\) Then r is the residue of a with respect to the modulus m and we write \(r = |a|_m\). The RNS is a number representation and arithmetic system defined by a set of two or more moduli [13, 16].

Definition 1 (Residue number system)

Consider a set of positive integers (moduli), \( \mathbf {M} = \{m_1, m_2, \ldots , m_N\}\), for which it holds that \(\forall j, k \in N : j\ne k \Rightarrow \) \(m_j\) and \(m_k\) have no common divisor greater than 1. Every two moduli in \(\mathbf {M}\) are relatively prime (co–prime) to each other and any number, x, can be represented by a set of residues, \(\mathbf {r} = \{|x|_{m_i} : 1 \le i \le N\}\). Let \(\mathcal {DR} = \prod _{i \in N} (m_i)\) be the dynamic range of the RNS. Every \(x <\mathcal {DR} \) has an unique representation in the RNS defined by \(\mathbf {M}\). The RNS can represent positive integers from the range \([0, \mathcal {DR} - 1]\).

We adopt the notation from [16] and write

$$\begin{aligned} x \cong \langle x_1, x_2, \ldots , x_N \rangle \end{aligned}$$
(1)

to indicate that x is a number uniquely represented by the residue set

\(\{|x|_{m_1}, \ldots , |x|_{m_1}\}\) in the RNS defined by the moduli set \(\{ m_1, m_2, \ldots m_N\}\).

Basic arithmetic operations are in RNSs defined on residue sets [13, 16]. Addition of two numbers, \(x \cong \langle x_1, x_2, \ldots , x_N \rangle \) and \(y \cong \langle y_1, y_2, \ldots , y_N \rangle \), is in a RNS defined by

$$\begin{aligned} \nonumber x + y&\cong \langle x_1, x_2, \ldots , x_N \rangle + \langle y_1, y_2, \ldots , y_N \rangle \\&= \langle |x_ 1 + y_1|_{m_1}, |x_2 + y_2|_{m_2}, \ldots , |x_N + y_N|_{m_N} \rangle . \end{aligned}$$
(2)

Multiplication of x and y is defined in an analogous way

$$\begin{aligned} \nonumber x \times y&\cong \langle x_1, x_2, \ldots , x_N \rangle \times \langle y_1, y_2, \ldots , y_N \rangle \\&= \langle |x_ 1 \times y_1|_{m_1}, |x_2 \times y_2|_{m_2}, \ldots , |x_N \times y_N|_{m_N} \rangle . \end{aligned}$$
(3)

In the simplest case, RNSs work with unsigned non–negative integers. However, they can be easily extended on negative integers and subtraction operation can be defined. The realization of other arithmetic operations such as comparison and division is in general problematic in RNSs [16].

Although RNSs are generally more complex than traditional number systems, the definitions of addition and multiplication clearly illustrate why they are attractive for an efficient realization of fast arithmetics. The computations with potentially large numbers are split into N less complex independent tasks in a divide–and–conquer manner [13] and can be executed concurrently. They are performed over individual residues that have significantly smaller range than the RNS as a whole. Because of that and because there is no carry–propagation for addition and multiplication in RNSs, the operations can be realized in hardware fast [13] and at low–power costs [16].

The conversions from traditional to residue number systems and back are associated with a computational overhead. However, they are required only when the operations of an algorithm ‘switch’ to and from a RNS and efficient conversion methods are known for RNSs with specific moduli sets [16]. Applications that involve a large number of consecutive addition or multiplication operations can benefit from RNSs and achieve a significant speedup by residue arithmetic. RNSs have been used in digital signal processing to implement finite and infinite impulse response filters, table–lookup–based filters, discrete Fourier transform, error–detection [16], digital to analog converters, and e.g. for digital frequency synthesis [13].

figure a
Fig. 2.
figure 2

Four RNS-based space-filling curves with different quotients.

Full size image

2.3 Algorithm for RNS-Based Space-Filling Curves

The RNS system is a solid system for number representation, that may be used for acceleration of the computation using parallelization. Moreover, the RNS has a very specific behavior that may be used in many special cases. In this paper, we developed a new type of space-filling curve that is based on the residue arithmetics. More specific, the algorithm is based on the conversion from the RNS into traditional number system.

The definition of the RNS guarantees that any assignment into x that fulfill the constrains defined above may be converted into traditional system. The nature of the RNS is that the final conversion uses a lot of multiplication the inverse coefficients and the final modulo operation [16]. The consequence of this complexity of the reverse conversion is that when x and y are two different RNS numbers that differ in only residue by one than the inverse conversion of x and y differs significantly.

This behavior is the main idea of the space-filling curves generation using the RNS. The algorithm for the creating of the curve that covers a square area of size N is depicted in Algorithm 1.

As it may be seen, the pseudocode in the Algorithm 1 does not take into account rectangular areas, but the RNS curve may also cover non-squared areas. The line no. 9, where the coordinates are computed, may lead into coordinate outside of the computation area, but such point may be discarded. The set of moduli M is not unique, and many different sets may be found and used for the same size of the area. The example of four different curves that covers an area of 16 \(\times \) 16 points is depicted in Fig. 2, where the numbers in the brackets represent the moduli set.

As it can be seen from the Fig. 2, the behavior of the curves or the position of the consecutive points is different than for the standard curves. The cases (a) and (b) are highly regular. The case (d) is almost chaotic. All cases except the example (a) show that the are of the center is denser than the area around borders. This is really unusual behavior that does not follow the usual layout of the space-filling curves. This behavior, where the following points are not necessarily close to the previous may be used for neighborhood search that does not stuck too close to actual one, e.g. in the optimization algorithms.

2.4 Comparison of the Space-Filling Curves Properties

The space-filling curves that are used in real applications satisfy a locality property. It means that the near points in the original space are mapped onto near point in the curve. In the other words, when a small neighborhood is taken, e.g. classical 8-neighborhood of a point, then this neighborhood should be placed in a relatively close area in the curve. The results of such mapping are depicted in Fig. 3 which shows the cumulative frequency of average distance from the source point to the point in the neighborhood.

As it may be seen, the Z-curve and Hilbert curve are able to concentrate all points very close to each other, because about 50% of points is located closer than 10. On the contrary, the RNS-based curves spread the points from the neighborhood much farther. For the first two curves, more than 50% points are in the average on the same distance from the selected point.

Fig. 3.
figure 3

A cumulative frequency of average distances in the 8-neighborhood for a 16 \(\times \) 16 space.

Full size image
Fig. 4.
figure 4

A cumulative frequency of distances along the curves (mapping from index into 2D space of size 16 \(\times \) 16).

Full size image
Fig. 5.
figure 5

A cumulative frequency of distances along the curves (mapping from index into 2D space of size 64 \(\times \) 64).

Full size image

The second histogram depicts the inverse behavior because RNS curves show how far the following indices on the curve are placed in the 2D space. The cumulative frequency of the distances between the following indices is depicted in Fig. 4. This distance is measured using well-known Manhattan measure to maintain integer values. The similar plot for larger space is depicted in Fig. 5.

As it can be seen, the distances along the curve are in the case of RNS much bigger, and, moreover, it may increases with the size of the covered space (compare Figs. 4 and 5). This behavior is unusual and it is opposite to the standard behavior of the boths, Z- and Hilbert curves.

3 Conclusion

In this paper, a novel approach for space-filling curves generation based on the Residue Number System is introduced. The presented novel curves have a special behavior which can be customized by the selection of the Moduli set. The coverage of the defined region may look chaotic or systematic according to the used moduli set. The main difference of the proposed space-filling curves and the standard curves such as Hilbert’s or Z-curves is that the locality is not satisfied, when the mapping is applied. This property may be used in many areas, such as optimization algorithms. Even when the behavior may look chaotic and or random, it is deterministic and replicable. Everything is controlled by the moduli set that is used for curve generation.