| Hosted by CoCalc | Download
n = var('n')
l = var('l')
s = var('s')
t = var('t')
r = var('r')

restriction_l = (l >= n/2)
restriction_r = ( 2*r <=l)

Step1 = l
Step2 = n / 2
Step3 = n / 2 + s
Step4 = t
Step5_1 = n - t + r + n - s -2 * r - l
Step5_2 = n / 2 + 2 * r
Step6 = l

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

ts, ss, rs = solve([Step3 == Step4, Step3 == Step5_1, Step3 == Step5_2], t, s, r)[0]
show('--------------------------------------------------------------------')
show('Balance the Step 3, 4, and 5 by setting: ')
show(ts)
show(ss)
show(rs)
ts = ts.rhs()
ss = ss.rhs()
rs = rs.rhs()
show('This balance only valid under the restriction: ')
show(restriction_r)
show('Which implies: ')
bound_l = solve([rs <= l/2, l < n], l)[-1]
show(bound_l[0])

Step3  = Step3(t = ts, s = ss, r = rs)
Step4  = Step4(t = ts, s = ss, r = rs)
Step5_1  = Step5_1(t = ts, s = ss, r = rs)
Step5_2  = Step5_2(t = ts, s = ss, r = rs)

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())

ls = solve([Step1 == Step3], l)[0]

Step1 = Step1(l = ls.rhs())
Step2  = Step2(l = ls.rhs())
Step3 = Step3(l = ls.rhs())
Step4 = Step4(l = ls.rhs())
Step5_1 = Step5_1(l = ls.rhs())
Step5_2 = Step5_2(l = ls.rhs())
Step6 = Step6(l = ls.rhs())

show('--------------------------------------------------------------------')
show('The optimal complexity is (log2):')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5 term 1: ', Step5_1.simplify_full())
show('Step 5 term 2: ', Step5_2.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('Obtained for ')
show(ls)
show('--------------------------------------------------------------------')
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: l\displaystyle l
Step 2: 12 n\displaystyle \frac{1}{2} \, n
Step 3: 12 n+s\displaystyle \frac{1}{2} \, n + s
Step 4: t\displaystyle t
Step 5 term 1: −l+2 n−r−s−t\displaystyle -l + 2 \, n - r - s - t
Step 5 term 2: 12 n+2 r\displaystyle \frac{1}{2} \, n + 2 \, r
Step 6: l\displaystyle l
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the Step 3, 4, and 5 by setting:
t=−27 l+1114 n\displaystyle t = -\frac{2}{7} \, l + \frac{11}{14} \, n
s=−27 l+27 n\displaystyle s = -\frac{2}{7} \, l + \frac{2}{7} \, n
r=−17 l+17 n\displaystyle r = -\frac{1}{7} \, l + \frac{1}{7} \, n
This balance only valid under the restriction:
2 r≤l\displaystyle 2 \, r \leq l
Which implies:
29 n<l\displaystyle \frac{2}{9} \, n < l
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: l\displaystyle l
Step 2: 12 n\displaystyle \frac{1}{2} \, n
Step 3: −27 l+1114 n\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n
Step 4: −27 l+1114 n\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n
Step 5 term 1: −27 l+1114 n\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n
Step 5 term 2: −27 l+1114 n\displaystyle -\frac{2}{7} \, l + \frac{11}{14} \, n
Step 6: l\displaystyle l
--------------------------------------------------------------------
The optimal complexity is (log2):
Step 1: 1118 n\displaystyle \frac{11}{18} \, n
Step 2: 12 n\displaystyle \frac{1}{2} \, n
Step 3: 1118 n\displaystyle \frac{11}{18} \, n
Step 4: 1118 n\displaystyle \frac{11}{18} \, n
Step 5 term 1: 1118 n\displaystyle \frac{11}{18} \, n
Step 5 term 2: 1118 n\displaystyle \frac{11}{18} \, n
Step 6: 1118 n\displaystyle \frac{11}{18} \, n
Obtained for
l=1118 n\displaystyle l = \frac{11}{18} \, n
--------------------------------------------------------------------