Long multiplication: Difference between revisions

Content added Content deleted
m (Fixed lang tags.)
Line 10: Line 10:
=={{header|Ada}}==
=={{header|Ada}}==
The following implementation uses representation of a long number by an array of 32-bit elements:
The following implementation uses representation of a long number by an array of 32-bit elements:
⚫
<lang ada>type Long_Number is array (Natural range <>) of Unsigned_32;
<lang ada>
⚫
type Long_Number is array (Natural range <>) of Unsigned_32;


function "*" (Left, Right : Long_Number) return Long_Number is
function "*" (Left, Right : Long_Number) return Long_Number is
Result : Long_Number (0..Left'Length + Right'Length - 1) := (others => 0);
Result : Long_Number (0..Left'Length + Right'Length - 1) := (others => 0);
Accum : Unsigned_64;
Accum : Unsigned_64;
begin
begin
for I in Left'Range loop
for I in Left'Range loop
for J in Right'Range loop
for J in Right'Range loop
Accum := Unsigned_64 (Left (I)) * Unsigned_64 (Right (J));
Accum := Unsigned_64 (Left (I)) * Unsigned_64 (Right (J));
for K in I + J..Result'Last loop
for K in I + J..Result'Last loop
exit when Accum = 0;
exit when Accum = 0;
Accum := Accum + Unsigned_64 (Result (K));
Accum := Accum + Unsigned_64 (Result (K));
Result (K) := Unsigned_32 (Accum and 16#FFFF_FFFF#);
Result (K) := Unsigned_32 (Accum and 16#FFFF_FFFF#);
Accum := Accum / 2**32;
Accum := Accum / 2**32;
⚫
end loop;
end loop;
end loop;
end loop;
end loop;
⚫
end loop;
⚫
for Index in reverse Result'Range loop -- Normalization
if Result (Index) /= 0 then
for Index in reverse Result'Range loop -- Normalization
return Result (0..Index);
if Result (Index) /= 0 then
end if;
return Result (0..Index);
end loop;
end if;
⚫
end loop;
return (0 => 0);
end "*";
return (0 => 0);
</lang>
end "*";</lang>
The task requires conversion into decimal base. For this we also need division to short number with a remainder. Here it is:
The task requires conversion into decimal base. For this we also need division to short number with a remainder. Here it is:
<lang ada>
<lang ada>procedure Div
( Dividend : in out Long_Number;
procedure Div
( Dividend : in out Long_Number;
Last : in out Natural;
Last : in out Natural;
Remainder : out Unsigned_32;
Remainder : out Unsigned_32;
Divisor : Unsigned_32
Divisor : Unsigned_32
) is
Div : constant Unsigned_64 := Unsigned_64 (Divisor);
) is
Div : constant Unsigned_64 := Unsigned_64 (Divisor);
Accum : Unsigned_64 := 0;
Accum : Unsigned_64 := 0;
Size : Natural := 0;
⚫
begin
Size : Natural := 0;
⚫
for Index in reverse Dividend'First..Last loop
⚫
begin
for Index in reverse Dividend'First..Last loop
Accum := Accum * 2**32 + Unsigned_64 (Dividend (Index));
Accum := Accum * 2**32 + Unsigned_64 (Dividend (Index));
Dividend (Index) := Unsigned_32 (Accum / Div);
Dividend (Index) := Unsigned_32 (Accum / Div);
if Size = 0 and then Dividend (Index) /= 0 then
if Size = 0 and then Dividend (Index) /= 0 then
Size := Index;
Size := Index;
end if;
end if;
Accum := Accum mod Div;
⚫
end loop;
Accum := Accum mod Div;
Remainder := Unsigned_32 (Accum);
⚫
end loop;
Remainder := Unsigned_32 (Accum);
Last := Size;
⚫
end Div;</lang>
Last := Size;
⚫
end Div;
⚫
</lang>
With the above the test program:
With the above the test program:
⚫
<lang ada>with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
<lang ada>
⚫
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Text_IO; use Ada.Text_IO;
with Interfaces; use Interfaces;
with Interfaces; use Interfaces;
Line 87: Line 82:
begin
begin
Put (X);
Put (X);
end Long_Multiplication;
end Long_Multiplication;</lang>
</lang>
Sample output:
Sample output:
<pre>
<pre>
Line 100: Line 94:
[[ALGOL 68G]] allows any precision for '''long long int''' to be defined
[[ALGOL 68G]] allows any precision for '''long long int''' to be defined
when the program is run, e.g. 200 digits.
when the program is run, e.g. 200 digits.
<lang algol>PRAGMAT precision=200 PRAGMAT
<lang algol68>PRAGMAT precision=200 PRAGMAT
MODE INTEGER = LONG LONG INT;
MODE INTEGER = LONG LONG INT;


Line 133: Line 127:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
<!-- {{does not works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386 - translator throws and assert. I'm not sure why.}} -->
<!-- {{does not works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386 - translator throws and assert. I'm not sure why.}} -->
<lang algol>MODE DIGIT = INT;
<lang algol68>MODE DIGIT = INT;
MODE INTEGER = FLEX[0]DIGIT; # an arbitary number of digits #
MODE INTEGER = FLEX[0]DIGIT; # an arbitary number of digits #


Line 226: Line 220:
IF leading zeros = UPB out THEN "0" ELSE sign + out[leading zeros+1:] FI
IF leading zeros = UPB out THEN "0" ELSE sign + out[leading zeros+1:] FI
);</lang>
);</lang>
<lang algol>################################################################
<lang algol68>################################################################
# Finally Define the required INTEGER multiplication OPerator. #
# Finally Define the required INTEGER multiplication OPerator. #
################################################################
################################################################
Line 249: Line 243:
NORMALISE ab
NORMALISE ab
);</lang>
);</lang>
<lang algol># The following standard operators could (potentially) also be defined #
<lang algol68># The following standard operators could (potentially) also be defined #
OP - = (INTEGER a)INTEGER: raise integer not implemented error("monadic minus"),
OP - = (INTEGER a)INTEGER: raise integer not implemented error("monadic minus"),
ABS = (INTEGER a)INTEGER: raise integer not implemented error("ABS"),
ABS = (INTEGER a)INTEGER: raise integer not implemented error("ABS"),
Retrieved from "https://rosettacode.org/wiki/Long_multiplication"