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

=={{header|Maxima}}==

<lang maxima>/* -*- Maxima -*- */

/*

The Rosetta Code integer square root task, in Maxima.

I have not tried to make the output conform quite to the task

description, because Maxima is not a general purpose programming

language. Perhaps someone else will care to do it.

*/

/* pow4gtx -- find a power of 4 greater than x. */

pow4gtx (x) := block (

[q],

q : 1, while q <= x do q : bit_lsh (q, 2),

q

) $

/* rosetta_code_isqrt -- find the integer square root. */

rosetta_code_isqrt (x) := block (

[q, z, r, t],

q : pow4gtx (x),

z : x,

r : 0,

while 1 < q do (

q : bit_rsh (q, 2),

t : z - r - q,

r : bit_rsh (r, 2),

if 0 <= t then (

z : t,

r : r + q

)

),

r

) $

for i : 0 thru 65 do (display (isqrt (i))) $

for i : 1 thru 73 step 2 do (display (7**i, isqrt (7**i))) $</lang>

{{out}}

<pre style="height:30em;overflow:auto">$ maxima -q -b isqrt.mac

(%i1) batch("isqrt.mac")

read and interpret /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac

(%i2) pow4gtx(x):=block([q],q:1,while q <= x do q:bit_lsh(q,2),q)

(%i3) rosetta_code_isqrt(x):=block([q,z,r,t],q:pow4gtx(x),z:x,r:0,

while 1 < q do

(q:bit_rsh(q,2),t:z-r-q,r:bit_rsh(r,2),

if 0 <= t then (z:t,r:r+q)),r)

(%i4) for i from 0 thru 65 do display(isqrt(i))

isqrt(0) = 0

isqrt(1) = 1

isqrt(2) = 1

isqrt(3) = 1

isqrt(4) = 2

isqrt(5) = 2

isqrt(6) = 2

isqrt(7) = 2

isqrt(8) = 2

isqrt(9) = 3

isqrt(10) = 3

isqrt(11) = 3

isqrt(12) = 3

isqrt(13) = 3

isqrt(14) = 3

isqrt(15) = 3

isqrt(16) = 4

isqrt(17) = 4

isqrt(18) = 4

isqrt(19) = 4

isqrt(20) = 4

isqrt(21) = 4

isqrt(22) = 4

isqrt(23) = 4

isqrt(24) = 4

isqrt(25) = 5

isqrt(26) = 5

isqrt(27) = 5

isqrt(28) = 5

isqrt(29) = 5

isqrt(30) = 5

isqrt(31) = 5

isqrt(32) = 5

isqrt(33) = 5

isqrt(34) = 5

isqrt(35) = 5

isqrt(36) = 6

isqrt(37) = 6

isqrt(38) = 6

isqrt(39) = 6

isqrt(40) = 6

isqrt(41) = 6

isqrt(42) = 6

isqrt(43) = 6

isqrt(44) = 6

isqrt(45) = 6

isqrt(46) = 6

isqrt(47) = 6

isqrt(48) = 6

isqrt(49) = 7

isqrt(50) = 7

isqrt(51) = 7

isqrt(52) = 7

isqrt(53) = 7

isqrt(54) = 7

isqrt(55) = 7

isqrt(56) = 7

isqrt(57) = 7

isqrt(58) = 7

isqrt(59) = 7

isqrt(60) = 7

isqrt(61) = 7

isqrt(62) = 7

isqrt(63) = 7

isqrt(64) = 8

isqrt(65) = 8

(%i5) for i step 2 thru 73 do display(7^i,isqrt(7^i))

1

7 = 7

isqrt(7) = 2

3

7 = 343

isqrt(343) = 18

5

7 = 16807

isqrt(16807) = 129

7

7 = 823543

isqrt(823543) = 907

9

7 = 40353607

isqrt(40353607) = 6352

11

7 = 1977326743

isqrt(1977326743) = 44467

13

7 = 96889010407

isqrt(96889010407) = 311269

15

7 = 4747561509943

isqrt(4747561509943) = 2178889

17

7 = 232630513987207

isqrt(232630513987207) = 15252229

19

7 = 11398895185373143

isqrt(11398895185373143) = 106765608

21

7 = 558545864083284007

isqrt(558545864083284007) = 747359260

23

7 = 27368747340080916343

isqrt(27368747340080916343) = 5231514822

25

7 = 1341068619663964900807

isqrt(1341068619663964900807) = 36620603758

27

7 = 65712362363534280139543

isqrt(65712362363534280139543) = 256344226312

29

7 = 3219905755813179726837607

isqrt(3219905755813179726837607) = 1794409584184

31

7 = 157775382034845806615042743

isqrt(157775382034845806615042743) = 12560867089291

33

7 = 7730993719707444524137094407

isqrt(7730993719707444524137094407) = 87926069625040

35

7 = 378818692265664781682717625943

isqrt(378818692265664781682717625943) = 615482487375282

37

7 = 18562115921017574302453163671207

isqrt(18562115921017574302453163671207) = 4308377411626977

39

7 = 909543680129861140820205019889143

isqrt(909543680129861140820205019889143) = 30158641881388842

41

7 = 44567640326363195900190045974568007

isqrt(44567640326363195900190045974568007) = 211110493169721897

43

7 = 2183814375991796599109312252753832343

isqrt(2183814375991796599109312252753832343) = 1477773452188053281

45

7 = 107006904423598033356356300384937784807

isqrt(107006904423598033356356300384937784807) = 10344414165316372973

47

7 = 5243338316756303634461458718861951455543

isqrt(5243338316756303634461458718861951455543) = 72410899157214610812

49

7 = 256923577521058878088611477224235621321607

isqrt(256923577521058878088611477224235621321607) = 506876294100502275687

51

7 = 12589255298531885026341962383987545444758743

isqrt(12589255298531885026341962383987545444758743) = 3548134058703515929815

53

7 = 616873509628062366290756156815389726793178407

isqrt(616873509628062366290756156815389726793178407) = 24836938410924611508707

55

7 = 30226801971775055948247051683954096612865741943

isqrt(30226801971775055948247051683954096612865741943) =

173858568876472280560953

57

7 = 1481113296616977741464105532513750734030421355207

isqrt(1481113296616977741464105532513750734030421355207) =

1217009982135305963926677

59

7 = 72574551534231909331741171093173785967490646405143

isqrt(72574551534231909331741171093173785967490646405143) =

8519069874947141747486745

61

7 = 3556153025177363557255317383565515512407041673852007

isqrt(3556153025177363557255317383565515512407041673852007) =

59633489124629992232407216

63

7 = 174251498233690814305510551794710260107945042018748343

isqrt(174251498233690814305510551794710260107945042018748343) =

417434423872409945626850517

65

7 = 8538323413450849900970017037940802745289307058918668807

isqrt(8538323413450849900970017037940802745289307058918668807) =

2922040967106869619387953625

67

7 = 418377847259091645147530834859099334519176045887014771543

isqrt(418377847259091645147530834859099334519176045887014771543) =

20454286769748087335715675381

69

7 = 20500514515695490612229010908095867391439626248463723805607

isqrt(20500514515695490612229010908095867391439626248463723805607) =

143180007388236611350009727669

71

7 = 1004525211269079039999221534496697502180541686174722466474743

isqrt(1004525211269079039999221534496697502180541686174722466474743) =

1002260051717656279450068093686

73

7 = 49221735352184872959961855190338177606846542622561400857262407

isqrt(49221735352184872959961855190338177606846542622561400857262407) =

7015820362023593956150476655802

(%o6) /home/trashman/src/chemoelectric/rosettacode-contributions/isqrt.mac</pre>