Isqrt (integer square root) of X: Difference between revisions

=={{header|Fortran}}==

<lang fortran>MODULE INTEGER_SQUARE_ROOT

IMPLICIT NONE

CONTAINS

! Convert string representation number to string with comma digit separation

FUNCTION COMMATIZE(NUM) RESULT(OUT_STR)

INTEGER(16), INTENT(IN) :: NUM

INTEGER(16) I

CHARACTER(83) :: TEMP, OUT_STR

WRITE(TEMP, '(I0)') NUM

OUT_STR = ""

DO I=0, LEN_TRIM(TEMP)-1

IF (MOD(I, 3) .EQ. 0 .AND. I .GT. 0 .AND. I .LT. LEN_TRIM(TEMP)) THEN

OUT_STR = "," // TRIM(OUT_STR)

END IF

OUT_STR = TEMP(LEN_TRIM(TEMP)-I:LEN_TRIM(TEMP)-I) // TRIM(OUT_STR)

END DO

END FUNCTION COMMATIZE

! Calculate the integer square root for a given integer

FUNCTION ISQRT(NUM)

INTEGER(16), INTENT(IN) :: NUM

INTEGER(16) :: ISQRT

INTEGER(16) :: Q, Z, R, T

Q = 1

Z = NUM

R = 0

T = 0

DO WHILE (Q .LT. NUM)

Q = Q * 4

END DO

DO WHILE (Q .GT. 1)

Q = Q / 4

T = Z - R - Q

R = R / 2

IF (T .GE. 0) THEN

Z = T

R = R + Q

END IF

END DO

ISQRT = R

END FUNCTION ISQRT

END MODULE INTEGER_SQUARE_ROOT

! Demonstration of integer square root for numbers 0-65 followed by odd powers of 7

! from 1-73. Currently this demo takes significant time for numbers above 43

PROGRAM ISQRT_DEMO

USE INTEGER_SQUARE_ROOT

IMPLICIT NONE

INTEGER(16), PARAMETER :: MIN_NUM_HZ = 0

INTEGER(16), PARAMETER :: MAX_NUM_HZ = 65

INTEGER(16), PARAMETER :: POWER_BASE = 7

INTEGER(16), PARAMETER :: POWER_MIN = 1

INTEGER(16), PARAMETER :: POWER_MAX = 73

INTEGER(16), DIMENSION(MAX_NUM_HZ-MIN_NUM_HZ+1) :: VALUES

CHARACTER(2) :: HEADER_1

CHARACTER(83) :: HEADER_2

CHARACTER(83) :: HEADER_3

INTEGER(16) :: I

HEADER_1 = " n"

HEADER_2 = "7^n"

HEADER_3 = "isqrt(7^n)"

WRITE(*,'(A, I0, A, I0)') "Integer square root for numbers ", MIN_NUM_HZ, " to ", MAX_NUM_HZ

DO I=1, SIZE(VALUES)

VALUES(I) = ISQRT(MIN_NUM_HZ+I)

END DO

WRITE(*,'(100I2)') VALUES

WRITE(*,*) NEW_LINE('A')

WRITE(*,'(A,A,A,A,A)') HEADER_1, " | ", HEADER_2, " | ", HEADER_3

WRITE(*,*) REPEAT("-", 8+83*2)

DO I=POWER_MIN,POWER_MAX, 2

WRITE(*,'(I2, A, A, A, A)') I, " | " // COMMATIZE(7**I), " | ", COMMATIZE(ISQRT(7**I))

END DO

END PROGRAM ISQRT_DEMO</lang>

<pre>

Integer square root for numbers 0 to 65

0 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 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 7 8 8

n | 7^n | isqrt(7^n)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 | 7 | 2

3 | 343 | 18

5 | 16,807 | 129

7 | 823,543 | 907

9 | 40,353,607 | 6,352

11 | 1,977,326,743 | 44,467

13 | 96,889,010,407 | 311,269

15 | 4,747,561,509,943 | 2,178,889

17 | 232,630,513,987,207 | 15,252,229

19 | 11,398,895,185,373,143 | 106,765,608

21 | 558,545,864,083,284,007 | 747,359,260

23 | 27,368,747,340,080,916,343 | 5,231,514,822

25 | 1,341,068,619,663,964,900,807 | 36,620,603,758

27 | 65,712,362,363,534,280,139,543 | 256,344,226,312

29 | 3,219,905,755,813,179,726,837,607 | 1,794,409,584,184

31 | 157,775,382,034,845,806,615,042,743 | 12,560,867,089,291

33 | 7,730,993,719,707,444,524,137,094,407 | 87,926,069,625,040

35 | 378,818,692,265,664,781,682,717,625,943 | 615,482,487,375,282

37 | 18,562,115,921,017,574,302,453,163,671,207 | 4,308,377,411,626,977

39 | 909,543,680,129,861,140,820,205,019,889,143 | 30,158,641,881,388,842

41 | 44,567,640,326,363,195,900,190,045,974,568,007 | 211,110,493,169,721,897

43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281

</pre>