Isqrt (integer square root) of X: Difference between revisions
Content added Content deleted
(Ada version) |
|||
Line 97: | Line 97: | ||
:* [[Square_Root_by_Hand|square root by hand]] |
:* [[Square_Root_by_Hand|square root by hand]] |
||
<br><br> |
<br><br> |
||
=={{header|Ada}}== |
|||
{{works with|Ada 2022}} |
|||
<lang Ada>with Ada.Text_Io; |
|||
with Ada.Numerics.Big_Numbers.Big_Integers; |
|||
with Ada.Strings.Fixed; |
|||
procedure Integer_Square_Root is |
|||
subtype Big_Integer is Ada.Numerics.Big_Numbers.Big_Integers.Big_Integer; |
|||
use all type Big_Integer; |
|||
function Isqrt (X : Big_Integer) return Big_Integer is |
|||
Q : Big_Integer := To_Big_Integer (1); |
|||
Z : Big_Integer; |
|||
T : Big_Integer; |
|||
R : Big_Integer; |
|||
begin |
|||
while Q <= X loop |
|||
Q := Q * To_Big_Integer (4); |
|||
end loop; |
|||
Z := X; |
|||
R := To_Big_Integer (0); |
|||
while Q > To_Big_Integer (1) loop |
|||
Q := Q / To_Big_Integer (4); |
|||
T := Z - R - Q; |
|||
R := R / To_Big_Integer (2); |
|||
if T >= To_Big_Integer (0) then |
|||
Z := T; |
|||
R := R + Q; |
|||
end if; |
|||
end loop; |
|||
return R; |
|||
end Isqrt; |
|||
function Commatize (N : Big_Integer; Width : Positive) return String is |
|||
S : constant String := To_String (N, Width); |
|||
Image : String (1 .. Width + Width / 3) := (others => ' '); |
|||
Pos : Natural := Image'Last; |
|||
begin |
|||
for I in S'Range loop |
|||
Image (Pos) := S (S'Last - I + S'First); |
|||
exit when Image (Pos) = ' '; |
|||
Pos := Pos - 1; |
|||
if I mod 3 = 0 and S (S'Last - I + S'First - 1) /= ' ' then |
|||
Image (Pos) := '''; |
|||
Pos := Pos - 1; |
|||
end if; |
|||
end loop; |
|||
return Image; |
|||
end Commatize; |
|||
use Ada.Text_Io; |
|||
type Mode_Kind is (Tens, Ones, Spacer, Result); |
|||
begin |
|||
Put_Line ("Integer square roots of integers 0 .. 65:"); |
|||
for Mode in Mode_Kind loop |
|||
for N in 0 .. 65 loop |
|||
case Mode is |
|||
when Tens => Put ((if N / 10 = 0 |
|||
then " " |
|||
else Natural'Image (N / 10))); |
|||
when Ones => Put (Natural'Image (N mod 10)); |
|||
when Spacer => Put ("--"); |
|||
when Result => Put (To_String (Isqrt (To_Big_Integer (N)))); |
|||
end case; |
|||
end loop; |
|||
New_Line; |
|||
end loop; |
|||
New_Line; |
|||
declare |
|||
package Integer_Io is new Ada.Text_Io.Integer_Io (Natural); |
|||
use Ada.Strings.Fixed; |
|||
N : Integer := 1; |
|||
P : Big_Integer := To_Big_Integer (7); |
|||
R : Big_Integer; |
|||
begin |
|||
Put_Line ("| N|" & 80 * " " & "7**N|" & 30 * " " & "isqrt (7**N)|"); |
|||
Put_Line (133 * "="); |
|||
loop |
|||
R := Isqrt (P); |
|||
Put ("|"); Integer_Io.Put (N, Width => 3); |
|||
Put ("|"); Put (Commatize (P, Width => 63)); |
|||
Put ("|"); Put (Commatize (R, Width => 32)); |
|||
Put ("|"); New_Line; |
|||
exit when N >= 73; |
|||
N := N + 2; |
|||
P := To_Big_Integer (7 * 7) * P; |
|||
end loop; |
|||
Put_Line (133 * "="); |
|||
end; |
|||
end Integer_Square_Root;</lang> |
|||
{{out}} |
|||
<pre> |
|||
Integer square roots of integers 0 .. 65: |
|||
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 |
|||
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 |
|||
------------------------------------------------------------------------------------------------------------------------------------ |
|||
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 |
|||
| 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| |
|||
| 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|ALGOL 68}}== |
=={{header|ALGOL 68}}== |