How to resolve the algorithm Isqrt (integer square root) of X step by step in the AppleScript programming language

Published on 12 May 2024 09:40 PM
#Applescript

How to resolve the algorithm Isqrt (integer square root) of X step by step in the AppleScript programming language

Table of Contents

Problem Statement

Sometimes a function is needed to find the integer square root of   X,   where   X   can be a real non─negative number. Often   X   is actually a non─negative integer. For the purposes of this task,   X   can be an integer or a real number,   but if it simplifies things in your computer programming language,   assume it's an integer.

One of the most common uses of   Isqrt   is in the division of an integer by all factors   (or primes)   up to the   √ X    of that integer,   either to find the factors of that integer,   or to determine primality.

An alternative method for finding the   Isqrt   of a number is to calculate:       floor( sqrt(X) )

If the hardware supports the computation of (real) square roots,   the above method might be a faster method for small numbers that don't have very many significant (decimal) digits. However, floating point arithmetic is limited in the number of   (binary or decimal)   digits that it can support.

For this task, the integer square root of a non─negative number will be computed using a version of   quadratic residue,   which has the advantage that no   floating point   calculations are used,   only integer arithmetic. Furthermore, the two divisions can be performed by bit shifting,   and the one multiplication can also be be performed by bit shifting or additions. The disadvantage is the limitation of the size of the largest integer that a particular computer programming language can support.

Pseudo─code of a procedure for finding the integer square root of   X       (all variables are integers): Another version for the (above)   1st   perform   is:

Integer square roots of some values:

Compute and show all output here   (on this page)   for:

You can show more numbers for the 2nd requirement if the displays fits on one screen on Rosetta Code. If your computer programming language only supports smaller integers,   show what you can.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Isqrt (integer square root) of X step by step in the AppleScript programming language

Source code in the applescript programming language

on isqrt(x)
    set q to 1
    repeat until (q > x)
        set q to q * 4
    end repeat
    set z to x
    set r to 0
    repeat while (q > 1)
        set q to q div 4
        set t to z - r - q
        set r to r div 2
        if (t > -1) then
            set z to t
            set r to r + q
        end if
    end repeat
    
    return r
end isqrt

-- Task code
on intToText(n, separator)
    set output to ""
    repeat until (n < 1000)
        set output to separator & (text 2 thru 4 of ((1000 + (n mod 1000) as integer) as text)) & output
        set n to n div 1000
    end repeat
    
    return (n as integer as text) & output
end intToText

on doTask()
    -- Get the integer and power results.
    set {integerResults, powerResults} to {{}, {}}
    repeat with x from 0 to 65
        set end of integerResults to isqrt(x)
    end repeat
    repeat with p from 1 to 73 by 2
        set x to 7 ^ p
        if (x > 1.0E+15) then exit repeat -- Beyond the precision of AppleScript reals.
        set end of powerResults to "7^" & p & tab & "(" & intToText(x, ",") & "):" & (tab & tab & intToText(isqrt(x), ","))
    end repeat
    -- Format and output.
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to space
    set output to {"Isqrts of integers from 0 to 65:", space & integerResults, ¬
        "Isqrts of odd powers of 7 from 1 to " & (p - 2) & ":", powerResults}
    set AppleScript's text item delimiters to linefeed
    set output to output as text
    set AppleScript's text item delimiters to astid
    
    return output
end doTask

doTask()


"Isqrts of integers from 0 to 65:
 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Isqrts of odd powers of 7 from 1 to 17:
7^1	(7):		2
7^3	(343):		18
7^5	(16,807):		129
7^7	(823,543):		907
7^9	(40,353,607):		6,352
7^11	(1,977,326,743):		44,467
7^13	(96,889,010,407):		311,269
7^15	(4,747,561,509,943):		2,178,889
7^17	(232,630,513,987,207):		15,252,229"

You may also check:How to resolve the algorithm Convert decimal number to rational step by step in the Haskell programming language
You may also check:How to resolve the algorithm Text processing/2 step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Terminal control/Display an extended character step by step in the J programming language
You may also check:How to resolve the algorithm Start from a main routine step by step in the Racket programming language
You may also check:How to resolve the algorithm Factorial step by step in the Elixir programming language