n = var('n')
l = var('l')
k = var('k')
kappa = var('kappa')
g2 = var('g2')
g1 = var('g1')
restriction_g1 = (g1 >= n/2, g1 >= n - l)
Phase1 = l
Phase2 = g1 - l + k*n - k * g1
Phase3_1 = g2
Phase3_2 = k*n - (k + 1) * (n - g1) + n - g2
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('--------------------------------------------------------------------')
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 becomes (log2): ')
show('Phase2: ', Phase2)
show('Phase 3 term 1: ', Phase3_1.simplify_full())
show('Phase 3 term 2:', Phase3_2.simplify_full())
g1s = solve([Phase2 == Phase3_1], 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]
bound_l_ = (bound_l[0], bound_l[1])
show(bound_l_)
show('--------------------------------------------------------------------')
Phase1_case1 = Phase1(g1 = g1s)
Phase2_case1 = Phase2(g1 = g1s)
Phase3_1_case1 = Phase3_1(g1 = g1s)
Phase3_2_case1 = Phase3_2(g1 = g1s)
show('--------------------------------------------------------------------')
show('For the case')
show(bound_l_)
show('Complexity of Phases are (log2): ')
show('Phase 1: ', Phase1_case1.simplify_full())
show('Phase 2: ', Phase2_case1.simplify_full())
show('Phase 3 term 1: ', Phase3_1_case1.simplify_full())
show('Phase 3 term 2: ', Phase3_2_case1.simplify_full())
show('--------------------------------------------------------------------')
ls = solve([Phase1_case1 == Phase2_case1], l)[0]
Phase1_case1 = Phase1_case1 (l = ls.rhs())
Phase2_case1 = Phase2_case1 (l = ls.rhs())
Phase3_1_case1 = Phase3_1_case1 (l = ls.rhs())
Phase3_2_case1 = Phase3_2_case1 (l = ls.rhs())
show('--------------------------------------------------------------------')
show('The optimal complexity is (log2):')
show('Phase1: ', Phase1_case1.simplify_full())
show('Phase2: ', Phase2_case1.simplify_full())
show('Phase 3, term 1:', Phase3_1_case1.simplify_full())
show('Phase 3, term 2:', Phase3_2_case1.simplify_full())
show('Obtained for ')
show(ls)
show('--------------------------------------------------------------------')
for i in range(2, 4):
show(' ------------------------------ ', k == i, ' ------------------------------')
Phase1cplx = Phase1_case1(k = i)
Phase1cplxs = Phase1cplx(kappa=log(i, 2)).simplify_full()
Phase2cplx = Phase2_case1(k = i)
Phase2cplxs = Phase2cplx(kappa=log(i, 2)).simplify_full()
Phase3_1cplx = Phase3_1_case1(k = i)
Phase3_1cplxs = Phase3_1cplx(kappa=log(i, 2)).simplify_full()
Phase3_2cplx = Phase3_2_case1(k = i)
Phase3_2cplxs = Phase3_2cplx(kappa=log(i, 2)).simplify_full()
show('Phase 1: ', Phase2cplxs)
show('Phase 2: ', Phase2cplxs)
show('Phase 3 term 1: ', Phase3_1cplxs)
show('Phase 3 term 2: ', Phase3_2cplxs)
--------------------------------------------------------------------
Complexity of Phases are (log2):
Phase 1: l Phase 2: −g1k+kn+g1−l Phase 3 term 1: g2 Phase 3 term 2: g1k+g1−g2 --------------------------------------------------------------------
--------------------------------------------------------------------
Balance the first two terms in Phase 3 by setting:
g2=21g1k+21g1 --------------------------------------------------------------------
Complexity of Phases becomes (log2):
Phase2: −g1k+kn+g1−l Phase 3 term 1: 21g1k+21g1 Phase 3 term 2: 21g1k+21g1 --------------------------------------------------------------------
Balance Phase 2 and Phase 3 term 1 by setting:
g1=3k−12(kn−l) This balance only valid under the restriction:
(g1≥21n, g1≥−l+n) (31n<l, l<n) --------------------------------------------------------------------
--------------------------------------------------------------------
(31n<l, l<n) Complexity of Phases are (log2):
Phase 1: l Phase 2: −3k−1(k+1)l−(k2+k)n Phase 3 term 1: −3k−1(k+1)l−(k2+k)n Phase 3 term 2: −3k−1(k+1)l−(k2+k)n --------------------------------------------------------------------
--------------------------------------------------------------------
The optimal complexity is (log2):
Phase1: 41(k+1)n Phase2: 41(k+1)n Phase 3, term 1: 41(k+1)n Phase 3, term 2: 41(k+1)n l=41(k+1)n --------------------------------------------------------------------
------------------------------ k=2 ------------------------------ Phase 1: 43n Phase 2: 43n Phase 3 term 1: 43n Phase 3 term 2: 43n ------------------------------ k=3 ------------------------------ Phase 1: n Phase 2: n Phase 3 term 1: n Phase 3 term 2: n