Вычислить корень N-й степени с помощью целочисленной арифметики

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

Главное, что он не может использовать арифметику с плавающей запятой, что исключает метод Ньютона и его производные. Единственный известный мне способ найти корни - это биномиальное расширение, но оно также требует арифметики с плавающей запятой.

Какие существуют методы / алгоритмы для вычисления целых корней n-й степени с использованием только целочисленной арифметики?

Редактировать: Спасибо за все ответы. Все они кажутся немного более разумными для проб и усовершенствований. Нет ли лучшего способа?

Edit2: Хорошо, кажется, нет разумного способа сделать это без проб / улучшений и без метода Ньютона или бинарного поиска. Может ли кто-нибудь дать сравнение двух теоретически ? Я провел несколько тестов между ними и нашел их очень похожими.