Квадратный корень из длинного числа

[Вся длинная арифметика]

Эта задача далась мне тяжелее всех. Наверное потому, что я пытался зачесть ее на acm.sgu.ru и acmp.ru, где ограничения на количество разрядов в числе 1000 и 3000 соответственно. Для начала зачтем эту задачу на informatics.mccme.ru, где ограничение всего 100.

Здесь можно пойти двумя путями:
I) Бинарным поиском подбирать число, квадрат которого не превосходит данное число. При этом придется не полениться и реализовать компаратор, короткий плюс и минус, длинное умножение и сложение, а также деление на короткое. Многовато, не правда ли? Общую логику видно по следующему фрагменту:

1. BigInt sqrt()
2. {
3.     BigInt l , r = *this;
4.     BigInt res;
5.     while (l<=r)
6.     {
7.       BigInt m = (l + r)/2;
8.       if (m*m <= *this)
9.       {
10.         res = m;
11.         l = m + 1;
12.       }
13.       else
14.         r = m - 1;
15.     }
16.     return res;
17. }

* This source code was highlighted with Source Code Highlighter.

II) Оценить максимальное количество цифр в ответе и подбирать бинарным поиском цифры ответа, начиная со старшего разряда. При таком раскладе нам нужны только компаратор и умножение на длинное. Да и сама функция будет работать быстрее первого варианта:

1. BigInt sqrt()
2. {
3.     BigInt cur;
4.     // максимальное количество разрядов в ответе
5.     int pos = (amount + 1) / 2;
6.     cur.amount = pos;
7.     pos--;
8.     while (pos>=0)
9.     {
10.       int l = 0, r = osn;
11.       int curDigit = 0;
12.       while (l<=r) // подбираем текущую цифру
13.       {
14.         int m = (l+r)>>1;
15.         cur.digits[pos] = m;
16.         if (cur * cur <= *this)
17.         {
18.           curDigit = m;
19.           l = m + 1;
20.         }
21.         else
22.           r = m - 1;
23.       }
24.       cur.digits[pos] = curDigit;
25.       pos--;
26.     }
27.     // избавляемся от лидирующих нулей
28.     if (cur.amount!=1 && !cur.digits[cur.amount-1])
29.       cur.amount--;
30.     return cur; 
31. }

* This source code was highlighted with Source Code Highlighter.

Справедливости ради нужно отметить, что представленные решения со всеми возможными моими ухищрениями по оптимизации получили TLE#22, TLE#23 на acmp.ru и TLE#15, TLE#29 на acm.sgu.ru соответственно. И как еще удалось выяснить на sgu имеются пробелы во входных данных 6 теста(=.

На acmp.ru имеется разбор, который идентичиен второму решению. Т.е. нужно подумать где можно соптимизировать еще. И надо считать, что именно этот подход нужно использовать в полевых условиях, т.е. на контестах).

Картина была бы неполной, если бы речь не зашла про совершенно магический способ вычисления квадратного корня “ручками”. С ним можно ознакомиться в книге “Математика: Справочные материалы. Гусев В.А., Мордкович А.Г.[с.45]” Общий механизм представлю ниже:

1. Считываем входное число при osn = 100. В дальнейшем считаем что osn = 10.
2. Подбираем цифру, квадрат которой не превосходит старший разряд входного числа. Это есть первая цифра ответа.
3. Найдем разницу между старшим разрядом входного числа и квадратом найденной цифры. Ответ припишем слева ко второму разряду входного числа. Получим некое число A.
4. Удвоим имеющуюся часть ответа, получим число a. Подберем наибольшую цифру x, такую что произведение чисел ax(a - десятки, x - единицы) и x не превосходило А. Число x - вторая цифра ответа.
5. Число A - ax * x припишем слева к третьему разряду входного числа. Получим некое число B. Повторяем итерации 4-5 до тех пор пока не закончатся разряды во входном числе.

Более нагляднее рассмотрим пример на основе числа 138384.
1) Храним число как 84-83-13
2) 3*3 <=13. Текущий ответ: 3
3) 13-3*3 = 4. Припишем 4 к 83. Получаем А = 483.
4) a = 3*2 = 6. 6x * x <=483. x = 7. Текущий ответ: 37.
5)483-67*7 = 14. Припишем 14 к 84. Получаем B = 1484.
6). b = 37*2 = 74. 74x*x <=1484. x = 2. Текущий ответ = 372. Он же и окончательный.

III) Все вышеизложенное реализовано здесь.
Как видно время работы пропорционально количеству разрядов в корне входного числа. С таким решением не стыдно показаться на любом сервере проверки). На acm.sgu.ru эта реализация работала 0.095 с, на acmp.ru 0.389 с.