| Hosted by CoCalc | Download
n = var('n')
l = var('l')
g1 = var('g1')
g2 = var('g2')
r = var('r')

restriction_g1 = (g1 >= n/2, g1 >= n - l)
restriction_r = ( 2*r <=l)
restrictions = (g1 >= n/2, g1 >= n - l, 2*r <= l)

Phase1 = l
Phase2 = 2 * n - g1 - l
Phase3_1 = g2
Phase3_2 = (3 * g1 - n - 2 * r) + (r + n - g2)
Phase3_3 = n/2 + 2 * r

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1)
show('Phase 2: ', Phase2)
show('Phase 3 term 1: ', Phase3_1.simplify_full())
show('Phase 3 term 2: ', Phase3_2.simplify_full())
show('Phase 3 term 3: ', Phase3_3.simplify_full())
show('--------------------------------------------------------------------')

g2s = solve([Phase3_1 == Phase3_2], g2)[0]
show('--------------------------------------------------------------------')
show('Balance the first two terms in Phase 3 by setting: ')
show(g2s)
g2s = g2s.rhs()

Phase3_1  = Phase3_1(g2 = g2s)
Phase3_2 = Phase3_2(g2 = g2s)

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1)
show('Phase 2: ', Phase2)
show('Phase 3 term 1: ', Phase3_1.simplify_full())
show('Phase 3 term 2: ', Phase3_2.simplify_full())
show('Phase 3 term 3: ', Phase3_3.simplify_full())

g1s, rs = solve([Phase2 == Phase3_1 , Phase3_1 == Phase3_3], g1, r)[0]
show('--------------------------------------------------------------------')
show('Balance Phase 2, Phase 3 term 1 and Phase 3 term 2 by setting:')
show(g1s)
show(rs)
g1s = g1s.rhs()
rs = rs.rhs()
show('This balance only valid under the restrictions: ')
show(restrictions)
show('Which implies: ')
bound_l = solve([g1s >= n - l, g1s >= n/2, rs <= l/2, l < n], l)[-1]
bound_l_ = (bound_l[0], bound_l[1])
show(bound_l_)

Phase1_case1 = Phase1(g1 = g1s)
Phase2_case1 = Phase2(g1 = g1s)
Phase3_1_case1 = Phase3_1(g1 = g1s, r = rs)
Phase3_2_case1 = Phase3_2(g1 = g1s, r = rs)
Phase3_3_case1 = Phase3_3(g1 = g1s, r = rs)

show('--------------------------------------------------------------------')
show('For the case')
show(bound_l_)
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1_case1)
show('Phase 2: ', Phase2_case1)
show('Phase 3 term 1: ', Phase3_1_case1.simplify_full())
show('Phase 3 term 2: ', Phase3_2_case1.simplify_full())
show('Phase 3 term 3: ', Phase3_3_case1.simplify_full())
show('--------------------------------------------------------------------')

ls = solve([Phase1_case1 == Phase2_case1], l)[0]
show('The optimal complexity is (log2):')
show('Phase1: ', Phase1_case1(l = ls.rhs()).simplify_full())
show('Phase2: ', Phase2_case1(l = ls.rhs()).simplify_full())
show('Phase 3, term 1:', Phase3_1_case1(l = ls.rhs()).simplify_full())
show('Phase 3, term 2:', Phase3_2_case1(l = ls.rhs()).simplify_full())
show('Phase 3, term 3:', Phase3_3_case1(l = ls.rhs()).simplify_full())
show('Obtained for ')
show(ls)
show('--------------------------------------------------------------------')

bound_l_low = (bound_l[0].rhs() <= bound_l[0].lhs())
rs = (r == l/2)
Phase1_case2 = Phase1(r = l / 2)
Phase2_case2 = Phase2(r = l / 2)
Phase3_1_case2 = Phase3_1(r = l / 2)
Phase3_2_case2 = Phase3_2(r = l / 2)
Phase3_3_case2 = Phase3_3(r = l / 2)

show('--------------------------------------------------------------------')
show('For the case')
show(bound_l_low)
show('Set: ', rs)
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1_case2)
show('Phase 2: ', Phase2_case2)
show('Phase 3 term 1: ', Phase3_1_case2.simplify_full())
show('Phase 3 term 2: ', Phase3_2_case2.simplify_full())
show('Phase 3 term 3: ', Phase3_3_case2.simplify_full())

g1s = solve([Phase2_case2 == Phase3_1_case2], g1)[0]
show('--------------------------------------------------------------------')
show('Balance Phase 2 and Phase 3 term 1 by setting:')
show(g1s)
g1s = g1s.rhs()
show('This balance only valid under the restriction: ')
show(restriction_g1)
show('Which implies: ')
bound_l = solve([g1s >= n - l, g1s >= n/2, l < n], l)[-1]
show(bound_l[0])

