Определение того, какое целое число ближе всего к корню k-го из n без использования арифметики с плавающей запятой?

Ответ 1

2 ^k a ^k 2 ^k n < (2a + 1) ^k → (деля на 2 ^k) a ^k n < (a + 0,5) ^k → (взяв k-й корень) a < ^k √n < a + 0,5, поэтому k-й корень n ближе к a, чем к a+1. Обратите внимание, что кромка края не встречается; k-й корень целого не может быть целым числом плюс 0,5 (a + 0,5), так как k-ые корни n, которые не являются k-ыми степенями, являются иррациональными, а если n - совершенная k-я степень, то k-й корень будет целым числом./p >

Ответ 2

Ответы Ramchandra Apte и Lazarus содержат то, что кажется сущностью правильного ответа, но и то, и другое (по крайней мере для меня) немного трудно следовать. Позвольте мне попытаться объяснить трюк, с которым они, похоже, добираются, насколько я понимаю, немного более четко:

Основная идея состоит в том, что для выяснения того, ближе ли a + или + к ^k √n, нам нужно проверить, является ли ^k √n < а + & frac12;.

Чтобы избавиться от & frac12;, мы можем просто умножить обе стороны этого неравенства на 2, давая 2 & middot; ^k √n < 2 a +1, и, подняв обе стороны к k-й степени (и предположив, что они оба положительны), получаем эквивалентное неравенство 2 ^k & middot; n < lt; (2 <я > а + 1) ^к. Итак, по крайней мере, до тех пор, пока 2 ^k & middot; n = n & ll; k не переполняется, мы можем просто сравнить его с (2 a +1) ^k чтобы получить ответ.

Фактически мы могли бы просто вычислить b = & lloor; ^k √ (2 ^k & middot; n) & rfloor; начать с. Если b четно, то ближайшим целым числом к ​​ ^k √n является b/2; если b нечетно, это (b + 1)/2. Действительно, мы можем комбинировать эти два случая и сказать, что самое близкое целое к ^k √n is & lloloor; (b + 1)/2 & rfloor; или в псевдо-C:

int round_root( int k, int n ) {
    int b = floor_root( k, n << k );
    return (b + 1) / 2;
}

Ps. Альтернативный подход может заключаться в том, чтобы вычислить приближение (a + & frac12;) ^k непосредственно, используя теорему биномиальной теоремы как (А + & frac12;) ^к = & sum; _{я = 0..k} (k выберите i) a ^{k & minus; i}/2 ⁱ & Около; а ^к + k & middot; a ^{k & minus; 1}/2 +... и сравнить его напрямую с n. Однако, по крайней мере, наивно, суммируя все термины биномиального расширения, по-прежнему необходимо отслеживать k дополнительных бит точности (или, по крайней мере, k & minus; 1, я считаю, что последний термин можно безопасно пренебречь), поэтому он может не получить много по предложенному выше методу.

Ответ 3

Я предполагаю, что вы хотите использовать этот алгоритм для FPGA/CPLD или процессора с ограниченными ресурсами, поскольку ваш подход напоминает мне CORDIC. Поэтому я дам решение с этим.

Когда вы достигнете a^k ≤ n < (a+1)^k, это означает, что пол x = root (n, k) равен 'a'. Другими словами, x = a + f, где 0=<f<0.5. Таким образом, умножая уравнение на 2, вы получите 2x=2a+2f. Это в основном означает, что floor(2x) = 2a (поскольку 2f < 1). Теперь x = √n (kth root), таким образом 2x = k√((2^k)*n) (kth root). Итак, просто сдвиньте n на k бит влево, а затем вычислите свой k-й корень с помощью вашего алгоритма. Если его нижняя граница была ровно в 2 раза k-го корня из n, то k-й корень из n равен a, в противном случае это a + 1.

Предполагая, что у вас есть функция, которая дает вам нижнюю границу k-го корня из n (rootk (n)), конечный результат с использованием двоичных операторов и с обозначениями C будет:

closeestint = a + ((rootk (n) < 1) == rootk (n → k));

Ответ 4

Вычислить куб (a + 0.5)*10 (или 10a + 5 - нет арифметики с плавающей запятой), затем разделите его на 1000.

Затем проверьте, на какой стороне номер.

Идея умножения на 10 - сдвинуть десятичное место на одну позицию вправо. Затем мы делим на 1000, потому что мы умножаемся на 10 3 раза из-за кубирования.

Например:

Input: 16

a = 2
a+1 = 3

a^3 = 8
(a+1)^3 = 27

10a + 5 = 25

25^3 = 15625

floor(15625 / 1000) = 15

16 > 15, thus 3 is closer.

Это также сработало бы, как отметил Oli, вычислить куб (a + 0.5)*2 (или 2a + 1), а затем разделить его на 8.

Например:

2a + 1 = 5

5^3 = 125

floor(125 / 8) = 15

16 > 15, thus 3 is closer.

Ответ 5

Вы можете использовать метод Ньютона для поиска; он отлично работает с целыми числами и быстрее, чем двоичный поиск. Затем вычислите a ^k и (a + 1) ^k используя алгоритм питания с квадратным и множителем. Здесь некоторый код, на Схеме, потому что у меня получилось, что удобно:

(define (iroot k n) ; largest integer x such that x ^ k <= n
  (let ((k-1 (- k 1)))
    (let loop ((u n) (s (+ n 1)))
      (if (<= s u) s
        (loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))

(define (ipow b e) ; b^e
  (if (= e 0) 1
    (let loop ((s b) (i e) (a 1)) ; a * s^i = b^e
      (let ((a (if (odd? i) (* a s) a)) (i (quotient i 2)))
        (if (zero? i) a (loop (* s s) i a))))))

Чтобы определить, какая из ^k и (a + 1) ^k ближе к корню, вы можете использовать алгоритм питания для вычисления (a + ¹/ ₂) ^k — это точный расчет, что операция квадратного умножения может выполняться — затем сравните результат с n и определите, какая из сторон ближе.

Ответ 6

Изменить: -

Извините, что не понял проблему. Вот возможное решение оригинального вопроса: -

Использовать аппроксимационную теорию Ньютонов: -

here = means (approximately = )

f(b+a) = f(b) + a*f'(b)

 a -> 0

f(x) = x^k

f'(x) = k*x^(k-1)

hence using above equation

f(a+0.5) = a^k + 1/2*k*a^(k-1);



need to check    n < f(a+0.5)  

                 n < a^k + 1/2*k*a^(k-1)

rearranging      (n-a^k)*2 < k*a^(k-1)

Примечание: вы можете использовать биномиальную теорему для получения большей точности.

Ответ 7

Думать. В идеале вы бы сделали еще один шаг бинарного поиска, чтобы увидеть, на какой стороне лежит корень. То есть проверим неравенство

(a + 0,5) ^k п

Но левая сторона трудно точно вычислить (проблемы с плавающей запятой). Итак, запишем эквивалентное неравенство, в котором все члены являются целыми числами:

(2a + 1) ^k 2 ^k n

Готово.