1
Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition
arXiv:2605.21400v2 [cs.DS] 21 May 2026
Kyeong Soo Kim , Senior Member, IEEE
Abstract—We have been investigating clock skew compensation immune to floating-point precision loss by taking into account the discrete nature of clocks in digital communication systems, through which we have constructed more efficient incremental error algorithms using only integer operations by extending Bresenham’s line drawing algorithm. In this paper, we formulate the problem of clock skew compensation as a special case of the integer linear scaling in the form of i D , where there is no offset A and the scale factor is a product of two integers, and propose two algorithms—i.e., the multiplicative decomposition of integer division and the additive decomposition of direct search—for its nearest integer solution, which are not only immune to floatingpoint precision loss but also non-incremental unlike our prior approaches based on Bresenham’s algorithm. Having theoretically established both decomposition algorithms based on a unified and rigorous formulation of the problem of the integer linear scaling rounded to the nearest integer, we discuss the space-time trade-off through the analysis of their computational complexities and nonoverflow conditions. The numerical examples demonstrate the relative advantages and disadvantages of the two algorithms in a practical context of clock skew compensation under two different scenarios based on 32-bit and 64-bit integers: We observe that the multiplicative decomposition of integer division algorithm can obtain the nearest integer solutions with the complexity of O(1) when D is much smaller than the maximum value of the underlying integer type but overflows otherwise; in comparison, the additive decomposition of direct search algorithm can handle all the cases under both scenarios without overflows but at the expense of increased computational complexity when i approaches the maximum value of the underlying integer type. We also observe that the additive decomposition of direct search algorithm based on 32-bit integers is equivalent to the clock skew compensation based on 64-bit double-precision floatingpoint arithmetic, while both algorithms based on 64-bit integers are equivalent to the clock skew compensation based on 128-bit quadruple-precision floating-point arithmetic, which highlights another trade-off between the bounded compensation errors and lower space complexity of the integer-based decomposition algorithms and the lower chances of overflows resulting from the wide ranges of numbers of the clock skew compensation based on floating-point arithmetic. Index Terms—Integer linear scaling, multiplicative decomposition, additive decomposition, non-incremental error algorithm, floating-point arithmetic, clock skew compensation.
I. I NTRODUCTION This work was supported in part by the Postgraduate Research Scholarships (under Grant FOSA2412040 and PGRS1912001) of Xi’an Jiaotong-Liverpool University. K. S. Kim is with the Department of Communications and Networking, School of Advanced Technology, Xi’an Jiaotong-Liverpool University, Suzhou 215123, P. R. China (e-mail: [email protected]).
SERVING that the performance of clock skew compensation based on floating-point arithmetic does not match with the prediction from theories and simulations due to the use of 32-bit single-precision floating-point arithmetic on resource-constrained platforms like wireless sensor network (WSN) nodes and Internet of Things (IoT) devices, we have been investigating clock skew compensation algorithms immune to floating-point precision loss: In [1], we have proposed an incremental error algorithm based on the extension of Bresenham’s line drawing algorithm [2], which takes into account the discrete nature of clocks in digital communication systems and thereby eliminates the effect of limited floatingpoint precision on clock skew compensation. In [3], we have complemented the algorithm by providing practical as well as theoretical bounds on the initial value of a skew-compensated clock by floating-point division based on systematic analyses of the errors of floating-point operations [4]. Note that the clock skew compensation algorithms immune to floating-point precision loss studied in [1], [3] are for a special case of linear scaling, where the y-intercept is zero, the slope is given by a ratio of two integers, and both domain and codomain are limited to integers. In fact, the integer linear scaling problem has been studied for various applications, including line drawing and pixel-perfect scaling in image/video processing and visualization [2], [5]–[7], the operation and data processing for the large area telescope (LAT) instrument in the Gamma-ray large area space telescope (GLAST) satellite in astronomy [8], and integer-only inference in machine learning [9]–[11] in addition to clock skew compensation in networking [1], [3], [12], [13], but not based on a common framework and, oftentimes, without formal proofs and systematically taking into account rounding errors. In this paper, we generalize and formulate the problem of clock skew compensation as the integer linear scaling problem in the form of i D A and propose two decomposition algorithms that can avoid floating-point precision loss while reducing overflows in obtaining the the nearest integer solution based on a fixedwidth integer type. The major contributions of our work can be summarized as follows: First, we provide a unified and rigorous formulation of the problem of the integer linear scaling rounded to the nearest integer. Second, based on the unified formulation, we propose two decomposition algorithms—i.e., the multiplicative decomposition of integer division and the additive decomposition of direct search—for the nearest integer solution to the integer linear scaling problem, which are not only immune
O
2
to floating-point precision loss but also non-incremental unlike our prior approaches based on Bresenham’s algorithm. Third, we discuss the space-time trade-off in obtaining the nearest integer solution to the integer linear scaling problem through the analysis of the computational complexities and the non-overflow conditions of the proposed decomposition algorithms. Fourth, we demonstrate the relative advantages and disadvantages of the two decomposition algorithms through extensive numerical examples in a practical context of clock skew compensation under two different scenarios based on 32bit and 64-bit integers, which also highlights another trade-off between the bounded compensation errors and lower space complexity of the integer-based decomposition algorithms and the lower chances of overflows resulting from the wide ranges of numbers of the clock skew compensation based on floatingpoint arithmetic. The rest of the paper is organized as follows: In Section II, we review clock skew compensation algorithms immune to floating-point precision loss with the underlying hardware clock model. Section III describes the multiplicative decomposition of integer division and the additive decomposition of direct search algorithms for the integer linear scaling rounded to the nearest integer and discuss their space-time trade-off through the analysis of the computational complexities and the non-overflow conditions. Section IV presents numerical examples to further demonstrate the space-time trade-off in obtaining the nearest integer solution to the integer linear scaling problem in the practical context of clock skew compensation. We conclude our work in Section V.
II. R EVIEW OF C LOCK S KEW C OMPENSATION A LGORITHMS I MMUNE TO F LOATING -P OINT P RECISION L OSS Time synchronization in networking provides a common time frame among network nodes [14], and we began our investigation of the impact of limited precision floatingpoint arithmetic on it at resource-constrained WSN/IoT nodes with the energy-efficient time synchronization based on asynchronous source clock frequency recovery—EE-ASCFR in short—scheme proposed in [15]; EE-ASCFR is based on the idea of the separation of the clock frequency estimation/compensation at sensor nodes and the clock offset and delay estimation at the head node and thereby can reduce the complexity and power consumption of sensor nodes for time synchronization by moving most of time synchronization operations to the head node. The investigation of the practical implementation of EE-ASCFR on a real WSN testbed composed of TelosB motes running TinyOS, however, reveals that its performance on battery-powered, low-complexity sensor nodes is not up to that predicted from theories and simulations due to the limited 32-bit single-precision floating-point arithmetic of sensor nodes [12]. Because we focus on the clock skew compensation at a sensor node in EE-ASCFR, we consider the first-order affine clock model [16] describing the hardware clock T of the
sensor node with respect to the reference clock t of the head node but without a clock offset as in [1], [3]: T (t) = (1 + ϵ) t
(1)
where ϵ∈R is the clock skew. Compensating for the clock skew from the hardware clock T in (1), we can obtain the logical clock t̂ of the sensor node—i.e., the estimation of the reference clock t given the hardware clock T —as follows: For ti <t≤ti+1 (i=0, 1, . . .), T (t) − T (t ) i , (2) t̂ T (t) = t̂ T (ti ) + 1 + ϵ̂i where ti is the reference time for the ith synchronization between the head and the sensor node and ϵ̂i is the estimated clock skew from the ith synchronization. The major issue is the floating-point division required for the calculation of the (ti ) , which is the skewsecond term of rhs in (2), i.e., T (t)−T 1+ϵ̂i compensated increment of the hardware clock since the ith synchronization. Because clocks in digital communication systems are basically discrete counters and timestamps exchanged among nodes are their values, we proposed an incremental error algorithm to obtain the second term of rhs in (2) using only integer addition/subtraction and comparison by extending Bresenham’s line drawing algorithm in [1], [3]: If D A is 1 ) estimated the inverse of a clock frequency ratio (i.e., 1+ϵ i based on two positive integers D and A, where D and A represent interdeparture and interarrival times of packets or their cumulative sums from the previous synchronization [17], the clock skew can be compensated for based on Theorem 1: Theorem 1 (Clock Skew Compensation Based on the Extended Bresenham’s Algorithm [1], [3]). Given a hardware clock i, we can obtain its skew-compensated clock j as follows: Case 1. D A <1: The skew-compensated clock j satisfies D D ≤j≤ i . (3) i A A Unless i D A is an integer, there are two values satisfying (3). Because we cannot know the exact value of i D A due to limited floating-point precision, however, we extend (3) to include the effect of the precision loss: For floating-point numbers with a base 2 and a precision p1 , (1 + 2u)3 (1+u−2u2 ) 1−u+2u2 t ≤j≤ t , (4) (1+u)2 (1+2u) (1+u)2 −p where t=i D . A and u=2 Let k, . . ., k+l be the candidate values of j satisfying (4). We determine j by applying the extended Bresenham’s algorithm of [1] with ∆a and ∆b set to A and D from the point (i−l, k) and on; j is determined by the y coordinate of the valid point whose x coordinate is i. Case 2. D A >1: In this case, we can decompose the skewcompensated clock j into two components as follows: D D−A j =i =i+i . (5) A A 1 p is precision in bits; for example, p=24 for the 32-bit single-precision floating-point format (i.e., binary32) defined in IEEE 754-2008 [18].
3
̂
III. I NTEGER L INEAR S CALING ROUNDED TO THE N EAREST I NTEGER Without loss of generality, we confine our discussions to the special case of integer linear scaling with two non-negative integers i and D and a positive integer A; the nearest integer solution to a general case can be obtained by applying the sign of an original problem to the solution to its non-negative version. For convenience, we also assume i≥D unless stated otherwise.
∆
Δ <1 Δ
+1
− ( ) 1+ ̂
2
1
0,0
1
2
+1
−1
A. Preliminaries Let N0 and N+ denote the set of non-negative integers and the set of positive integers, respectively. The problem of the clock skew compensation can be generalized to the problem of integer linear scaling rounded to the nearest integer as follows:
∆
−
(a) ̂ ∆ Range of the initial Value of j
− ( ) 1+ ̂
Definition 1. Given i, D∈N0 and A∈N+ , we define the nearest integer solution j to i D A as follows: j ≜ arg min k − i k∈N0
(6)
Due to the lack of tie-breaking, Definition 1 allows up to two nearest integer solutions (e.g., 7 or 8 for 3 25 =7.5). Lemma 1 provides an equivalent condition for the nearest integer solution without division.
∆
0,0
D . A
T
−
(b)
Fig. 1. Clock skew compensation based on (a) the original [2] and (b) the <1. extended Bresenham’s algorithm [1], [3] for the case of D A
Lemma 1. Given i, D∈N0 and A∈N+ , j is the nearest integer solution to i D A if and only if j satisfies the following condition: |jA − iD| ≤ |kA − iD|
Note that practical bounds loosening the theoretical bounds in (4) are also provided for practical implementation at resourceconstrained sensor nodes with limited floating-point precision in [3]. As illustrated in Fig. 1 (b), the range of the initial value of j, which are bounded in (4), determines the number of iterations of the algorithm (i.e., the difference between the upper and lower bounds). Though the clock skew compensation based on the extended Bresenham’s algorithm can greatly reduce the number of iterations compared to that based on the original algorithm as shown in Fig. 1, the numerical examples presented in [3] demonstrate that the theoretical and practical bounds based on the systematic analyses of floating-point operation errors are looser than the approximate bounds of [1] and still increase the number of iterations, which is the motivation for the current work on non-incremental error algorithms not relying on the bounds on the initial value of the clock.
(7)
∀k ∈ N0 .
(8)
Proof: If j is the nearest integer solution to i D A , j satisfies the following condition by Definition 1: j−i
Now that D−A A <1, we can apply the same procedure of Case 1 to the second component in (5) by setting ∆a and ∆b of the extended Bresenham’s algorithm to A and D−A, respectively. Let j̄ be the result from the procedure. The skew-compensated clock j is given by i+j̄ as per (5).
∀k ∈ N0 .
D D ≤ k−i A A
Multiplying both sides of (8) by A, we obtain (7). If j satisfies (7), we obtain (8) by dividing both sides of (7) by A, which means that j is the nearest integer solution to i D A according to Definition 1. Lemma 2 provides the nearest integer solution based on the exact value of i D A. Lemma 2. Given i, D∈N0 and A∈N+ , we can obtain the nearest integer solution j to i D A as follows: D j = i + 0.5 . (9) A Proof: See Appendix A. Unlike Definition 1, as Lemma 2 incorporates the round half up tie-breaking rule, it results in a unique solution. A major issue with Lemma 2 is that we cannot obtain the exact value of i D A on a real platform but only an approximate value of it due to floating-point precision loss, i.e., fp(i D A ) where fp(·) denotes the result of the floating-point operations on the given platform. From Lemmas 1 and 2, we can derive a bound on the lhs of (7): A |jA − iD| ≤ . (10) 2
4
B. Algorithms Immune to Floating-Point Precision Loss We present efficient algorithms for the integer linear scaling rounded to the nearest integer, which are immune to floatingpoint precision loss and reduce overflows in obtaining the nearest integer solution based on a fixed-width integer type through multiplicative and additive decomposition techniques. 1) Multiplicative Decomposition of Integer Division: Theorem 2 presents an algorithm based on multiplicative decomposition of integer division using the fixed-point representation [19], not relying on floating-point arithmetic and thereby immune to floating-point precision loss. Theorem 2 (Multiplicative decomposition of integer division). Given i, D∈N0 and A∈N+ , we can obtain the nearest integer solution j to i D A as follows: $ % (i mod A) D + A2 i D+ . (11) j= A A Proof: See Appendix B. Unlike the approach based on normal integer division (i.e., Theorem 2 enables us to obtain the nearest integer solution to i D A without calculating the product iD for the dividend, which could overflow when the result cannot be represented by a fixed-width integer type. If both i and D are smaller than A, however, (11) reduces back to normal integer division rounded to the nearest integer, i.e., $ % iD + A2 j= . (12) A iD A ),
2) Additive Decomposition of Direct Search: Noting that finding the nearest integer solution to i D A is an integer programming problem whose objective function is f (x)=|x−i D A| (i.e., (6) of Definition 1), we provide an alternative algorithm directly searching the minimum in Theorem 3. Theorem 3 (Direct search). Given i, D∈N0 and A∈N+ , we can obtain j, the nearest integer solution to i D A , and ∆, the value of jA−iD, using Algorithm 12 as follows: (j, ∆) = ds(i, D, A, κ, 0),
(13)
where κ∈N0 is an initial guess of j. Proof: See Appendix C. Though j from Algorithm 1 does not depend on the value of k0 (i.e., κ in (13)), it can be set to ⌊fp(i D A )+0.5⌋ if floatingpoint arithmetic is available; otherwise, it can be set to ⌊ Ai ⌋D, ⌊D A ⌋i, or just i depending on the values of i, D, and A. Also, the initialization of ∆ in Line 2 is to avoid overflow during the multiplication of kA or iD because ∆0 = k0 A − iD = (k0 − i)A + i(A − D), D A ≈1,
which is the case for clock skew especially when compensation. When the value of i is very large, there could be a chance of an overflow during the initialization of ∆. To avoid the 2 The internal variables of k , k , ∆ , and ∆ are subscripted to differen0 1 0 1 tiate their values between the updates during the proof.
Algorithm 1 Inter linear scaling to the nearest integer by direct search. 1: function ds(i, D, A, k0 , ∆− ) 2: ∆0 ⇐ (k0 − i)A + i(A − D) + ∆− 3: if ∆0 = 0 then ▷ Case 1 4: j ⇐ k0 5: else if ∆0 > 0 then ▷ Case 2 ∆0 6: k1 ⇐ k0 − A 7: ∆1 ⇐ ∆0 mod A 8: if |∆1 − A| < |∆1 | then ▷ Case 2.1 9: j ⇐ k1 − 1 10: ∆ ⇐ ∆1 − A 11: else ▷ Case 2.2 12: j ⇐ k1 13: ∆ ⇐ ∆1 14: end if 15: else ▷ Case 3 ∆0 16: k1 ⇐ k0 − A 17: ∆1 ⇐ − (|∆0 | mod A) 18: if |∆1 + A| < |∆1 | then ▷ Case 3.1 19: j ⇐ k1 + 1 20: ∆ ⇐ ∆1 + A 21: else ▷ Case 3.2 22: j ⇐ k1 23: ∆ ⇐ ∆1 24: end if 25: end if 26: return j, ∆ 27: end function
overflow, we can divide the given problem with i into a series ofPsub-problems with smaller values of in (n=1, . . ., N ), N where i=1 in =i. The main challenge is that the rounding error from a subproblem with in needs to be properly taken into account in the next subproblem with in+1 so that there should be no cumulation of rounding errors in the end. ∆ resulting from Algorithm 1, which indicates how close j is to i D A without division, can be used to carry out the information on the rounding error from one subproblem to another as stated in Lemma 3. Lemma 3. Given i1 , i2 , D∈N0 and A∈N+ , we can obtain j, the nearest integer solution to i D A , where i=i1 +i2 , and ∆, the value of jA−iD, using Algorithm 1 as follows: j = j1 + j2 , ˜ 2, ∆=∆
(14)
˜ 1 ) = ds(i1 , D, A, κ1 , 0), (j1 , ∆ ˜ 2 ) = ds(i2 , D, A, κ2 , ∆ ˜ 1 ), (j2 , ∆
(15)
where
and κn ∈N0 (n=1, 2) is an initial guess of jn . Proof: See Appendix D. Theorem 4 extends Lemma 3 to a general case.
5
j=
N X
jn ,
n=1
(16)
˜ N, ∆=∆ where for n=1, . . ., N , ˜ n ) = ds(in , D, A, κn , ∆ ˜ n−1 ), (jn , ∆ ˜ 0 = 0, ∆
×102
4
Integer Linear Scaling Error
Theorem 4 (Additive decomposition of direct search). Given i1 , . . ., iN , D∈N0 and A∈N+ , we PNcan obtain j, the nearest integer solution to i D n=1 in , and ∆, the value of A , where i= jA−iD, using Algorithm 1 for every integer N ≥1 as follows:
2
0
−2
−4
(17)
100
101
and κn ∈N0 is an initial guess of jn .
C. Space-Time Trade-off We analyze the computational complexities and the nonoverflow conditions of the algorithms presented in Theorems 2–4 and Bresenham’s algorithm [2] for integer linear scaling rounded to the nearest integer, whose results are summarized in Table I. As stated in the beginning of Section III, the nearest integer solution to a general case can be obtained by applying the sign of an original problem to the solution to its non-negative version provided by the algorithms under consideration, so we assume that not only the input and output values but also all the intermediate values of an algorithm are represented by a fixed-width W -bit signed integer type (e.g., int32_t in C/C++) for the analysis. Because the space complexity captured by O(·) describes only the limiting behavior of the memory requirements, we
103
102
103
(a)
Proof: See Appendix E.
×102
4
Integer Linear Scaling Error
Theorem 4 enables us to decompose the original problem of integer linear scaling PN rounded to the nearest integer with a large value of i= n=1 in into subproblems with its smaller components (i.e., in ) without incurring additional rounding errors during the decomposition and the summation. It is ˜ l (l<N ) that carries the information on the rounding error ∆ Pl of the nearest integer solution to n=1 in D A to the (l+1)th ˜ l is sequential, yet its absolute value subproblem; as such, ∆ is bounded by A2 (i.e., (10)). Fig. 2 shows the integer linear scaling errors resulting from ˜ n to zero for n=1, . . ., N −1 in (17) of the additive setting ∆ decomposition of direct search, where the integer linear scaling errors are calculated with respect to ⌊ fp(i D A )+0.5⌋ based on binary512 of IEEE 754-2008 [3, Table III]. We set i and D to 1×106 for 32-bit integers and 1×1012 for 64-bit integers, respectively. We also set A to D+u, where u is an integer uniformly distributed in the range of [1, 1×103 ] for 32-bit integers and [1, 1×106 ] for 64-bit integers, respectively. Because i<A, D<A, and iA≥2W−1−1, not only normal integer division but also the multiplicative decomposition of integer division cannot handle these cases due to overflows. From the results, we can observe that the integer linear scaling errors are bounded by ±0.5N as the rounding errors are bounded by ±0.5, which demonstrate how critical the transfer ˜ n between the consecutive sub-problems in the additive of ∆ decomposition of direct search is.
102 N
2
0
−2
−4
100
101 N
(b)
˜ n =0 for n=1, . . ., N −1 in (17) Fig. 2. Integer linear scaling errors with ∆ of the additive decomposition of direct search based on (a) 32-bit and (b) 64-bit integers.
also investigate the non-overflow conditions of each algorithm during its entire operation, which gives us an alternative and practical measure of its space complexity; when Algorithm A needs a bigger-size integer type than Algorithm B to avoid overflows, we could say that the space complexity of Algorithm A is higher than Algorithm B. As for Bresenham’s algorithm, due to its recursive construction of ▽(·) whose absolute value is bounded by 2A [2, Lemma 1], we have the third condition for its representation by a W -bit signed integer type. The direct search algorithm in Theorem 3 and its additive decomposition in Theorem 4, too, use ∆(·) whose absolute value is bounded by A2 and therefore require the third condition for ∆0 . The third conditions of the multiplicative decomposition of integer division in Theorem 2, on the other hand, are for the intermediate calculations in (11); its fourth condition for the product iD is for the case when both i and D are smaller than A, which reduces it back to normal integers division rounded to the nearest integer as discussed in Section III-B1. Regarding the implications of the non-overflow conditions, we first consider a special case of iD=2W−1 and A=2W−1−1 for the multiplicative decomposition of integer division algorithm. The nearest integer solution to i D A in this case is just one for W >1, but the product iD results in overflow when
6
TABLE I S UMMARY OF THE ALGORITHMS FOR INTEGER LINEAR SCALING ROUNDED TO THE NEAREST INTEGER . Complexity
Algorithm Space
Bresenham’s algorithm [2]
O(1)
Non-overflow conditions
Time
O (min(i, D))
W−1−1, D≤2W−1−1, A≤2W−1−1, i≤2 j k D i A +0.5 ≤ 2W−1−1, and
−2W−2 ≤ A ≤ 2W−2−1.
Multiplicative decomposition of integer division (Theorem 2)
Direct search (Theorem 3)
O(1)
O(1)
O(1)
O(1)
W−1−1, D≤2W−1−1, A≤2W−1−1, i≤2 k j D i A +0.5 ≤ 2W−1−1, i ⌊A ⌋D≤2W−1−1, (imodA)D+⌊ A ⌋≤2W−1−1, and 2 W−1 iD ≤ 2 −1 when i<A and D<A. W−1−1, D≤2W−1−1, A≤2W−1−1, i≤2 j k D i A +0.5 ≤ 2W−1−1, and
−2W−1 ≤ (κ−i)A+i(A−D) ≤ 2W−1 −1.
Additive decomposition of direct search (Theorem 4)
O(N )
O(N )
For n=1, . . ., N , W−1−1, D≤2W−1−1, A≤2W−1−1, ij n ≤2 k PN D W−1−1, and i=1 in A +0.5 ≤ 2 −2W−1 + A ≤ (κn −in )A+in (A−D) ≤ 2W−1 −1− A . 2 2
i≥2 or D≥2. The direct search algorithm can handle this case by setting i=2, D=2W−2 , and k0 =i without overflows. Bresenham’s algorithm, however, cannot support A=2W−1−1 due to the condition on A. For another special case of D A ≈1, which holds for clock skew compensation, the major issue is the non-overflow condition on i as we need the nearest integer solution to i D A for a large value of i. Compared to Bresenham’s and the multiplicative decomposition of integer division algorithms, the direct search algorithm can provide the nearest integer solution even for i≥2W−1−1 thanks to the additive decomposition at the expense of the increased time complexity. The results of the analysis of the computational complexities and non-overflow conditions of the algorithms summarized in Table I and the related discussions on their implications show that the direct search algorithm can better exploit the trade-off between space and time complexity in obtaining the nearest integer solution to integer linear scaling through additive decomposition together with flexible setting of an initial guess of the solution (i.e., k0 in Algorithm 1). IV. N UMERICAL E XAMPLES : C LOCK S KEW C OMPENSATION To demonstrate the space-time trade-off in integer linear scaling rounded to the nearest integer in a practical context, we apply the decomposition algorithms described in Section III-B to clock skew compensation under two different scenarios: The first scenario based on 32-bit integers assumes a resourceconstrained platform for WSN/IoT running on 1-MHz clock and focuses on the capability of each algorithm carrying out clock skew compensation without overflows. The second scenario based on 64-bit integers, on the other hand, targets a resourceful platform running on 1-GHz clock, where the focus is shifted to the scalability of the algorithms even with extremely large values of i up to 1×1018 .
The results of clock skew compensation based on the decomposition algorithms are summarized in Tables II, III, IV, and V in comparison to those based on the floating-point arithmetic with various precisions. We set D to 1×106 and 1×108 for 32-bit integers and 1×109 and 1×1012 for 64bit integers, respectively, and generate one million samples of A corresponding to clock skew uniformly distributed in the range of [−100 ppm, 100 ppm]. Given the clock resolutions of 1 µs and 1 ns for the two scenarios, the minimum and the maximum values of i (i.e., the hardware clock) correspond to 1 s and 1×103 s in Table II, 1×10−3 s and 1×101 s in Table III, 1×103 s and 1×109 s in Table IV, and 1×10−2 s and 1×105 s in Table V respectively. For the clock skew compensation based on the floating-point arithmetic, we round half up the results to obtain the nearest integer values throughout the experiments. Regarding the overflows, we observe that the multiplicative decomposition of integer division algorithm overflows for all the cases under the first scenario where the ratio of D to the maximum value of the underlying integer type is relatively larger (i.e., 231D−1 ≈4.6566×10−4 ), while it can handle all the cases of the second scenario when the said ratio is much smaller (i.e., 263D−1 ≈1.0842×10−10 ). In comparison, the additive decomposition of direct search algorithm can handle all the cases under both scenarios without overflows but at the expense of increased computational complexity when the value of i approaches the maximum value of the underlying integer type. As for the compensation errors, we observe that the additive decomposition of direct search algorithm is equivalent to the clock skew compensation based on 64-bit double-precision floating-point arithmetic under the first scenario based on 32-bit integers; under the second scenario based on 64-bit integers, on the other hand, both algorithms are equivalent
7
TABLE II C LOCK SKEW COMPENSATION BASED ON INTEGER LINEAR SCALING ROUNDED TO THE NEAREST INTEGER WITH 32- BIT INTEGERS AND D=1×106 . Algorithm
i
Compensation error*
N Min.
Double precision (binary64)†
1×106 1×107 1×108 1×109
– – – –
Single precision (binary32)†
1×106 1×107 1×108 1×109
– – – –
Multiplicative decomposition of integer division (Theorem 2)
1×106 1×107 1×108 1×109
– – – –
Additive decomposition of direct search (Theorem 4)
1×106 1×107 1×108 1×109
1 1 1×101 1×102
0 0 0 0
0 0 0 0
0 0 −4.0000 −1.9000×101
Avg. 0 0 0 0
0 0 1.0000 4.4000×101
– – – – 0 0 0 0
Notes
Max.
0 0 −1.6962 1.2973×101
– – – – 0 0 0 0
– – – –
– – – – 0 0 0 0
– – – – Overflow Overflow Overflow Overflow – – – –
* With respect to ⌊ fp(i D )+0.5⌋ based on binary512 of IEEE 754-2008 [3, Table III]. A † ⌊ fp(i D )+0.5⌋ based on the corresponding precision. A
TABLE III C LOCK SKEW COMPENSATION BASED ON INTEGER LINEAR SCALING ROUNDED TO THE NEAREST INTEGER WITH 32- BIT INTEGERS AND D=1×108 . Algorithm
Double precision (binary64)†
Single precision (binary32)†
Multiplicative decomposition of fixed-point division (Theorem ??)
Additive decomposition of direct search (Theorem 4)
i
N
1×105
– – – – – – – – – – – – – – –
1×106 1×107 1×108 1×109 1×105 1×106 1×107 1×108 1×109 1×105 1×106 1×107 1×108 1×109 1×105 1×106 1×107 1×108 1×109
1 1×101 1×102 1×103 1×104
Min. 0 0 0 0 0 0 0 0 −4.0000 −4.0000×101 – – – – – 0 0 0 0 0
Compensation error* Max. Avg. 0 0 0 0 0 0 0 0 0 0 1.0000 4.4958×10−2 0 0 1.0000 1.1900×10−1 5.0000 1.8586×10−1 8.2000×101 1.4780×101 – – – – – – – – – – 0 0 0 0 0 0 0 0 0 0
Notes – – – – – – – – – – Overflow Overflow Overflow Overflow Overflow – – – – –
* With respect to ⌊ fp(i D )+0.5⌋ based on binary512 of IEEE 754-2008 [13, Table III]. A † ⌊ fp(i D )+0.5⌋ based on single precision. A
to the clock skew compensation based on 128-bit quadrupleprecision floating-point arithmetic. This is remarkable in that the decomposition algorithms based only on integer operations require only half the size of the data types for the clock skew compensation based on floating-point arithmetic for the same compensation error. V. C ONCLUSIONS We have generalized the problem of clock skew compensation as the integer linear scaling problem in the form of iD A and proposed the multiplicative decomposition of integer
division and the additive decomposition of direct search algorithms, which decompose the product of iD and the input i, respectively, during the intermediate calculation to reduce overflows in obtaining the nearest integer solution based on a fixed-width integer type. The proposed algorithms are not only immune to floating-point precision loss due to their using only integer operations but also non-incremental to reduce their computational complexities unlike our prior approaches based on Bresenham’s algorithm. We have theoretically established both decomposition algorithms based on a unified and rigorous formulation of
8
TABLE IV C LOCK SKEW COMPENSATION BASED ON INTEGER LINEAR SCALING ROUNDED TO THE NEAREST INTEGER WITH 64- BIT INTEGERS AND D=1×109 . Compensation error*
Algorithm
i
N
Quadruple precision (binary128)†
1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – –
Double precision (binary64)†
1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – –
0 0 0 −1.0000 −2.0000 −1.3000×101 −7.7000×101
0 0 0 0 0 3.0000 5.0000×101
0 0 0 −3.9930×10−2 −8.7624×10−1 −4.9326 −1.5377×101
Single precision (binary32)†
1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – –
−7.9880×104 −5.8453×105 −5.1420×106 −7.5579×107 −1.5611×109 −9.8398×109 −5.0991×1010
3.8672×104 1.0421×106 9.4285×106 4.3954×107 1.3190×108 4.9293×109 7.6703×1010
−2.0476×104 2.1766×105 2.0610×106 −1.4900×107 −5.9591×108 −2.5240×109 1.1032×1010
Multiplicative decomposition of integer division (Theorem 2)
1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – –
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Additive decomposition of direct search (Theorem 4)
1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
1 1 1×101 1×102 1×103 1×104 1×105
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Min. 0 0 0 0 0 0 0
Max. 0 0 0 0 0 0 0
Avg. 0 0 0 0 0 0 0
* With respect to ⌊ fp(i D )+0.5⌋ based on binary512 of IEEE 754-2008 [3, Table III]. A † ⌊ fp(i D )+0.5⌋ based on the corresponding precision. A
the problem of the integer linear scaling rounded to the nearest integer—which has been studied in several disciplines under different names but not based on a common framework and, oftentimes, without formal proofs and taking into account rounding errors—and discussed the space-time trade-off through the analysis of their computational complexities and non-overflow conditions. Through numerical examples, we have demonstrated the relative advantages and disadvantages of the two decomposition algorithms in the practical context of clock skew compensation under two different scenarios. Specifically, the multiplicative decomposition of integer division algorithm overflows under the first scenario based on 32-bit integers, while it can handle all the cases of the second scenario based on 64-bit integers with a constant time complexity (i.e., O(1)); in comparison, the additive decomposition of direct search algorithm can handle all the cases under both scenarios without overflows but at the expense of increased computational complexity when the value of i approaches the maximum value of the
underlying integer type. The results also highlight the tradeoff between the bounded compensation errors and lower space complexity of the integer-based decomposition algorithms and the lower chances of overflows resulting from the wide ranges of numbers of the clock skew compensation based on floatingpoint arithmetic. Of the two algorithms, the results of the analysis of computational complexities and non-overflow conditions show that the direct search algorithm can better exploit the trade-off between space and time complexity in obtaining the nearest integer solution to integer linear scaling through additive ˜ n in (17) of decomposition. Given the sequential nature of ∆ Theorem 4, however, the parallelization of the additive decomposition of direct search algorithm is not straightforward, which is an interesting topic for further research together with an alternative setting of an initial guess of the solution (i.e., k0 in Algorithm 1) to avoid an overflow given the values of i, D, and A.
9
TABLE V C LOCK SKEW COMPENSATION BASED ON INTEGER LINEAR SCALING ROUNDED TO THE NEAREST INTEGER WITH 64- BIT INTEGERS AND D=1×1012 . i
Algorithm
Compensation error*
N Min.
Notes
Max.
Avg.
Quadruple precision (binary128)†
1×1010 1×1011 1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – – – –
Double precision (binary64)†
1×1010 1×1011 1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – – – –
0 0 0 −1.0000 −1.0000 −1.0000 −1.0000 1.0000 −8.3000×101
0 0 0 0 0 0 1.0000 1.7000×101 4.4000×101
0 0 0 −5.0650×10−3 −4.9660×10−3 −5.4861×10−2 4.0231×10−1 9.1050 −1.9741×101
– – – – – – – – –
Single precision (binary32)†
1×1010 1×1011 1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – – – –
−5.4000×102 −3.8040×103 −2.3943×104 −3.6194×105 −8.8637×106 −4.8585×107 −1.4219×109 −7.9438×109 −7.9025×1010
9.9600×102 8.9730×103 4.8410×104 1.1916×106 4.0356×106 7.3491×107 1.2857×108 5.6568×109 4.9332×1010
2.2672×102 2.4693×103 1.1400×104 4.3032×105 −2.4610×106 1.1034×107 −6.2788×108 −1.4239×109 −1.5484×1010
– – – – – – – – –
Multiplicative decomposition of fixed-point division (Theorem 2)
1×1010 1×1011 1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
– – – – – – – – –
– – – – – – – – –
– – – – – – – – –
– – – – – – – – –
Overflow Overflow Overflow Overflow Overflow Overflow Overflow Overflow Overflow
Additive decomposition of direct search (Theorem 4)
1×1010 1×1011 1×1012 1×1013 1×1014 1×1015 1×1016 1×1017 1×1018
1 1×101 1×102 1×103 1×104 1×105 1×106 1×107 1×108
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
– – – – – – – – –
0 0 0 0 0 0 0 0 0
– – – – – – – –
* With respect to ⌊ fp(i D )+0.5⌋ based on binary512 of IEEE 754-2008 [13, Table III]. A † ⌊ fp(i D )+0.5⌋ based on the corresponding precision. A
If b<0.5, j becomes a. Also,
A PPENDIX A P ROOF OF L EMMA 2
j−i Let a and b denote the integer and the fractional part of i D A such that i D A =a+b where a∈N0 , b∈R, and 0≤b<1. Suppose that there exists k∈N0 such that k=j+l, where l∈N and |l|≥1, and
D = |a − (a + b)| = |b| < 0.5, A
and k−i
D = |(a + l) − (a + b)| = |l − b| > 0.5. A
Therefore, D D j−i > k−i . A A
(18)
j−i
D D < k−i . A A
(19)
10
If b≥0.5, on the other hand, j becomes a+1. Also, j−i
we have from Lemma 1
D = |(a + 1) − (a + b)| = |1 − b| ≤ 0.5, A
|jA − iD| ≤ |k0 A − iD| = 0, which results in j=k0 .
and k−i
D = |(a + 1 + l) − (a + b)| = |1 + l − b| ≥ 0.5. A
Therefore,
D D j−i ≤ k−i . A A
(20)
(19) and (20) contradict the assumption of the existence of k satisfying (18). Therefore, j satisfies (6) and is the nearest integer solution to i D A.
(21)
where q=⌊ Ai ⌋ and r=i mod A. Multiplying both sides of (21) by D A , we obtain D i rD (i mod A)D i = qD + = D+ . (22) A A A A Applying (22) to (9) of Lemma 2, the nearest integer solution j is given by i (i mod A)D j= D+ + 0.5 A A $ % (i mod A)D + A2 i D+ = (23) A A $ % (i mod A) D + A2 i = D+ , A A where the last step (i.e., A2 →⌊ A2 ⌋ in the numerator) is from the special property of the floor function [21, Eq. (3.11)]. A PPENDIX C P ROOF OF T HEOREM 3 Given the objective function f (x)=|x−i D A |, we can decrease its value by decreasing x as far as x>i D A or increasing x as far as x<i D A . Because x is constrained to be an integer, there could be at most two integer values of x minimizing f (x) around x=i D A . Therefore, if we start the minimization from either side of x=i D A and cannot decrease any further the value D of f (x) by decreasing (i.e., x>i D A ) or increasing (i.e., x<i A ) x, it means that we have reached the value of x minimizing f (x), which is a termination criterion for Algorithm 1. Having the termination criterion in mind, therefore, we consider each case of Algorithm 1: Case 1: This is a special case of Lemma 1, where rhs of (7) is zero. Because
(24)
where q=⌊ |∆A0 | ⌋ and r=|∆0 | mod A according to the division algorithm. Case 2: Because ∆0 >0, we have ∆0 = k0 − q, (25) k1 = k0 − A = (k0 A − iD) − Aq = (k0 − q)A − iD
According to the theorem of division algorithm (also called Euclid’s division lemma) [20, Theorem 2.1], there exist unique integers q, r∈N0 such that
∆0 = (k0 A − iD) = 0,
|∆0 | = Aq + r,
∆1 = ∆0 mod A = r = ∆0 − Aq
A PPENDIX B P ROOF OF T HEOREM 2
i = Aq + r,
When ∆0 ̸=0, there exist unique integers q, r∈N0 such that
(26)
= k1 A − iD.
Because r=∆1 <A, we could obtain the minimum value of rhs of (7) by comparing |∆1 | and |∆1 −A|. If |∆1 −A|<|∆1 |, it suffices to show that |∆1 −A| is the rhs of (7) corresponding to k1 −1, that is, |∆1 − A| = |(k1 A − iD) − A| = |(k1 − 1)A − iD| . Because |∆1 −A| is the minimum value of rhs of (7), k1 −1 is j according to Lemma 1 (Case 2.1). Otherwise, k1 is j (Case 2.2). Case 3: Because ∆0 <0, we have ∆0 k1 = k0 − = k0 + q, (27) A ∆1 = −(|∆0 | mod A) = −r = ∆0 + Aq
= (k0 A − iD) + Aq = (k0 + q)A − iD
(28)
= k1 A − iD.
Because r=−∆1 <A, we could obtain the minimum value of rhs of (7) by comparing |∆1 | and |∆1 +A|. If |∆1 +A|<|∆1 |, it suffices to show that |∆1 +A| is the rhs of (7) corresponding to k1 +1, that is, |∆1 + A| = |(k1 A − iD) + A| = |(k1 + 1)A − iD| . Because |∆1 +A| is the minimum value of rhs of (7), k1 +1 is j according to Lemma 1 (Case 3.1). Otherwise, k1 is j (Case 3.2). A PPENDIX D P ROOF OF L EMMA 3 ˜ 1 )=j−j1 . If suffices to show that ds(i2 , D, A, κ2 , ∆ ˜ 1 ) is identical to In fact, ∆0 in line 2 of ds(i2 , D, A, κ2 , ∆ ˜ that of ds(i, D, A, κ2 +j1 , 0); because ∆1 =j1 A−i1 D, ∆0 in line 2 is given by ˜1 ∆0 = (κ2 − i2 )A + i2 (A − D) + ∆ ˜1 = (κ2 A − i2 D) + ∆ = (κ2 A − i2 D) + (j1 A − i1 D) = (κ2 + j1 )A − (i1 + i2 )D
= (κ2 + j1 )A − iD.
(29)
11
The only internal difference between two function calls ˜ 1 ) and ds(i, D, A, κ2 +j1 , 0) is the value of ds(i2 , D, A, κ2 , ∆ k0 (i.e., κ2 vs. κ2 +j1 ) from line 4 and on, which determines the return value directly (i.e., line 4) or indirectly through k1 (i.e., lines 9, 12, 18, and 21). As the value of k0 does not affect the conditional processing, which depends only on the value of ∆0 and ∆1 , the return value between the two function calls differs by j1 . As ds(i, D, A, κ2 +j1 , 0) returns j, ds(i2 , D, A, κ2 , ∆1 ) returns j−j1 . A PPENDIX E P ROOF OF T HEOREM 4 The base case of N =1 holds by Theorem Pl 3. Assume that (16) and (17) give ǰl = n=1 jn , the nearest Pl ˇ integer solution to ǐl D n=1 in , and ∆l , the value A , where ǐl = of ǰl A−ǐl D, for an integer l≥1. Based on Lemma 3, we can obtain ǰl+1 , the nearest integer solution to ǐl+1 D A , where Pl+1 ˇ l+1 , the value of ǰl+1 A−ǐl+1 D, as ǐl+1 = n=1 in , and ∆ follows: l+1 X ǰl+1 = ǰl + jl+1 = jn , (30) n=1 ˜ ˜ ∆l+1 = ∆l+1 , where ˜ l ) = ds(ǐl , D, A, κ̌l , 0), (ǰl , ∆ (31) ˜ l+1 ) = ds(il+1 , D, A, κl+1 , ∆ ˜ l ), (jl+1 , ∆ Pl and κ̌l = n=1 κn and κl+1 ∈N0 are the initial guesses of ǰl and jl+1 , respectively. Therefore, (16)P and (17) give j, the nearest integer solution N to i D , where i= n=1 in , and ∆=jA−iD for every integer A N ≥1 by mathematical induction. R EFERENCES [1] K. S. Kim and S. Kang, “Clock skew compensation algorithm immune to floating-point precision loss,” IEEE Commun. Lett., vol. 26, no. 4, pp. 902–906, Apr. 2022. [2] J. E. Bresenham, “Algorithm for computer control of a digital plotter,” IBM Systems Journal, vol. 4, no. 1, pp. 25–30, 1965. [3] S. Kang and K. S. Kim, “Theoretical and practical bounds on the initial value of clock skew compensation algorithm immune to floating-point precision loss for resource-constrained wireless sensor nodes,” Fiber and Integrated Optics, vol. 43, no. 3, pp. 111–121, Jun. 2024. [Online]. Available: https://arxiv.org/abs/2208.11520
[4] C.-P. Jeannerod and S. M. Rump, “On relative errors of floatingpoint operations: Optimal bounds and applications,” Mathematics of computation, vol. 87, no. 310, pp. 803–819, 2018. [Online]. Available: http://hdl.handle.net/11420/2654 [5] P. Marti and A. Velasco, “Memory architecture for parallel line drawing based on non incremental algorithm,” in Proc. EUROMICRO 2000, vol. 1. Maastricht, Netherlands: IEEE Comput. Soc, 2000, pp. 266–273. [6] M. Pitteway, “On some pel level research problems,” in Proc. IV’97, London, UK, Aug. 1997, pp. 156–164. [7] M. Bostock, V. Ogievetsky, and J. Heer, “D3: Data-driven documents,” IEEE Trans. Vis. Comput. Graphics, vol. 17, no. 12, pp. 2301–2309, 2011. [8] FSW (flight software) group. LAT flight software. Accessed: May 03, 2026. [Online]. Available: https://s3df.slac.stanford.edu/data/fermi/ flight/web//FSW_home.shtml [9] P. Liu, C. Li, N. Zhang, J. Yang, and L. Wang, “Efficient integer quantization for compressed DETR models,” Entropy, vol. 27, no. 4, 2025, (article number: 422). [10] Y. Hu, J. Zuo, E. Zhang, B. Iannucci, and C. Joe-Wong, “Tin-Tin: Towards tiny learning on tiny devices with integer-based neural network training,” ArXiv e-prints, Apr. 2025. [11] H. Wu, P. Judd, X. Zhang, M. Isaev, and P. Micikevicius, “Integer quantization for deep learning inference: Principles and empirical evaluation,” ArXiv e-prints, Apr. 2020. [12] X. Huan and K. S. Kim, “On the practical implementation of propagation delay and clock skew compensated high-precision time synchronization schemes with resource-constrained sensor nodes in multi-hop wireless sensor networks,” Computer Networks, vol. 166, pp. 1–8, Jan. 2020. [13] S. Kang and K. S. Kim, “Theoretical and practical bounds on the initial value of clock skew compensation algorithm immune to floating-point precision loss for resource-constrained wireless sensor nodes,” in Proc. FOAN 2023, Ghent, Belgium, Oct. 2023, pp. 12–16. [14] Y.-C. Wu, Q. Chaudhari, and E. Serpedin, “Clock synchronization of wireless sensor networks,” IEEE Signal Process. Mag., vol. 28, no. 1, pp. 124–138, 2011. [15] K. S. Kim, S. Lee, and E. G. Lim, “Energy-efficient time synchronization based on asynchronous source clock frequency recovery and reverse two-way message exchanges in wireless sensor networks,” IEEE Trans. Commun., vol. 65, no. 1, pp. 347–359, Jan. 2017. [16] S. P. Chepuri, R. T. Rajan, G. Leus, and A.-J. van der Veen, “Joint clock synchronization and ranging: Asymmetrical time-stamping and passive listening,” IEEE Signal Process. Lett., vol. 20, no. 1, pp. 51–54, Jan. 2013. [17] K. S. Kim, “Asynchronous source clock frequency recovery through aperiodic packet streams,” IEEE Commun. Lett., vol. 17, no. 7, pp. 1455– 1458, Jul. 2013. [18] IEEE Computer Society, IEEE Std 754™-2008, IEEE Standard for floating-point arithmetic, Std., Aug. 2008. [19] R. Yates, “Fixed-point arithmetic: An introduction,” Digital Signal Labs, Tech. Rep., Sep. 2020, technical reference. [20] D. M. Burton, Elementary number theory, 7th ed. Boston: McGrawHill, Higher Education, 2010. [21] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics: A foundation for computer science, 2nd ed. Addison-Wesley Professional, Feb. 1994.