How to resolve the algorithm Nth root step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Nth root step by step in the Prolog programming language

Table of Contents

Problem Statement

Implement the algorithm to compute the principal   nth   root

A

n

{\displaystyle {\sqrt[{n}]{A}}}

of a positive real number   A,   as explained at the   Wikipedia page.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Nth root step by step in the Prolog programming language

Source code in the prolog programming language

iroot(_, 0, 0) :- !.
iroot(M, N, R) :-
    M > 1,
    (N > 0 ->
        irootpos(M, N, R)
    ;
        N /\ 1 =:= 1,
        NegN is -N, irootpos(M, NegN, R0), R is -R0).

irootpos(N, A, R) :-
    X0 is 1 << (msb(A) div N),  % initial guess is 2^(log2(A) / N)
    newton(N, A, X0, X1),
    iroot_loop(A, X1, N, A, R).

iroot_loop(X1, X2, _, _, X1) :- X1 =< X2, !.
iroot_loop(_, X1, N, A, R) :-
    newton(N, A, X1, X2),
    iroot_loop(X1, X2, N, A, R).

newton(2, A, X0, X1) :- X1 is (X0 + A div X0) >> 1, !.  % fast special case
newton(N, A, X0, X1) :- X1 is ((N - 1)*X0 + A div X0**(N - 1)) div N.

You may also check:How to resolve the algorithm Greatest common divisor step by step in the Klong programming language
You may also check:How to resolve the algorithm Honaker primes step by step in the RPL programming language
You may also check:How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the Racket programming language
You may also check:How to resolve the algorithm Balanced brackets step by step in the Groovy programming language
You may also check:How to resolve the algorithm Middle three digits step by step in the Klong programming language