---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework5 (quiz5)
contributed by < `johnnycck` >
> [第 5 週測驗題](https://hackmd.io/@sysprog/2020-quiz5)
## 測驗 `1`
### 題目
```c=
#include <stdio.h>
#include <stdlib.h>
double divop(double orig, int slots) {
if (slots == 1 || orig == 0)
return orig;
int od = slots & 1;
double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1);
if (od)
result += divop(result, slots);
return result;
}
```
## 延伸問題1-1：
解釋上述程式碼運作原理
### 思考流程
1. 使用 od = slots & 1 得到 slots(除數) 是否為奇數
2. 再來會看到使用遞迴的方法完成除法，因此可以猜到 orig / D1 想表達的是被除數每次都除以2，所以 `D1 = (c) 2`
3. 若 slots 為奇數，會將放入遞迴的除數設為：(slots + D2) >> 1，在這裡不難推斷出 `D2 = (d) 1`，因為奇數要 + 1 後再位移
### 程式邏輯
* 如果除數是偶數，那將被除數 /2 後再將除數右移 1 位放入遞迴中，就會是正確結果
* 但若除數是奇數，那將被除數 /2 後再將除數 + 1 後右移 1 位放入遞迴中，這樣結果會比正確答案來的小，因此要在第 9~10 行把結果加回來，參考以下數學式：
$$
\begin{align}
\frac{a}{b} =& \frac{a}{b+1}\frac{b+1}{b} \\
=& \frac{a}{b+1}(1+\frac{1}{b}) \\
=& \frac{\frac{a}{2}}{\frac{b+1}{2}} + \frac{\frac{a}{2}}{\frac{b+1}{2}} \frac{1}{b}
\end{align}
$$
* 所以我們要補加回來的部份就是 $\frac{\text{result}}{b}$ 也就是 `divop(result, slot)`
## 延伸問題 1-2：
以編譯器最佳化的角度，推測上述程式碼是否可透過 [tail call optimization](https://en.wikipedia.org/wiki/Tail_call) 進行最佳化，搭配對應的實驗
搭配閱讀 [C 語言: 編譯器和最佳化原理](https://hackmd.io/s/Hy72937Me) 及 [C 語言: 遞迴呼叫](https://hackmd.io/s/rJ8BOjGGl)
### 思考流程
### divop.c 組合語言
程式碼是否有做 tail call optimization 最佳化可以直接從組合語言得知，傳統的遞迴會執行 "call divop" 此動作，因此以下列出有無執行編譯器最佳化的組合語言來做比較，指令分別是 gcc -S -O0 -o divop_O0 divop.c 跟 gcc -S -O3 -o divop_O3 divop.c
* gcc -S -O0
```clike=
.file "divop.c"
.text
.globl divop
.type divop, @function
divop:
.LFB6:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $48, %rsp
movsd %xmm0, -24(%rbp)
movl %edi, -28(%rbp)
cmpl $1, -28(%rbp)
je .L2
pxor %xmm0, %xmm0
ucomisd -24(%rbp), %xmm0
jp .L3
pxor %xmm0, %xmm0
ucomisd -24(%rbp), %xmm0
jne .L3
.L2:
movsd -24(%rbp), %xmm0
jmp .L5
.L3:
movl -28(%rbp), %eax
andl $1, %eax
movl %eax, -12(%rbp)
cmpl $0, -12(%rbp)
je .L6
movl -28(%rbp), %eax
addl $1, %eax
sarl %eax
jmp .L7
.L6:
movl -28(%rbp), %eax
sarl %eax
.L7:
movsd -24(%rbp), %xmm0
movsd .LC1(%rip), %xmm1
divsd %xmm1, %xmm0
movl %eax, %edi
call divop // 第一個遞迴呼叫
movq %xmm0, %rax
movq %rax, -8(%rbp)
cmpl $0, -12(%rbp)
je .L8
movl -28(%rbp), %edx
movq -8(%rbp), %rax
movl %edx, %edi
movq %rax, -40(%rbp)
movsd -40(%rbp), %xmm0
call divop // 第二個遞迴呼叫
movapd %xmm0, %xmm1
movsd -8(%rbp), %xmm0
addsd %xmm1, %xmm0
movsd %xmm0, -8(%rbp)
.L8:
movsd -8(%rbp), %xmm0
.L5:
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE6:
.size divop, .-divop
.section .rodata
.align 8
.LC1:
.long 0
.long 1073741824
.ident "GCC: (Ubuntu 7.5.0-6ubuntu2) 7.5.0"
.section .note.GNU-stack,"",@progbits
```
可以發現，GCC 沒有進行最佳化的情況下，只是單純的把 c 轉換成組合語言，而上面的組合語言中，單純的跟原始碼一樣做了兩次遞迴呼叫
* gcc -S -O3
```clike=
.file "divop.c"
.text
.p2align 4,,15
.globl divop
.type divop, @function
divop:
.LFB39:
.cfi_startproc
cmpl $1, %edi
movapd %xmm0, %xmm1
je .L12
pxor %xmm2, %xmm2
sete %dl
ucomisd %xmm2, %xmm0
setnp %al
cmovne %edx, %eax
testb %al, %al
je .L16
.L12:
movapd %xmm1, %xmm0
ret
.p2align 4,,10
.p2align 3
.L16:
pushq %r12
.cfi_def_cfa_offset 16
.cfi_offset 12, -16
pushq %rbp
.cfi_def_cfa_offset 24
.cfi_offset 6, -24
movl %edi, %r12d
pushq %rbx
.cfi_def_cfa_offset 32
.cfi_offset 3, -32
movl %edi, %ebx
subq $16, %rsp
.cfi_def_cfa_offset 48
movsd .LC1(%rip), %xmm0
mulsd %xmm0, %xmm1
ucomisd %xmm2, %xmm1
setnp %dl
cmove %edx, %eax
andl $1, %r12d
je .L3
leal 1(%rdi), %ebp
sarl %ebp
cmpl $1, %ebp
je .L4
testb %al, %al
jne .L4
.L5:
testb $1, %bpl
mulsd %xmm1, %xmm0
jne .L17
movl %ebp, %edi
sarl %edi
call divop
movapd %xmm0, %xmm1
.L7:
testl %r12d, %r12d
je .L2
.p2align 4,,10
.p2align 3
.L4:
movapd %xmm1, %xmm0
movl %ebx, %edi
movsd %xmm1, 8(%rsp)
call divop
movsd 8(%rsp), %xmm1
addsd %xmm0, %xmm1
jmp .L2
.p2align 4,,10
.p2align 3
.L3:
movl %edi, %ebp
sarl %ebp
cmpl $1, %ebp
je .L2
testb %al, %al
je .L5
.L2:
addq $16, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 32
movapd %xmm1, %xmm0
popq %rbx
.cfi_def_cfa_offset 24
popq %rbp
.cfi_def_cfa_offset 16
popq %r12
.cfi_def_cfa_offset 8
ret
.p2align 4,,10
.p2align 3
.L17:
.cfi_restore_state
leal 1(%rbp), %edi
sarl %edi
call divop
movl %ebp, %edi
movsd %xmm0, 8(%rsp)
call divop
movsd 8(%rsp), %xmm1
addsd %xmm0, %xmm1
jmp .L7
.cfi_endproc
.LFE39:
.size divop, .-divop
.section .rodata.cst8,"aM",@progbits,8
.align 8
.LC1:
.long 0
.long 1071644672
.ident "GCC: (Ubuntu 7.5.0-6ubuntu2) 7.5.0"
.section .note.GNU-stack,"",@progbits
```
* 在此解說 O3 下組合語言的流程
- 原先在 O0 下組合語言只有出現 2 次 "call divop"，這是因為編譯器單純將 c code 轉換成對應的組合語言
- O3 下出現了 4 次 "call divop"，這是因為它將步驟進行優化，依照 od 是否為 '0'，來區分兩種處理的模式
- 若編譯器判斷 od 為 '0'，則先執行第一次的 call divop 呼叫(.L5)，執行後再檢查一次 od 是否為 '0'，若是，則直接回傳，若不是，則執行 "result += divop(result, slots)"(.L4)，進行第二次 "call divop"
- 若 od 為 '1'，則編譯器將 "divop(orig / D1, (slots + 1) >> 1 )" 跟 "result += divop(result, slots)" 放在同一個 block 操作，也就是 .L17
* 由以上編譯器追蹤的結果，可以發現**並沒有執行 "tail recursive 的優化"**
## 測驗 `2`
### 題目
:::spoiler
```c=
#include <stdint.h>
/* A union allowing us to convert between a float and a 32-bit integers.*/
typedef union {
float value;
uint32_t v_int;
} ieee_float_shape_type;
/* Set a float from a 32 bit int. */
#define INSERT_WORDS(d, ix0) \
do { \
ieee_float_shape_type iw_u; \
iw_u.v_int = (ix0); \
(d) = iw_u.value; \
} while (0)
/* Get a 32 bit int from a float. */
#define EXTRACT_WORDS(ix0, d) \
do { \
ieee_float_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.v_int; \
} while (0)
static const float one = 1.0, tiny = 1.0e-30;
float ieee754_sqrt(float x)
{
float z;
int32_t sign = 0x80000000;
uint32_t r;
int32_t ix0, s0, q, m, t, i;
EXTRACT_WORDS(ix0, x);
/* take care of zero */
if (ix0 <= 0) {
if ((ix0 & (~sign)) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
/* take care of +INF and NaN */
if ((ix0 & 0x7f800000) == 0x7f800000) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
return x;
}
/* normalize x */
m = (ix0 >> 23);
if (m == 0) { /* subnormal x */
for (i = 0; (ix0 & 0x00800000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
}
m -= 127; /* unbias exponent */
ix0 = (ix0 & 0x007fffff) | 0x00800000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0;
q = s0 = 0; /* [q] = sqrt(x) */
r = 0x01000000; /* r = moving bit from right to left */
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0;
r >>= 1;
}
/* use floating add to find out rounding direction */
if (ix0 != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (z > one)
q += 2;
else
q += (q & 1);
}
}
ix0 = (q >> 1) + 0x3f000000;
ix0 += (m << 23);
INSERT_WORDS(z, ix0);
return z;
}
```
:::
## 延伸問題 2-1：
解釋上述程式碼何以運作
搭配研讀 [以牛頓法求整數開二次方根的近似值](http://science.hsjh.chc.edu.tw/upload_works/106/44f6ce7960aee6ef868ae3896ced46eb.pdf) (第 19 頁)
### 程式碼解析
```clike=
/* A union allowing us to convert between a float and a 32-bit integers.*/
typedef union {
float value;
uint32_t v_int;
} ieee_float_shape_type;
```
- union 的結構特性讓結構中的各變數是共用記憶體位置
- 因此 `ieee_float_shape_type` 可以把一段 IEEE 754 編碼的 float，轉換成 uint32_t 來達成 float 跟 uint32_t 的轉換
```clike=
/* Set a float from a 32 bit int. */
#define INSERT_WORDS(d, ix0) \
do { \
ieee_float_shape_type iw_u; \
iw_u.v_int = (ix0); \
(d) = iw_u.value; \
} while (0)
/* Get a 32 bit int from a float. */
#define EXTRACT_WORDS(ix0, d) \
do { \
ieee_float_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.v_int; \
} while (0)
```
- `INSERT_WORDS(d, ix0)` 能將型態為 `float` 的 'd' 轉成型態為 `int` 的 'ix0'
- `EXTRACT_WORDS(ix0, d)` 能將型態為 `int` 的 'ix0'轉成型態為 `float` 的 'd'
* 參考 IEEE 754 規範
-- [src](https://hackmd.io/@sysprog/c-floating-point)
- 首先將傳入的 `float x` 透過 EXTRACT_WORDS(ix0, x) 轉換成 `int` 型態
- 若是 ix0 <=0 且 ix0 & (~sign) == 0，代表除了 sign bit 之外都是 0，這樣子的浮點數可能為 +-0，開根號會是自己，因此回傳 x
- 若是進入 ix0 < 0 這個判斷式，代表 x 並非 0，則代表是負浮點數，負浮點數無法開根號，因此回傳 (x-x)/(x-x)，代表 NaN
```clike=
int32_t sign = 0x80000000;
EXTRACT_WORDS(ix0, x);
/* take care of zero */
if (ix0 <= 0) {
if ((ix0 & (~sign)) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
```
- 剛剛已經排除 +-0 跟負浮點數的情況，在此透過 ix0 & 0x7f800000 == 0x7f800000 來判斷浮點數是否為 +infinity 或 NaN，如果成立，則回傳 x，因為 +infinity 跟 NaN 開根號都是得到自己
```clike=
/* take care of +INF and NaN */
if ((ix0 & 0x7f800000) == 0x7f800000) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
return x;
}
```
- 目前已經排除 +-0 ,負浮點數, +INF, NaN 等特殊狀況，接下來考慮 denormalize number 的狀況
- 透過右移 23 位，m 只有保留 sign bit + exponent bits(9 bits)
- 如果 m==0，因為在前面已經排除浮點數是 0 的情況，因此代表此浮點數是 denormalize number，此浮點數是 $0.x * 2^{-126}$，denormalize number 的處理方式是要將 $0.x * 2^{-126}$ 變成 $1.Fraction * 2^{exponent}$ 這種 normalize number 的方式
- 透過 for loop，將 ix0 做左移，直到 exponent 位元 > 0 (此步驟讓 0.x 變成 $1.Fraction$
- m-= i-1 ( 此步驟以 'i' 記錄位移量，又因為原先 denormalize 表示法 exponent 是 -126，在此要 m+1-i 才會正確
- m-=127，得到 IEEE 規範中的 exponent
- ix0 保留 Fraction ，並在 exponent 的最低位加入 1，表達 $1.Fraction * 2^{exponent}$
- 因為目標是求 x 的根號，$1.Fraction * 2^{exponent}$ 開根號會是 $\sqrt{1.Fraction} * 2^{exponent/2}$
- 如果 m 是奇數，讓 $1.Fraction * 2^{exponent}$ * 2，變成 $2.Fraction * 2^{exponent-1}$
- m >>= 1，表達 exponent/2
```clike=
/* normalize x */
m = (ix0 >> 23);
if (m == 0) { /* subnormal x */
for (i = 0; (ix0 & 0x00800000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
}
m -= 127; /* unbias exponent */
ix0 = (ix0 & 0x007fffff) | 0x00800000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0;
}
m >>= 1; /* m = [m/2] */
```
- 以上的程式碼讓目前要求的 $x * 2^{exponent}$ 的 x 落在 1<=x<4 的範圍
- 因此求 x 的根號範圍會落在 1 < $\sqrt{x}$ < 2，這樣的範圍可以允許從 1 開始往上加，並使用 q 來代表解的精度
- 在此部分參考 `RusselCK` 的推導解釋:
* Generate ${(\sqrt{x})}_2$ Bit by Bit ( 數學推導 )：
* 假設 $1 \leq x < 2^2 = 4$
* 令 $q_i={(\sqrt{x})}_2$ 到小數點後第 $i$ 位的精確值, $i \geq 0$
$\Rightarrow q_0=1$
* 考慮 $q_{i+1}$ :
* 若 ${(q_i + 2^{-(i+1)})}^2 \leq x$ ，則 $q_{i+1}= q_i + 2^{-(i+1)}$
* 即 $q_i$ 後面補 1
* 若 ${(q_i + 2^{-(i+1)})}^2 > x$ ，則 $q_{i+1} = q_i$
* 即 $q_i$ 後面補 0
* 整理 ${(q_i + 2^{-(i+1)})}^2 \leq x$：
$$
\begin{split}
{(q_i + 2^{-(i+1)})}^2 \leq x &\Rightarrow q_i^2 + 2\times q_i \times (2^{-(i+1)}) + (2^{-(i+1)})^2 \leq x \\
&\Rightarrow q_i \times (2^{-i}) + 2^{-2(i+1)} \leq x - q_i^2 \\
&\Rightarrow q_i \times 2 \space + 2^{-(i+1)} \leq [x - q_i^2] \times 2^{(i+1)} \\
&\Rightarrow s_i + r_i \leq x_i, \\
&\begin{split} where \space &s_i = 2 \times q_i, \\
&r_i = 2^{-(i+1)}, \\
&x_i = [x - q_i^2] \times 2^{(i+1)} = [x - q_i^2]r_i^{-1}
\end{split}
\end{split}
$$
* $Thus,$
* 若 $s_i + r_i \leq x_i$，則
* $q_{i+1}= q_i + r_i$
* $s_{i+1}=(s_i + r_i) + r_i$
* $x_{i+1}=2x_i - 2(s_i + r_i) = 2[x_i - (s_i + r_i)]$
:::spoiler 推導過程
$$
\begin{split}
s_{i+1} &= 2 \times q_{i+1} \\
&= 2 \times [q_i + 2^{-(i+1)}] \\
&= (2 \times q_i) + 2^{-i} \\
&= s_i + 2^{-i} \\
&= s_i + 2^{-(i+1)} + 2^{-(i+1)} \\
&= (s_i + r_i) + r_i \\
\end{split}
$$
$$
\begin{split}
x_{i+1} &=[x - q_{i+1}^2] \times 2^{((i+1)+1)} \\
&= [x - (q_i + r_i)^2] \times 2^{(i+2)} \\
&= [x - (q_i^2 + 2q_ir_i + r_i^2)] \times 2r_i^{-1} \\
&= [x - q_i^2] \times 2r_i^{-1} - 2q_ir_i \times 2r_i^{-1} - r_i^2 \times 2r_i^{-1} \\
&= 2x_i - 2s_i - 2r_i \\
&= 2x_i - 2(s_i + r_i) \\
\end{split}
$$
:::
* 若 $s_i + r_i > x_i$，則
* $q_{i+1} = q_i$
* $s_{i+1}=s_i$
* $x_{i+1}=2x_i$
:::spoiler 推導過程
$$
\begin{split}
s_{i+1} &= 2 \times q_{i+1} \\
&= 2 \times q_i \\
&= s_i \\
\end{split}
$$
$$
\begin{split}
x_{i+1} &=[x - q_{i+1}^2] \times 2^{((i+1)+1)} \\
&= [x - q_i^2] \times 2^{(i+2)} \\
&= [x - q_i^2] \times 2r_i^{-1} \\
&= 2x_i
\end{split}
$$
:::
```clike=
/* generate sqrt(x) bit by bit */
ix0 += ix0;
q = s0 = 0; /* [q] = sqrt(x) */
r = 0x01000000; /* r = moving bit from right to left */
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0;
r >>= 1;
}
```
## 延伸問題 2-3：
練習 LeetCode 69. Sqrt(x)，提交不需要 FPU 指令的實作
#### 思考流程
* Naive Solution
一開始使用 naive 的想法，因為只需要回傳 input 的 sqrt() 整數解，所以使用 for 迴圈從 2 開始往上加，而終止條件則設定為 i*i > input，此解法的壞處為錯誤次數會很多，需要許多的乘法運算，造成效能低落，也因此在 leetcode 上只贏過 23％ 的人
```c=
int mySqrt(int x){
if(x==0 || x==1)
return x;
else {
long long i;// 此處為 long long 原因是 i*i 有可能過大到超過 int 能表示的範圍
for(i=2; i*i<=x; i++);
return (i-1);
}
}
```
Leetcode 結果：
* Binary Tree Solution
原先的解法是慢慢的往上加，這個尋找 root 的過程其實類似於搜尋已排序好的遞增數列，若是套用二元搜尋的概念，就能減少錯誤的次數，進而加快搜尋速度，因此更改為二元搜尋的方式來完成，最後發現比原先解法快速很多
```c=
int mySqrt(int x){
if(x==0 || x==1)
return x;
else {
// end = x/2 因為若 x>1 的情況，floor(sqrt(x)) 不可能 > x/2
long long start = 1, end = x/2, ans;
while (start <= end)
{
long long mid = (start + end) / 2;
if (mid*mid == x)
return mid;
if (mid*mid < x)
{
start = mid + 1;
ans = mid;
}
else
end = mid-1;
}
return ans;
}
}
```
Leetcode 結果：
* 因為 memory usage 的大小只贏過 23.19% 的提交，因此把 mid 這個變數刪掉，改用 (start+end)/2 代替，最後執行時間贏過 100% 的提交，空間贏過 98.35% 的提交
```clike=
int mySqrt(int x){
if(x==0 || x==1)
return x;
else {
long start = 1, end = x/2;
while (start <= end)
{
//long long mid = ((start + end) / 2);
if (((start + end) / 2) * ((start + end) / 2) == x)
return ((start + end) / 2);
if (((start + end) / 2) * ((start + end) / 2) < x)
{
//ans = ((start + end) / 2);
start = ((start + end) / 2) + 1;
}
else
end = ((start + end) / 2)-1;
}
return (((start - 1) * 2 ) / 2);
}
}
```
* leetcode 結果
:::warning
TODO:
1. 引入快取表格，將 Sqrt 的結果保存在表格中，避免之後重複運算，並運用 cache replacement policy
2. LeetCode [146. LRU Cache](https://leetcode.com/problems/lru-cache/)
:::
---
## 測驗 `3`
### 題目
```c=
int consecutiveNumbersSum(int N)
{
if (N < 1)
return 0;
int ret = 1;
int x = N;
for (int i = 2; i < x; i++) {
x += ZZZ;
if (x % i == 0)
ret++;
}
return ret;
}
```
## 延伸問題 3-1：
解釋上述程式碼何以運作
### 思考流程
* 數學式
1.
$$
kx = N - \frac{k(k-1)}{2}
$$
-------
2.
$$
N - \frac{(k-1)k}{2} = kx
$$
* 參考 [RinHizakura](https://hackmd.io/@RinHizakura/SJnXiSewD)，將上述公式(在 k 和 x 皆為正整數的前提下，使得等號成立的整數 x 和 k 組合有多少個)，轉換概念為
$$
N - \{從 \space 0 \space 加到\space (k - 1)\space 之和\} = kx
$$
* 每次的 for 迴圈代表 N-{0 加到 k-1 之和}，因此 k 從 2 開始往上加
* 第一次 interation，x (在一開始等於 N)，會需要減掉前述：{0 加到 k-1 之和}，並透過跟 k 取餘數，得知是否有正整數解，若有，則代表 N 可由 2 個連續整數相加來表達
* 在接下來的 iteration，透過 x += (1-k)，也就是 x -= (k-1)，可以計算 N-{0 加到 k-1 之和}，直到 k>=x，代表連續 k 整數已經超過 N-{0 加到 k-1 之和}，因此結束計算
* 因此，`ZZZ = (d) 1 - i`。
回顧原程式(下面 `i` 改成 `k`，與前式子做對應)：
```c=
int consecutiveNumbersSum(int N)
{
if (N < 1)
return 0;
int ret = 1;
int x = N;
for (int k = 2; k < x; k++) {
x += (1 - k); // = x -= (k - 1)
if (x % k == 0)
ret++;
}
return ret;
}
```
## 延伸問題 3-2：
嘗試改寫為更有效率的實作
### 思考流程
* 在前述題目中，有提到迴圈的結束條件是連續 k 整數的 k，已經超過 N-{0 加到 k-1 之和}，這樣子的結束條件是可以縮小的，以之前公式可以得出
$$
\Rightarrow k< \sqrt{2N}\\
\Rightarrow k^2 < 2N\\
$$
因此將程式碼改寫為：
```c=
int consecutiveNumbersSum(int N){
if (N < 1)
return 0;
int ret = 1;
int x = N;
for (int i = 2; i*i < 2*N; i++) {
x += (1-i);
if (x % i == 0)
ret++;
}
return ret;
}
```
* 結果
Sign in with Wallet
Connect another wallet