Long multiplication: Difference between revisions
Content added Content deleted
(added Ursala) |
(Ada solution added) |
||
Line 8: | Line 8: | ||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
=={{header|Ada}}== |
|||
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; |
|||
function "*" (Left, Right : Long_Number) return Long_Number is |
|||
Result : Long_Number (0..Left'Length + Right'Length - 1) := (others => 0); |
|||
Accum : Unsigned_64; |
|||
begin |
|||
for I in Left'Range loop |
|||
for J in Right'Range loop |
|||
Accum := Unsigned_64 (Left (I)) * Unsigned_64 (Right (J)); |
|||
for K in I + J..Result'Last loop |
|||
exit when Accum = 0; |
|||
Accum := Accum + Unsigned_64 (Result (K)); |
|||
Result (K) := Unsigned_32 (Accum and 16#FFFF_FFFF#); |
|||
Accum := Accum / 2**32; |
|||
end loop; |
|||
end loop; |
|||
end loop; |
|||
for Index in reverse Result'Range loop -- Normalization |
|||
if Result (Index) /= 0 then |
|||
return Result (0..Index); |
|||
end if; |
|||
end loop; |
|||
return (0 => 0); |
|||
end "*"; |
|||
</lang> |
|||
The task requires conversion into decimal base. For this we also need division to short number with a remainder. Here it is: |
|||
<lang ada> |
|||
procedure Div |
|||
( Dividend : in out Long_Number; |
|||
Last : in out Natural; |
|||
Remainder : out Unsigned_32; |
|||
Divisor : Unsigned_32 |
|||
) is |
|||
Div : constant Unsigned_64 := Unsigned_64 (Divisor); |
|||
Accum : Unsigned_64 := 0; |
|||
Size : Natural := 0; |
|||
begin |
|||
for Index in reverse Dividend'First..Last loop |
|||
Accum := Accum * 2**32 + Unsigned_64 (Dividend (Index)); |
|||
Dividend (Index) := Unsigned_32 (Accum / Div); |
|||
if Size = 0 and then Dividend (Index) /= 0 then |
|||
Size := Index; |
|||
end if; |
|||
Accum := Accum mod Div; |
|||
end loop; |
|||
Remainder := Unsigned_32 (Accum); |
|||
Last := Size; |
|||
end Div; |
|||
</lang> |
|||
With the above the test program: |
|||
<lang ada> |
|||
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
with Interfaces; use Interfaces; |
|||
procedure Long_Multiplication is |
|||
-- Insert definitions above here |
|||
procedure Put (Value : Long_Number) is |
|||
X : Long_Number := Value; |
|||
Last : Natural := X'Last; |
|||
Digit : Unsigned_32; |
|||
Result : Unbounded_String; |
|||
begin |
|||
loop |
|||
Div (X, Last, Digit, 10); |
|||
Append (Result, Character'Val (Digit + Character'Pos ('0'))); |
|||
exit when Last = 0 and then X (0) = 0; |
|||
end loop; |
|||
for Index in reverse 1..Length (Result) loop |
|||
Put (Element (Result, Index)); |
|||
end loop; |
|||
end Put; |
|||
X : Long_Number := (0 => 0, 1 => 0, 2 => 1) * (0 => 0, 1 => 0, 2 => 1); |
|||
begin |
|||
Put (X); |
|||
end Long_Multiplication; |
|||
</lang> |
|||
Sample output: |
|||
<pre> |
|||
340282366920938463463374607431768211456 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
The long multiplication for the golden ratio has been included as half the digits |
The long multiplication for the golden ratio has been included as half the digits |