Computing nth roots

We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y → x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y → x/y² . Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for y → x/y³ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y → x/y³ ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute n th roots as a fixed-point search based upon repeated average damping of y → x/yⁿ⁻¹ . Use this to implement a simple procedure for computing n th roots using fixed-point , average-damp , and the repeated procedure of exercise 1.43 . Assume that any arithmetic operations you need are available as primitives.

    # Maksimov Gleb
    4 months ago

    Честно говоря, не совсем понимаю результаты экспериментов. Пробывал изменять значение лямбды (количество нулей после запятой), менял количество усреднений, менял входные данные (корень n степени и само значение x).

    КАКИЕ-ТО ВЫВОДЫ При увеличении количеств усреднений, вроде как разходится алгоритм или вычисляет очень долго, что немогу дождаться. (скорее расходится) При увеличении лямбда и входных данных, увиличивается время, что логично.

Authentication required

You must log in to post a comment.