Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
Line 1,358: | 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}}== |
=={{header|Cowgol}}== |
||
<lang cowgol>include "cowgol.coh"; |
<lang cowgol>include "cowgol.coh"; |