Қосу-азайту тізбегі - Addition-subtraction chain

Ан қосу-азайту тізбегі, жалпылау қосу тізбектері азайтуды қосу, бұл а жүйелі а0, а1, а2, а3, ... қанағаттандырады

Үшін қосу-азайту тізбегі n, ұзындығы L, қосу-азайту тізбегі осындай . Яғни, сол арқылы есептеуге болады n арқылы L қосу және / немесе азайту. (Ескертіп қой n оң болмауы керек. Бұл жағдайда біреуін қамтуы мүмкін а−1 = 0 ретпен, осылайша n = −1 ұзындықтың тізбегімен алуға болады.)

Анықтама бойынша әрбір қосу тізбегі де қосу-азайту тізбегі болып табылады, бірақ керісінше емес. Сондықтан, ұзындығы ең қысқа қосу-азайту тізбегі n жоғарыда ең қысқа қосу тізбегінің ұзындығымен шектелген n. Жалпы алғанда, алайда минималды қосу-азайту тізбегін анықтау (минималды қосу тізбегін анықтау мәселесі сияқты) қиын есеп болып табылады, ол үшін қазіргі кезде тиімді алгоритмдер белгілі емес. Оптималды табу мәселесі қосу реті болып табылады NP аяқталды (Дауни және басқалар, 1981), бірақ оңтайлы қосу немесе қосу-азайту тізбектерін табу екендігі белгісіз NP-hard.

Мысалы, қосу-азайтудың бір тізбегі: , , , . Бұл а минималды қосу-азайту тізбегі n= 3, дегенмен, өйткені біз оның орнына таңдау жасай алдық . Ең кішкентай n ол үшін қосу-азайту тізбегі минималды қосу тізбегінен қысқа n= 31, оны тек 6 қосумен есептеуге болады (минималды қосу тізбегі үшін 7 емес):

Қосу тізбегі сияқты, қосу-азайту тізбегін пайдалануға болады қосымша тізбекті дәрежелеу: ұзындықты қосу-азайту тізбегі берілген L үшін n, қуат көбейту немесе бөлу арқылы есептеуге болады х L азайту бөлімдерге сәйкес келетін уақыт. Бұл бөлу арзан операция болып табылатын мәселелерде тиімді, әсіресе экспонентирование үшін тиімді эллиптикалық қисықтар мұнда бөлу тек белгінің өзгеруіне сәйкес келеді (Морен және Оливос ұсынған 1990 ж.).

Кейбіреулер аппараттық мультипликаторлар көбейту n екілік сипаттамада n сипатталған қосу тізбегін қолдану:

    n = 31 = 0 0 0 1 1 1 1 1 (екілік).

Басқа аппараттық көбейткіштер көбейтіледі n n-мен сипатталған қосу-азайту тізбегін қолдану Кабинаны кодтау:

    n = 31 = 0 0 1 0 0 0 0 −1 (стендтік кодтау).

Әдебиеттер тізімі

  • Вольгер, Гюго (8 сәуір 1985). «Қосу / азайту тізбектерінің кейбір нәтижелері». Ақпаратты өңдеу хаттары. 20 (3): 155–160. дои:10.1016/0020-0190(85)90085-7.
  • Морен, Франсуа; Оливос, Хорхе (1990). «Эллиптикалық қисық бойынша есептеулерді қосу-азайту тізбектерін пайдаланып жылдамдату» (PDF). Ақпараттық технологиялар және қосымшалар. 24 (6): 531–543. CiteSeerX  10.1.1.56.347.
  • Дауни, Питер Дж.; Леонг, Бентон Л .; Сети, Рави (1981). «Қосу тізбектері бар есептеу тізбегі». SIAM J. Comput. 10 (3): 638–646. дои:10.1137/0210047.
  • Слоан, Н. (ред.). «A128998 реттілігі (минималды қосу-азайту тізбегінің ұзындығы)». The Он-лайн тізбегінің энциклопедиясы. OEIS қоры.