Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Коэффициэнтларни дастлабки қайта ишлаш.
Кўпҳад коэффициэнтларини алгоритм ишидан олдинроқ қайта ишлаш орқали натижани яхшилаш мумкин. Асосий ғоя шундан иборатки, кўпҳадни тасвирлаш кичик даражали кўпҳадлар орқали бўлади. Масалан, даражани ҳисоблаш учун параграф бошидаги Evaluate функциясига ўхшаш циклли функциядан фойдаланиш мумкин. Натижада 255 та кўпайтириш бажарилади. Муқобил ёндошув шундан иборатки, result=x*x қўйилади ва операция 7 марта бажарилади. Биринчи бажаришдан сўнг ўзгарувчан result , иккинчидан кейин ни, учинчидан кейин тўртинчидан кейин ни, бешинчидан кейин ва еттинчидан сўнг ни ташкил этади.
Коэффициэнтларни дастлабки қайта ишлаш услуби ишлаши учун кўпҳадлар унимодал (яьни, катта коэффициэнт га тенг) бўлиши , кўпҳад даражаси эса бирга кам яьни ( баъзида k>1) бўлиши керак. Бу ҳолатлар кўпҳад қуйидаги кўпҳад кўринишда бўлади:
р(х)= (x^j+b)q(x)+r(х), бунда j=2^к-1
Ҳар икки кўпҳад q ва r аъзолар p га қараганда икки марта кам бўлади. Зарур натижани олиш учун q(x) ва n(x) ни алоҳида - алоҳида ҳисоблаймиз , шундан кейин битта қўшимча кўпайтириш ва иккита қўшишни бажарамиз. Агар бунда b нинг аҳамияти тўғри танланса, q ҳар икки q ва r кўпҳадлар унимодал бўлади. Ҳар бирининг даражаси уларнинг ҳар бирига ушбу процедурани қўллаш имкониятини яратади.
Шунда биз кетма – кет қўллаш ҳисоблашни татбиқ этишга олиб келганини кўрамиз. Умумий кўринишдаги кўпҳадлар тўғрисида сўз юритмасдан мисолга эътибор қаратамиз. Кўпҳадни кўриб чиқамиз:
р(х) = x⁷ + 4x⁶ – 8x⁴ + 6x³ + 9x² + 2х – 3
Аввал кўпайтирувчи х^j+b ни аниқлаштирамиз. Кўпҳад даражаси 7 ёки 2³ – 1, иш сабабли k = 3. Шундан келиб чиқадики, j=2²= 4 b нинг аҳамиятини шундай танлаймизки, ҳар икки q ва r кўпҳади унимодал бўлсин. Бунинг учун Р даги a_j-1 коэффициентни саралаш керак ва b = a_j-1-1 ни қўйиш керак. Бизнинг ҳолатда бу шуни англатадики, b=а₃-1=5. Энди биз q ва r аҳамиятни топишни истаймиз, бу қуйидаги тенгламани қондириши керак:
x⁷+4x⁶ – 8x⁴ + 6x³ + 9x² + 2х - 3 = (x⁴ + 5)q(x) + r(x)
q ва r кўпҳадларни g ни x⁴ + 5 бўлишда ҳосил бўлган алоҳида қолдиққа мос келади, қолдиқларни бўлиш эса шуни беради:
Р(х) = (x⁴ + 5)(x³ + 4x² + 0x + 8) + (x³ – 11x² + 2x - 37)
Кейинги қадамда биз худди шу процедурани ҳар бир q ва r кўпҳадларга қўллашимиз мумкин:
q(x) = (x² - 1)(x + 4)+(x+12), r(x)=(x²+1)(x-11)+(x -26)
Натижада эса қуйидагига эга бўламиз:
р(х) = (x⁴ + 5)((x² - 1)(x + 4) + (x + 12)) + ((x² + 1)(x - 11) + (x - 26))
Ушбу кўпҳадга қараб кўрамизда, x² ни ҳисоблаш учун битта кўпайтириш керак; яна бир кўпайтириш x = x²·x² ни ҳисоблаш учун зарур. Бу икки кўпайтиришлардан ташқари тенгламанинг ўнг томонини ҳисоблашда яна 3 та кўпайтириш иштирок этади.
Яна 10 та қўшиш операциялаш таъкидланади. 1 – жадвалда ушбу ҳисоблаш усули ва бошқа усулларнинг таққослов натижалари берилган.
Ушбу процедурани диққат билан ўрганиб умумий мурракаблик формуласини чиқариш мумкин. Аввало шуни кўрамизки, тенгламада битта кўпайтириш ва иккита қўшиш қатнашмоқда. Шу сабабли М=М(к) кўпайтириши ва А = А(к) қўшиш учун қуйидаги рекурент солиштирмалар боғланишини оламиз:
М(1)= 0 А(1)= 0
М(к)=2М(к-1)+1 при к >1 А(k)= 2А(k - 1) + 2 при к > 1.