Этюд в битовых тонах
Когда то давно, во время ковыряния "в" и изучения "как" очень хорошего и полезного пакета OpenSSL и как всегда неожиданно возникла одна простая идея и как все такие очень неожиданные идеи канула в лету. Но сухой остаток остался - была найдена ошибка в OpenSSL, в умножении большого числа на BN_ULONG и небольшая программа извлечения квадратного корня побитно. Сообщение об ошибке ушло на багтрекинг и было поправлено (пользуясь случаем извиняюсь за свою излишнюю эмоциональность тогда, не каждый день в OpenSSL ошибки находишь), а вот ту самую небольшую программу нахождения квадратного корня побитово по модулю 2^n, где n это количество бит\разрядность и предлагаю вашему вниманию. <cut /> Если рассмотреть алгоритм умножения двух чисел побитно, в столбик, то по значению i-х битов сомножителей, зная перенос, можно быстро определить бит результата - так и зная результат и предполагая распределение битов в сомножителях можно быстро эти биты вычислить. Как всегда ни