После провала программы Search Ultimate, искавшей строки в тексте за квадрат, Игорь К. задумался: "Отчего же, отчего моя программа работает так медленно?" Перепроверив еще раз свой код, он сказал: "В моем коде ошибок нет, однако я знаю, как мы будем улучшать Search Ultimate!" и достал с полки толстую книжку, на которой было написано "Аземблер. Принципиально новый подход".

Внимательно полистав эту книгу, Игорь К. понял, что, оказывается, умножение чисел можно проводить в десятки раз быстрее. "Search Ultimate будет быстра, как никогда!" — радостно прокричал он и приступил к работе.

Поясним теперь, в чем заключалась идея Игоря К. Дело в том, что код, генерируемый компилятором, далеко не оптимален — стандартное умножение чисел действительно работает медленнее, чем тот трюк, о котором рассказывалось в книжке.

В языке Azembler есть 26 регистров (eax, ebx, ..., ezx) и две команды:

• [x] — возвращает значение, записанное по адресу x. Например, [eax] возвращает значение, которое записано по адресу, равному значению в регистре eax.
• lea x, y — загружает в регистр x, указанный в качестве первого операнда, адрес второго операнда. Так, например, команда lea ebx, [eax] запишет в регистр ebx содержимое регистра eax: сначала выполнится операция [eax], результатом которой будет являться некоторое значение, лежащее по адресу, записанному в eax. Но нам не нужно это значение — следующей операцией будет lea — которая возьмет адрес [eax], т.е. значение в самом регистре eax, и запишет его в ebx.

На первый взгляд вторая операция кажется бессмысленной, но, оказывается, допустимо записывать эту операцию как

lea ecx, [eax + ebx],

lea ecx, [k*eax]

или даже

lea ecx, [ebx + k*eax],

где k = 1, 2, 4 или 8.

В результате в регистр ecx будут записаны соответственно числа eax + ebx, k*eax и ebx + k*eax. Но такая операция выполняется намного, в десятки раз, быстрее, чем обычное умножение чисел. А с помощью нескольких таких операций можно очень быстро умножить какое-либо число на другое. Конечно, вместо eax, ebx и ecx разрешено использовать любые регистры.

Например, пусть в регистре eax записано некоторое число, и требуется умножить его на 41. Это можно сделать в 2 cтрочки:

lea ebx, [eax + 4*eax] // теперь ebx = 5*eax

lea eax, [eax + 8*ebx] // теперь eax = eax + 8*ebx = 41*eax

Игорь К. заинтересовался, а каким минимальным числом операций lea можно умножить число на некоторое заданное число n и как это сделать. Ваша задача — помочь ему.

Считайте, что в начальный момент регистр eax содержит число, которое Игорь К. собрался умножать на n, а регистры от ebx до ezx содержат число 0. В конечный момент времени ответ может находиться в любом регистре.