Isqrt (integer square root) of X: Difference between revisions
Ada version
(Ada version) |
|||
Line 97:
:* [[Square_Root_by_Hand|square root by hand]]
<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}}==
| |||