Phase2_case2 = Phase2_case2(g1 = g1s )
Phase3_1_case2 = Phase3_1_case2(g1 = g1s )
Phase3_2_case2 = Phase3_2_case2(g1 = g1s )
Phase3_3_case2 = Phase3_3_case2(g1 = g1s )

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1_case2)
show('Phase 2: ', Phase2_case2)
show('Phase 3 term 1: ', Phase3_1_case2.simplify_full())
show('Phase 3 term 2: ', Phase3_2_case2.simplify_full())
show('Phase 3 term 3: ', Phase3_3_case2.simplify_full())
show('--------------------------------------------------------------------')
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: −g1−l+2 n\displaystyle -g_{1} - l + 2 \, n
Phase 3 term 1: g2\displaystyle g_{2}
Phase 3 term 2: 3 g1−g2−r\displaystyle 3 \, g_{1} - g_{2} - r
Phase 3 term 3: 12 n+2 r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
--------------------------------------------------------------------
Balance the first two terms in Phase 3 by setting:
g2=32 g1−12 r\displaystyle g_{2} = \frac{3}{2} \, g_{1} - \frac{1}{2} \, r
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: −g1−l+2 n\displaystyle -g_{1} - l + 2 \, n
Phase 3 term 1: 32 g1−12 r\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r
Phase 3 term 2: 32 g1−12 r\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{2} \, r
Phase 3 term 3: 12 n+2 r\displaystyle \frac{1}{2} \, n + 2 \, r
--------------------------------------------------------------------
Balance Phase 2, Phase 3 term 1 and Phase 3 term 2 by setting:
g1=−511 l+1922 n\displaystyle g_{1} = -\frac{5}{11} \, l + \frac{19}{22} \, n
r=−311 l+722 n\displaystyle r = -\frac{3}{11} \, l + \frac{7}{22} \, n
This balance only valid under the restrictions:
(g1≥12 n\displaystyle g_{1} \geq \frac{1}{2} \, n, g1≥−l+n\displaystyle g_{1} \geq -l + n, 2 r≤l\displaystyle 2 \, r \leq l)
Which implies:
(717 n<l\displaystyle \frac{7}{17} \, n < l, l<45 n\displaystyle l < \frac{4}{5} \, n)
--------------------------------------------------------------------
For the case
(717 n<l\displaystyle \frac{7}{17} \, n < l, l<45 n\displaystyle l < \frac{4}{5} \, n)
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: −611 l+2522 n\displaystyle -\frac{6}{11} \, l + \frac{25}{22} \, n
Phase 3 term 1: −611 l+2522 n\displaystyle -\frac{6}{11} \, l + \frac{25}{22} \, n
Phase 3 term 2: −611 l+2522 n\displaystyle -\frac{6}{11} \, l + \frac{25}{22} \, n
Phase 3 term 3: −611 l+2522 n\displaystyle -\frac{6}{11} \, l + \frac{25}{22} \, n
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: 2534 n\displaystyle \frac{25}{34} \, n
Phase2: 2534 n\displaystyle \frac{25}{34} \, n
Phase 3, term 1: 2534 n\displaystyle \frac{25}{34} \, n
Phase 3, term 2: 2534 n\displaystyle \frac{25}{34} \, n
Phase 3, term 3: 2534 n\displaystyle \frac{25}{34} \, n
Obtained for
l=2534 n\displaystyle l = \frac{25}{34} \, n
--------------------------------------------------------------------
--------------------------------------------------------------------
For the case
l≤717 n\displaystyle l \leq \frac{7}{17} \, n
Set: r=12 l\displaystyle r = \frac{1}{2} \, l
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: −g1−l+2 n\displaystyle -g_{1} - l + 2 \, n
Phase 3 term 1: 32 g1−14 l\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{4} \, l
Phase 3 term 2: 32 g1−14 l\displaystyle \frac{3}{2} \, g_{1} - \frac{1}{4} \, l
Phase 3 term 3: l+12 n\displaystyle l + \frac{1}{2} \, n
--------------------------------------------------------------------
Balance Phase 2 and Phase 3 term 1 by setting:
g1=−310 l+45 n\displaystyle g_{1} = -\frac{3}{10} \, l + \frac{4}{5} \, n
This balance only valid under the restriction:
(g1≥12 n\displaystyle g_{1} \geq \frac{1}{2} \, n, g1≥−l+n\displaystyle g_{1} \geq -l + n)
Which implies:
27 n<l\displaystyle \frac{2}{7} \, n < l
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l\displaystyle l
Phase 2: −710 l+65 n\displaystyle -\frac{7}{10} \, l + \frac{6}{5} \, n
Phase 3 term 1: −710 l+65 n\displaystyle -\frac{7}{10} \, l + \frac{6}{5} \, n
Phase 3 term 2: −710 l+65 n\displaystyle -\frac{7}{10} \, l + \frac{6}{5} \, n
Phase 3 term 3: l+12 n\displaystyle l + \frac{1}{2} \, n
--------------------------------------------------------------------