Я, конечно, не Ньютон...

[amarao]

Но вот самоизобретённый алгоритм поиска квадратного корня для int'а (на входе только положительные числа). Надо сказать, от Си его отличает только большая словесность (Ordering::Greater вместо 1).

use std::cmp::Ordering;

pub fn my_sqrt(x: i32) -> i32 {
    if x == 0 || x == 1{
        return x;
    }
    let x = x as u32;
    let sig_bit_count = 31 - x.leading_zeros();
    let mut working_bit = sig_bit_count / 2;
    let mut root = 1u32 << working_bit;
    while working_bit > 0 {
        working_bit -= 1;                    
        let candidate = 1 << working_bit; 
        root += match ((root + candidate) * (root + candidate)).cmp(&x) {
            Ordering::Equal | Ordering::Less => candidate,
            Ordering::Greater => 0,
        }
    }
    root as i32
}

Comments

[juan_gandhi]

А логично. Десятичный вариант мы в школе проходили, но двоичный-то логично. Спасибо.

[yurikhan]

Выглядит как работа с битами, а эквивалентно обычному методу половинного деления на интервале [2^k, 2^k+1-1] для какого-то подходящего k.

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