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

=={{header|Racket}}==

<lang Racket>

#lang racket

;; Integer Square Root (using Quadratic Residue)

(define (isqrt x)

(define q-init ; power of 4 greater than x

(let loop ([acc 1])

(if (<= acc x) (loop (* acc 4)) acc)))

(define-values (z r q)

(let loop ([z x] [r 0] [q q-init])

(if (<= q 1)

(values z r q)

(let* ([q (/ q 4)]

[t (- z r q)]

[r (/ r 2)])

(if (>= t 0)

(loop t (+ r q) q)

(loop z r q))))))

r)

(define (format-with-commas str #:chunk-size [size 3])

(define len (string-length str))

(define len-mod (modulo len size))

(define chunks

(for/list ([i (in-range len-mod len size)])

(substring str i (+ i size))))

(string-join (if (= len-mod 0)

chunks

(cons (substring str 0 len-mod) chunks))

","))

(displayln "Isqrt of integers (0 -> 65):")

(for ([i 66])

(printf "~a " (isqrt i)))

(displayln "\n\nIsqrt of odd powers of 7 (7 -> 7^73):")

(for/fold ([num 7]) ([i (in-range 1 74 2)])

(printf "Isqrt(7^~a) = ~a\n"

i

(format-with-commas (number->string (isqrt num))))

(* num 49))

</lang>

{{out}}

<pre>

Isqrt of integers (0 -> 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

Isqrt of odd powers of 7 (7 -> 7^73):

Isqrt(7^1) = 2

Isqrt(7^3) = 18

Isqrt(7^5) = 129

Isqrt(7^7) = 907

Isqrt(7^9) = 6,352

Isqrt(7^11) = 44,467

Isqrt(7^13) = 311,269

Isqrt(7^15) = 2,178,889

Isqrt(7^17) = 15,252,229

Isqrt(7^19) = 106,765,608

Isqrt(7^21) = 747,359,260

Isqrt(7^23) = 5,231,514,822

Isqrt(7^25) = 36,620,603,758

Isqrt(7^27) = 256,344,226,312

Isqrt(7^29) = 1,794,409,584,184

Isqrt(7^31) = 12,560,867,089,291

Isqrt(7^33) = 87,926,069,625,040

Isqrt(7^35) = 615,482,487,375,282

Isqrt(7^37) = 4,308,377,411,626,977

Isqrt(7^39) = 30,158,641,881,388,842

Isqrt(7^41) = 211,110,493,169,721,897

Isqrt(7^43) = 1,477,773,452,188,053,281

Isqrt(7^45) = 10,344,414,165,316,372,973

Isqrt(7^47) = 72,410,899,157,214,610,812

Isqrt(7^49) = 506,876,294,100,502,275,687

Isqrt(7^51) = 3,548,134,058,703,515,929,815

Isqrt(7^53) = 24,836,938,410,924,611,508,707

Isqrt(7^55) = 173,858,568,876,472,280,560,953

Isqrt(7^57) = 1,217,009,982,135,305,963,926,677

Isqrt(7^59) = 8,519,069,874,947,141,747,486,745

Isqrt(7^61) = 59,633,489,124,629,992,232,407,216

Isqrt(7^63) = 417,434,423,872,409,945,626,850,517

Isqrt(7^65) = 2,922,040,967,106,869,619,387,953,625

Isqrt(7^67) = 20,454,286,769,748,087,335,715,675,381

Isqrt(7^69) = 143,180,007,388,236,611,350,009,727,669

Isqrt(7^71) = 1,002,260,051,717,656,279,450,068,093,686

Isqrt(7^73) = 7,015,820,362,023,593,956,150,476,655,802

</pre>