Как обрабатывать большие входные данные в методе целочисленного квадрата root? - PullRequest
Новая
       84

Как обрабатывать большие входные данные в методе целочисленного квадрата root?

0 голосов
/ 14 марта 2020

Мне нужно реализовать метод для нахождения целочисленного квадрата - root целого числа.

Моя платформа - это язык Solidity, где поддерживается только целочисленное арифметическое c и размер iput 256 бит (uint256).

Типичным решением является бинарный поиск, который я легко реализовал.

Проблема в том, что мой метод ограничен вводом, меньшим 2 ^ 129.

Вот мой метод (реализованный в Python): 

def sqrt(x):
    assert(x < 0x200000000000000000000000000000000);
    lo = 0;
    hi = x;
    while (True):
        mid = (lo+hi)//2;
        if (mid == lo or mid**2 == x):
            return mid;
        elif (mid**2 < x):
            lo = mid;
        else: # (mid**2 > x)
            hi = mid;

Обратите внимание, что я разместил его в Python, а не в Solidity, потому что большинство пользователей здесь не знаком с Solidity, поэтому я подумал, что Python будет хорошим выбором, чтобы позволить другим легко применять изменения в моем методе.

Тем не менее, меня обычно интересует решение алгоритми c.

1 Ответ

1 голос
/ 14 марта 2020

Это в Java, а не Python, просто потому, что у меня уже лежал этот. Код достаточно прост для преобразования, поскольку все переменные являются целыми числами, поэтому все они имеют целочисленное арифметическое значение c. 

/**
 * Finds the integer square root of a positive number.
 * Crandall and Pomerance algorithm 9.2.11 (Newton-Raphson).
 *
 * @param num int Number to find root of.
 * @return int Integer square root of given number.
 */
public static int iSqrt(int num) {
    if (0 == num) {
        // Avoid zero divide crash
        return 0;
    }
    int x = (num / 2) + 1;
    int y = (x + (num / x)) / 2;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2;
    } // end while
    return x;
} // end iSqrt(int)

Очень похоже на то, что у вас уже есть, но я думаю, что оно немного проще.

...