Isqrt (integer square root) of X: Difference between revisions
→{{header|Cowgol}}
Line 1,358:
=={{header|Common Lisp}==
{{trans|Scheme}}
The program is wrapped in a [https://roswell.github.io/ Roswell script]. On a POSIX system with Roswell installed, you can simply run the script.
The code is an "imperative" translation of the "functional" Scheme.
Side notes:
* Straight translations from Scheme to Common Lisp run the risk of running properly with some CL compilers but not others, due to the prevalence of tail calls in Scheme. Common Lisp does not require proper tail calls, although CL compilers do optimize such calls, to varying degrees depending on the compiler.
* The simple program here would not require tail call optimization at all; the depth of recursion would be too small. I felt it better to write the CL in "imperative" style nonetheless.
* Not all Scheme compilers make all tail calls proper, either, at least by default. This, however, is nonstandard behavior.
<lang lisp>#!/bin/sh
#|-*- mode:lisp -*-|#
#|
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
(ros:ensure-asdf)
#+quicklisp(ql:quickload '() :silent t)
)
(defpackage :ros.script.isqrt.3860764029
(:use :cl))
(in-package :ros.script.isqrt.3860764029)
;;
;; The Rosetta Code integer square root task, in Common Lisp.
;;
;; I translate the tail recursions of the Scheme as regular loops in
;; Common Lisp, although CL compilers most often can optimize tail
;; recursions of the kind. They are not required to, however.
;;
;; As a result, the CL is actually closer to the task's pseudocode
;; than is the Scheme.
;;
;; (The Scheme, by the way, could have been written much as follows,
;; using "set!" where the CL has "setf", and with other such
;; "linguistic" changes.)
;;
(defun find-a-power-of-4-greater-than-x (x)
(let ((q 1))
(loop until (< x q)
do (setf q (* 4 q)))
q))
(defun isqrt+remainder (x)
(let ((q (find-a-power-of-4-greater-than-x x))
(z x)
(r 0))
(loop until (= q 1)
do (progn (setf q (/ q 4))
(let ((z1 (- z r q)))
(setf r (/ r 2))
(when (<= 0 z1)
(setf z z1)
(setf r (+ r q))))))
(values r z)))
(defun rosetta_code_isqrt (x)
(nth-value 0 (isqrt+remainder x)))
(defun main (&rest argv)
(declare (ignorable argv))
(format t "isqrt(i) for ~D <= i <= ~D:~2%" 0 65)
(loop for i from 0 to 64
do (format t "~D " (isqrt i)))
(format t "~D~3%" (isqrt 65))
(format t "isqrt(7**i) for ~D <= i <= ~D, i odd:~2%" 1 73)
(format t "~2@A ~84@A ~43@A~%" "i" "7**i" "sqrt(7**i)")
(format t "~A~%" (make-string 131 :initial-element #\-))
(loop for i from 1 to 73 by 2
for 7**i = (expt 7 i)
for root = (rosetta_code_isqrt 7**i)
do (format t "~2D ~84:D ~43:D~%" i 7**i root)))
;;; vim: set ft=lisp lisp:</lang>
{{out}}
<pre>$ sh isqrt.ros
isqrt(i) for 0 <= i <= 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(7**i) for 1 <= i <= 73, i odd:
i 7**i sqrt(7**i)
-----------------------------------------------------------------------------------------------------------------------------------
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
45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973
47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812
49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687
51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815
53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707
55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953
57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677
59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745
61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216
63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517
65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625
67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381
69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669
71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686
73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802</pre>
=={{header|Cowgol}}==
<lang cowgol>include "cowgol.coh";
| |||