Long multiplication: Difference between revisions
Content added Content deleted
m (→{{header|PL/I}}: Added syntax highlighting) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 23: | Line 23: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F add_with_carry(&result, =addend, =addendpos) |
||
L |
L |
||
L result.len < addendpos + 1 |
L result.len < addendpos + 1 |
||
Line 53: | Line 53: | ||
V sixtyfour = ‘18446744073709551616’ |
V sixtyfour = ‘18446744073709551616’ |
||
print(longhand_multiplication(sixtyfour, sixtyfour))</ |
print(longhand_multiplication(sixtyfour, sixtyfour))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 62: | Line 62: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
For maximum compatibility, we use only the basic 370 instruction set (use of MVCL). Pseudo-macro instruction XPRNT can be replaced by a WTO. |
For maximum compatibility, we use only the basic 370 instruction set (use of MVCL). Pseudo-macro instruction XPRNT can be replaced by a WTO. |
||
< |
<syntaxhighlight lang="360asm">LONGINT CSECT |
||
USING LONGINT,R13 |
USING LONGINT,R13 |
||
SAVEAREA B PROLOG-SAVEAREA(R15) |
SAVEAREA B PROLOG-SAVEAREA(R15) |
||
Line 334: | Line 334: | ||
LL EQU 94 |
LL EQU 94 |
||
YREGS |
YREGS |
||
END LONGINT</ |
END LONGINT</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 348: | Line 348: | ||
First we specify the required operations and declare our number type as an array of digits (in base 2^16): |
First we specify the required operations and declare our number type as an array of digits (in base 2^16): |
||
< |
<syntaxhighlight lang="ada">package Long_Multiplication is |
||
type Number (<>) is private; |
type Number (<>) is private; |
||
Line 381: | Line 381: | ||
Result : out Number; |
Result : out Number; |
||
Remainder : out Digit); |
Remainder : out Digit); |
||
end Long_Multiplication;</ |
end Long_Multiplication;</syntaxhighlight> |
||
Some of the operations declared above are useful helper operations for the conversion of numbers to and from base 10 digit strings. |
Some of the operations declared above are useful helper operations for the conversion of numbers to and from base 10 digit strings. |
||
Then we implement the operations: |
Then we implement the operations: |
||
< |
<syntaxhighlight lang="ada">package body Long_Multiplication is |
||
function Value (Item : in String) return Number is |
function Value (Item : in String) return Number is |
||
subtype Base_Ten_Digit is Digit range 0 .. 9; |
subtype Base_Ten_Digit is Digit range 0 .. 9; |
||
Line 529: | Line 529: | ||
return Zero; |
return Zero; |
||
end Trim; |
end Trim; |
||
end Long_Multiplication;</ |
end Long_Multiplication;</syntaxhighlight> |
||
And finally we have the requested test application: |
And finally we have the requested test application: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
with Long_Multiplication; |
with Long_Multiplication; |
||
Line 542: | Line 542: | ||
begin |
begin |
||
Put_Line (Image (N) & " * " & Image (N) & " = " & Image (M)); |
Put_Line (Image (N) & " * " & Image (N) & " = " & Image (M)); |
||
end Test_Long_Multiplication;</ |
end Test_Long_Multiplication;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 550: | Line 550: | ||
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: |
||
< |
<syntaxhighlight 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 |
||
Line 573: | Line 573: | ||
end loop; |
end loop; |
||
return (0 => 0); |
return (0 => 0); |
||
end "*";</ |
end "*";</syntaxhighlight> |
||
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: |
||
< |
<syntaxhighlight lang="ada">procedure Div |
||
( Dividend : in out Long_Number; |
( Dividend : in out Long_Number; |
||
Last : in out Natural; |
Last : in out Natural; |
||
Line 596: | Line 596: | ||
Remainder := Unsigned_32 (Accum); |
Remainder := Unsigned_32 (Accum); |
||
Last := Size; |
Last := Size; |
||
end Div;</ |
end Div;</syntaxhighlight> |
||
With the above the test program: |
With the above the test program: |
||
< |
<syntaxhighlight 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 624: | Line 624: | ||
begin |
begin |
||
Put (X); |
Put (X); |
||
end Long_Multiplication;</ |
end Long_Multiplication;</syntaxhighlight> |
||
Sample output: |
Sample output: |
||
Line 632: | Line 632: | ||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">data b, c, v; |
||
integer d, e, i, j, s; |
integer d, e, i, j, s; |
||
Line 670: | Line 670: | ||
} |
} |
||
o_form("~\n", c);</ |
o_form("~\n", c);</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 680: | Line 680: | ||
[[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. |
||
< |
<syntaxhighlight lang="algol68">PRAGMAT precision=200 PRAGMAT |
||
MODE INTEGER = LONG LONG INT; |
MODE INTEGER = LONG LONG INT; |
||
Line 700: | Line 700: | ||
INTEGER neg two to the power of 64 = -(LONG 2 ** 64); |
INTEGER neg two to the power of 64 = -(LONG 2 ** 64); |
||
print(("2 ** 64 * -(2 ** 64) = ", whole(two to the power of 64*neg two to the power of 64,width), new line)) |
print(("2 ** 64 * -(2 ** 64) = ", whole(two to the power of 64*neg two to the power of 64,width), new line)) |
||
)</ |
)</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 713: | Line 713: | ||
{{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.}} --> |
||
< |
<syntaxhighlight 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 805: | Line 805: | ||
# finally return the semi-normalised result # |
# finally return the semi-normalised result # |
||
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 |
||
);</ |
);</syntaxhighlight> |
||
< |
<syntaxhighlight lang="algol68">################################################################ |
||
# Finally Define the required INTEGER multiplication OPerator. # |
# Finally Define the required INTEGER multiplication OPerator. # |
||
################################################################ |
################################################################ |
||
Line 829: | Line 829: | ||
OD; |
OD; |
||
NORMALISE ab |
NORMALISE ab |
||
);</ |
);</syntaxhighlight> |
||
< |
<syntaxhighlight 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"), |
||
Line 860: | Line 860: | ||
INTEGER neg two to the power of 64 = INTEGERINIT(-(LONG 2 ** 64)); |
INTEGER neg two to the power of 64 = INTEGERINIT(-(LONG 2 ** 64)); |
||
print(("2 ** 64 * -(2 ** 64) = ", REPR (two to the power of 64 * neg two to the power of 64), new line)) |
print(("2 ** 64 * -(2 ** 64) = ", REPR (two to the power of 64 * neg two to the power of 64), new line)) |
||
)</ |
)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 874: | Line 874: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% long multiplication of large integers % |
% long multiplication of large integers % |
||
% large integers are represented by arrays of integers whose absolute % |
% large integers are represented by arrays of integers whose absolute % |
||
Line 985: | Line 985: | ||
writeonLargeInteger( twoTo128, ELEMENT_COUNT ) |
writeonLargeInteger( twoTo128, ELEMENT_COUNT ) |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 993: | Line 993: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
<lang |
<syntaxhighlight lang="rebol">print 2^64 * 2</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,001: | Line 1,001: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=149 discussion] |
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=149 discussion] |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox % x := mul(256,256) |
||
MsgBox % x := mul(x,x) |
MsgBox % x := mul(x,x) |
||
MsgBox % x := mul(x,x) ; 18446744073709551616 |
MsgBox % x := mul(x,x) ; 18446744073709551616 |
||
Line 1,019: | Line 1,019: | ||
} |
} |
||
Return cy ? a : SubStr(a,2) |
Return cy ? a : SubStr(a,2) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Line 1,025: | Line 1,025: | ||
{{works with|nawk|20100523}} |
{{works with|nawk|20100523}} |
||
{{trans|Tcl}} |
{{trans|Tcl}} |
||
< |
<syntaxhighlight lang="awk">BEGIN { |
||
DEBUG = 0 |
DEBUG = 0 |
||
n = 2^64 |
n = 2^64 |
||
Line 1,112: | Line 1,112: | ||
print "====" |
print "====" |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
outputs: |
outputs: |
||
<pre>2^64 * 2^64 = 340282366920938463463374607431768211456 |
<pre>2^64 * 2^64 = 340282366920938463463374607431768211456 |
||
Line 1,121: | Line 1,121: | ||
===Version 1=== |
===Version 1=== |
||
< |
<syntaxhighlight lang="qbasic">'PROGRAM : BIG MULTIPLICATION VER #1 |
||
'LRCVS 01.01.2010 |
'LRCVS 01.01.2010 |
||
'THIS PROGRAM SIMPLY MAKES A MULTIPLICATION |
'THIS PROGRAM SIMPLY MAKES A MULTIPLICATION |
||
Line 1,267: | Line 1,267: | ||
CLS |
CLS |
||
PRINT "THE SOLUTION IN THE FILE: R" |
PRINT "THE SOLUTION IN THE FILE: R" |
||
END SUB</ |
END SUB</syntaxhighlight> |
||
===Version 2=== |
===Version 2=== |
||
<!-- I'm not sure what the difference is; don't feel like reading through them, I was just making sure they work and bughunting. --> |
<!-- I'm not sure what the difference is; don't feel like reading through them, I was just making sure they work and bughunting. --> |
||
< |
<syntaxhighlight lang="qbasic">'PROGRAM: BIG MULTIPLICATION VER # 2 |
||
'LRCVS 01/01/2010 |
'LRCVS 01/01/2010 |
||
'THIS PROGRAM SIMPLY MAKES A BIG MULTIPLICATION |
'THIS PROGRAM SIMPLY MAKES A BIG MULTIPLICATION |
||
Line 1,377: | Line 1,377: | ||
NEXT N |
NEXT N |
||
PRINT "END" |
PRINT "END" |
||
PRINT "THE SOLUTION IN THE FILE: R.MLT"</ |
PRINT "THE SOLUTION IN THE FILE: R.MLT"</syntaxhighlight> |
||
==={{header|Applesoft BASIC}}=== |
==={{header|Applesoft BASIC}}=== |
||
< |
<syntaxhighlight lang="applesoftbasic"> 100 A$ = "18446744073709551616" |
||
110 B$ = A$ |
110 B$ = A$ |
||
120 GOSUB 400 |
120 GOSUB 400 |
||
Line 1,412: | Line 1,412: | ||
680 NEXT J |
680 NEXT J |
||
700 IF E THEN V = VAL ( MID$ (D$,E,1)) + C:C = V > 9:V = V - 10 * C:E$ = STR$ (V) + E$:E = E - 1: GOTO 700 |
700 IF E THEN V = VAL ( MID$ (D$,E,1)) + C:C = V > 9:V = V - 10 * C:E$ = STR$ (V) + E$:E = E - 1: GOTO 700 |
||
720 RETURN</ |
720 RETURN</syntaxhighlight> |
||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
Based on the JavaScript iterative code. |
Based on the JavaScript iterative code. |
||
< |
<syntaxhighlight lang="dos">::Long Multiplication Task from Rosetta Code |
||
::Batch File Implementation |
::Batch File Implementation |
||
Line 1,473: | Line 1,473: | ||
for /l %%F in (0,1,%length%) do set "prod=!digit%%F!!prod!" |
for /l %%F in (0,1,%length%) do set "prod=!digit%%F!!prod!" |
||
endlocal & set "%3=%prod%" |
endlocal & set "%3=%prod%" |
||
goto :eof</ |
goto :eof</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>340282366920938463463374607431768211456</pre> |
<pre>340282366920938463463374607431768211456</pre> |
||
Line 1,480: | Line 1,480: | ||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
Library method: |
Library method: |
||
< |
<syntaxhighlight lang="bbcbasic"> INSTALL @lib$+"BB4WMAPMLIB" |
||
MAPM_DllPath$ = @lib$+"BB4WMAPM.DLL" |
MAPM_DllPath$ = @lib$+"BB4WMAPM.DLL" |
||
PROCMAPM_Init |
PROCMAPM_Init |
||
twoto64$ = "18446744073709551616" |
twoto64$ = "18446744073709551616" |
||
PRINT "2^64 * 2^64 = " ; FNMAPM_Multiply(twoto64$, twoto64$)</ |
PRINT "2^64 * 2^64 = " ; FNMAPM_Multiply(twoto64$, twoto64$)</syntaxhighlight> |
||
Explicit method: |
Explicit method: |
||
< |
<syntaxhighlight lang="bbcbasic"> twoto64$ = "18446744073709551616" |
||
PRINT "2^64 * 2^64 = " ; FNlongmult(twoto64$, twoto64$) |
PRINT "2^64 * 2^64 = " ; FNlongmult(twoto64$, twoto64$) |
||
END |
END |
||
Line 1,514: | Line 1,514: | ||
num3&(S%) = 0 |
num3&(S%) = 0 |
||
IF num3&(0) = &30 THEN = $$^num3&(1) |
IF num3&(0) = &30 THEN = $$^num3&(1) |
||
= $$^num3&(0)</ |
= $$^num3&(0)</syntaxhighlight> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Doing it as if by hand. |
Doing it as if by hand. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 1,572: | Line 1,572: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight>output<syntaxhighlight lang="text">340282366920938463463374607431768211456</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{works with|C sharp|C#|4+}}If you strip out the ''BigInteger'' checking, it will work with lesser versions.<br/><br/>This uses the '''decimal''' type, (which has a '''MaxValue''' of 79,228,162,514,264,337,593,543,950,335). By limiting it to '''10^28''', it allows 28 decimal digits for the ''hi'' part, and 28 decimal digits for the ''lo'' part, '''56 decimal digits''' total. A side computation of ''BigInteger'' assures that the results are accurate. |
{{works with|C sharp|C#|4+}}If you strip out the ''BigInteger'' checking, it will work with lesser versions.<br/><br/>This uses the '''decimal''' type, (which has a '''MaxValue''' of 79,228,162,514,264,337,593,543,950,335). By limiting it to '''10^28''', it allows 28 decimal digits for the ''hi'' part, and 28 decimal digits for the ''lo'' part, '''56 decimal digits''' total. A side computation of ''BigInteger'' assures that the results are accurate. |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using static System.Console; |
using static System.Console; |
||
using BI = System.Numerics.BigInteger; |
using BI = System.Numerics.BigInteger; |
||
Line 1,615: | Line 1,615: | ||
BS.ToString() == toStr(y) ? "does" : "fails to"); } } |
BS.ToString() == toStr(y) ? "does" : "fails to"); } } |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The square of (2^64): 18,446,744,073,709,551,616 |
<pre>The square of (2^64): 18,446,744,073,709,551,616 |
||
Line 1,625: | Line 1,625: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
===Version 1=== |
===Version 1=== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
#include <sstream> |
#include <sstream> |
||
Line 1,706: | Line 1,706: | ||
} |
} |
||
//-------------------------------------------------------------------------------------------------- |
//-------------------------------------------------------------------------------------------------- |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>340282366920938463463374607431768211456 |
<pre>340282366920938463463374607431768211456 |
||
Line 1,717: | Line 1,717: | ||
===Version 2=== |
===Version 2=== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 1,784: | Line 1,784: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
<pre> |
<pre> |
||
Line 1,797: | Line 1,797: | ||
=={{header|Ceylon}}== |
=={{header|Ceylon}}== |
||
< |
<syntaxhighlight lang="ceylon">"run() is the main function of this module." |
||
shared void run() { |
shared void run() { |
||
Line 1,854: | Line 1,854: | ||
print("The actual result is ``result``"); |
print("The actual result is ``result``"); |
||
print("Do they match? ``expectedResult == result then "Yes!" else "No!"``"); |
print("Do they match? ``expectedResult == result then "Yes!" else "No!"``"); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|COBOL}}== |
=={{header|COBOL}}== |
||
<syntaxhighlight lang="cobol"> |
|||
<lang COBOL> |
|||
identification division. |
identification division. |
||
program-id. long-mul. |
program-id. long-mul. |
||
Line 1,946: | Line 1,946: | ||
end program long-mul. |
end program long-mul. |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Line 1,955: | Line 1,955: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
# This very limited BCD-based collection of functions |
# This very limited BCD-based collection of functions |
||
# allows for long multiplication. It works for positive |
# allows for long multiplication. It works for positive |
||
Line 2,020: | Line 2,020: | ||
square = BcdInteger.product x, x |
square = BcdInteger.product x, x |
||
console.log BcdInteger.to_string square # 340282366920938463463374607431768211456 |
console.log BcdInteger.to_string square # 340282366920938463463374607431768211456 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun number->digits (number) |
||
(do ((digits '())) ((zerop number) digits) |
(do ((digits '())) ((zerop number) digits) |
||
(multiple-value-bind (quotient remainder) (floor number 10) |
(multiple-value-bind (quotient remainder) (floor number 10) |
||
Line 2,062: | Line 2,062: | ||
(let* ((bi (pop b)) |
(let* ((bi (pop b)) |
||
(row (mapcar #'(lambda (ai) (* ai bi)) a))) |
(row (mapcar #'(lambda (ai) (* ai bi)) a))) |
||
(push (append prefix row) rows)))))</ |
(push (append prefix row) rows)))))</syntaxhighlight> |
||
> (long-multiply (expt 2 64) (expt 2 64)) |
> (long-multiply (expt 2 64) (expt 2 64)) |
||
Line 2,069: | Line 2,069: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
< |
<syntaxhighlight lang="ruby">require "big" |
||
a = 2.to_big_i ** 64 |
a = 2.to_big_i ** 64 |
||
puts "#{a} * #{a} = #{a*a}" |
puts "#{a} * #{a} = #{a*a}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,081: | Line 2,081: | ||
=={{header|D}}== |
=={{header|D}}== |
||
Using the standard library: |
Using the standard library: |
||
< |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio, std.bigint; |
import std.stdio, std.bigint; |
||
writeln(2.BigInt ^^ 64 * 2.BigInt ^^ 64); |
writeln(2.BigInt ^^ 64 * 2.BigInt ^^ 64); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>340282366920938463463374607431768211456</pre> |
<pre>340282366920938463463374607431768211456</pre> |
||
Long multiplication, same output: |
Long multiplication, same output: |
||
{{trans|JavaScript}} |
{{trans|JavaScript}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.ascii, std.string; |
||
auto longMult(in string x1, in string x2) pure nothrow @safe { |
auto longMult(in string x1, in string x2) pure nothrow @safe { |
||
Line 2,120: | Line 2,120: | ||
immutable two64 = "18446744073709551616"; |
immutable two64 = "18446744073709551616"; |
||
longMult(two64, two64).writeln; |
longMult(two64, two64).writeln; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Dc}}== |
=={{header|Dc}}== |
||
{{incorrect|Dc|Code does not explicitly implement long multiplication}} |
{{incorrect|Dc|Code does not explicitly implement long multiplication}} |
||
Since Dc has arbitrary precision built-in, the task is no different than a normal multiplication: |
Since Dc has arbitrary precision built-in, the task is no different than a normal multiplication: |
||
< |
<syntaxhighlight lang="dc">2 64^ 2 64^ *p</syntaxhighlight> |
||
{{incorrect|Dc|A Dc solution might be: Represent bignums as numerical strings and implement arithmetic functions on them.}} |
{{incorrect|Dc|A Dc solution might be: Represent bignums as numerical strings and implement arithmetic functions on them.}} |
||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
Line 2,131: | Line 2,131: | ||
{{Trans|Go}} |
{{Trans|Go}} |
||
Copy of core Go answer. |
Copy of core Go answer. |
||
<syntaxhighlight lang="delphi"> |
|||
<lang Delphi> |
|||
program Long_multiplication; |
program Long_multiplication; |
||
Line 2,282: | Line 2,282: | ||
Writeln(validate); |
Writeln(validate); |
||
Readln; |
Readln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>340282366920938463463374607431768211456 |
<pre>340282366920938463463374607431768211456 |
||
Line 2,289: | Line 2,289: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
We implement long multiplication by multiplying polynomials, knowing that the number 1234 is the polynomial x^3 +2x^2 +3x +4 at x=10. As we assume no bigint library is present, long-mul operates on strings. |
We implement long multiplication by multiplying polynomials, knowing that the number 1234 is the polynomial x^3 +2x^2 +3x +4 at x=10. As we assume no bigint library is present, long-mul operates on strings. |
||
< |
<syntaxhighlight lang="lisp"> |
||
(lib 'math) ;; for poly multiplication |
(lib 'math) ;; for poly multiplication |
||
Line 2,331: | Line 2,331: | ||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
< |
<syntaxhighlight lang="euphoria">constant base = 1000000000 |
||
function atom_to_long(atom a) |
function atom_to_long(atom a) |
||
Line 2,391: | Line 2,391: | ||
c = long_mult(b,b) |
c = long_mult(b,b) |
||
printf(1,"a*a*a*a is %s\n",{long_to_str(c)})</ |
printf(1,"a*a*a*a is %s\n",{long_to_str(c)})</syntaxhighlight> |
||
Output: |
Output: |
||
Line 2,402: | Line 2,402: | ||
{{incorrect|F#|The problem is to implement long multiplication, not to demonstrate bignum support.}} |
{{incorrect|F#|The problem is to implement long multiplication, not to demonstrate bignum support.}} |
||
< |
<syntaxhighlight lang="f#">> let X = 2I ** 64 * 2I ** 64 ;; |
||
val X : System.Numerics.BigInteger = 340282366920938463463374607431768211456 |
val X : System.Numerics.BigInteger = 340282366920938463463374607431768211456 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: kernel math sequences ; |
||
: longmult-seq ( xs ys -- zs ) |
: longmult-seq ( xs ys -- zs ) |
||
Line 2,419: | Line 2,419: | ||
: digits->integer ( xs -- x ) 0 [ swap 10 * + ] reduce ; |
: digits->integer ( xs -- x ) 0 [ swap 10 * + ] reduce ; |
||
: longmult ( x y -- z ) [ integer->digits ] bi@ longmult-seq digits->integer ;</ |
: longmult ( x y -- z ) [ integer->digits ] bi@ longmult-seq digits->integer ;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="factor">( scratchpad ) 2 64 ^ dup longmult . |
||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
( scratchpad ) 2 64 ^ dup * . |
( scratchpad ) 2 64 ^ dup * . |
||
340282366920938463463374607431768211456</ |
340282366920938463463374607431768211456</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|95 and later}} |
{{works with|Fortran|95 and later}} |
||
< |
<syntaxhighlight lang="fortran">module LongMoltiplication |
||
implicit none |
implicit none |
||
Line 2,501: | Line 2,501: | ||
end subroutine longmolt_print |
end subroutine longmolt_print |
||
end module LongMoltiplication</ |
end module LongMoltiplication</syntaxhighlight> |
||
< |
<syntaxhighlight lang="fortran">program Test |
||
use LongMoltiplication |
use LongMoltiplication |
||
Line 2,515: | Line 2,515: | ||
write(*,*) |
write(*,*) |
||
end program Test</ |
end program Test</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 08-01-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 2,612: | Line 2,612: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 ^ 2 = 4 |
<pre>2 ^ 2 = 4 |
||
Line 2,627: | Line 2,627: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">// Long multiplication per WP article referenced by task description. |
||
// That is, multiplicand is multiplied by single digits of multiplier |
// That is, multiplicand is multiplied by single digits of multiplier |
||
// to form intermediate results. Intermediate results are accumulated |
// to form intermediate results. Intermediate results are accumulated |
||
Line 2,705: | Line 2,705: | ||
func main() { |
func main() { |
||
fmt.Println(mul(n, n)) |
fmt.Println(mul(n, n)) |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,712: | Line 2,712: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (transpose, inits) |
||
import Data.Char (digitToInt) |
import Data.Char (digitToInt) |
||
Line 2,731: | Line 2,731: | ||
main :: IO () |
main :: IO () |
||
main = print $ (2 ^ 64) `longmult` (2 ^ 64)</ |
main = print $ (2 ^ 64) `longmult` (2 ^ 64)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>340282366920938463463374607431768211456</pre> |
<pre>340282366920938463463374607431768211456</pre> |
||
Line 2,737: | Line 2,737: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Large integers are native to Icon and Unicon. Neither libraries nor special programming is required. |
Large integers are native to Icon and Unicon. Neither libraries nor special programming is required. |
||
< |
<syntaxhighlight lang="icon">procedure main() |
||
write(2^64*2^64) |
write(2^64*2^64) |
||
end</ |
end</syntaxhighlight> |
||
{{output}}<pre>340282366920938463463374607431768211456</pre> |
{{output}}<pre>340282366920938463463374607431768211456</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
'''Solution:''' |
'''Solution:''' |
||
< |
<syntaxhighlight lang="j"> digits =: ,.&.": |
||
polymult =: +//.@(*/) |
polymult =: +//.@(*/) |
||
buildDecimal=: 10x&#. |
buildDecimal=: 10x&#. |
||
longmult=: buildDecimal@polymult&digits</ |
longmult=: buildDecimal@polymult&digits</syntaxhighlight> |
||
'''Example:''' |
'''Example:''' |
||
< |
<syntaxhighlight lang="j"> longmult~ 2x^64 |
||
340282366920938463463374607431768211456</ |
340282366920938463463374607431768211456</syntaxhighlight> |
||
'''Alternatives:'''<br> |
'''Alternatives:'''<br> |
||
<code>longmult</code> could have been defined concisely: |
<code>longmult</code> could have been defined concisely: |
||
< |
<syntaxhighlight lang="j">longmult=: 10x&#.@(+//.@(*/)&(,.&.":))</syntaxhighlight> |
||
Or, of course, the task may be accomplished without the verb definitions: |
Or, of course, the task may be accomplished without the verb definitions: |
||
< |
<syntaxhighlight lang="j"> 10x&#.@(+//.@(*/)&(,.&.":))~2x^64 |
||
340282366920938463463374607431768211456</ |
340282366920938463463374607431768211456</syntaxhighlight> |
||
Or using the code <code>(+ 10x&*)/@|.</code> instead of <code>#.</code>: |
Or using the code <code>(+ 10x&*)/@|.</code> instead of <code>#.</code>: |
||
< |
<syntaxhighlight lang="j"> (+ 10x&*)/@|.@(+//.@(*/)&(,.&.":))~2x^64 |
||
340282366920938463463374607431768211456</ |
340282366920938463463374607431768211456</syntaxhighlight> |
||
Or you could use the built-in language support for arbitrary precision multiplication: |
Or you could use the built-in language support for arbitrary precision multiplication: |
||
< |
<syntaxhighlight lang="j"> (2x^64)*(2x^64) |
||
340282366920938463463374607431768211456</ |
340282366920938463463374607431768211456</syntaxhighlight> |
||
'''Explaining the component verbs:''' |
'''Explaining the component verbs:''' |
||
* <code>digits</code> translates a number to a corresponding list of digits; |
* <code>digits</code> translates a number to a corresponding list of digits; |
||
< |
<syntaxhighlight lang="j"> ,.&.": 123 |
||
1 2 3</ |
1 2 3</syntaxhighlight> |
||
* <code>polymult</code> (multiplies polynomials): '''ref.''' [http://www.jsoftware.com/help/dictionary/samp23.htm] |
* <code>polymult</code> (multiplies polynomials): '''ref.''' [http://www.jsoftware.com/help/dictionary/samp23.htm] |
||
< |
<syntaxhighlight lang="j"> 1 2 3 (+//.@(*/)) 1 2 3 |
||
1 4 10 12 9</ |
1 4 10 12 9</syntaxhighlight> |
||
* <code>buildDecimal</code> (translates a list of decimal digits - possibly including "carry" - to the corresponding extended precision number): |
* <code>buildDecimal</code> (translates a list of decimal digits - possibly including "carry" - to the corresponding extended precision number): |
||
< |
<syntaxhighlight lang="j"> (+ 10x&*)/|. 1 4 10 12 9 |
||
15129</ |
15129</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
Line 2,783: | Line 2,783: | ||
This version of the code keeps the data in base ten. By doing this, we can avoid converting the whole number to binary and we can keep things simple, but the runtime will be suboptimal. |
This version of the code keeps the data in base ten. By doing this, we can avoid converting the whole number to binary and we can keep things simple, but the runtime will be suboptimal. |
||
< |
<syntaxhighlight lang="java">public class LongMult { |
||
private static byte[] stringToDigits(String num) { |
private static byte[] stringToDigits(String num) { |
||
Line 2,834: | Line 2,834: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Binary version=== |
===Binary version=== |
||
Line 2,840: | Line 2,840: | ||
This version tries to be as efficient as possible, so it converts numbers into binary before doing any calculations. The complexity is higher because of the need to convert to and from base ten, which requires the implementation of some additional arithmetic operations beyond long multiplication itself. |
This version tries to be as efficient as possible, so it converts numbers into binary before doing any calculations. The complexity is higher because of the need to convert to and from base ten, which requires the implementation of some additional arithmetic operations beyond long multiplication itself. |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
public class LongMultBinary { |
public class LongMultBinary { |
||
Line 3,045: | Line 3,045: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 3,059: | Line 3,059: | ||
This means that to handle larger inputs, the multiplication function needs to have string parameters: |
This means that to handle larger inputs, the multiplication function needs to have string parameters: |
||
< |
<syntaxhighlight lang="javascript">function mult(strNum1,strNum2){ |
||
var a1 = strNum1.split("").reverse(); |
var a1 = strNum1.split("").reverse(); |
||
Line 3,080: | Line 3,080: | ||
mult('18446744073709551616', '18446744073709551616')</ |
mult('18446744073709551616', '18446744073709551616')</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 3,091: | Line 3,091: | ||
For the same reason, the output always takes the form of an arbitrary precision integer string, rather than a native integer data type. (See the '''largeIntegerString()''' helper function below) |
For the same reason, the output always takes the form of an arbitrary precision integer string, rather than a native integer data type. (See the '''largeIntegerString()''' helper function below) |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
'use strict'; |
'use strict'; |
||
Line 3,180: | Line 3,180: | ||
) |
) |
||
}; |
}; |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{"fromIntegerStrings":"340282366920938463463374607431768211456", |
<pre>{"fromIntegerStrings":"340282366920938463463374607431768211456", |
||
Line 3,188: | Line 3,188: | ||
{{Works with|jq|1.4}} |
{{Works with|jq|1.4}} |
||
Since the task description mentions 2^64, the following includes "long_power(i)" for computing n^i. |
Since the task description mentions 2^64, the following includes "long_power(i)" for computing n^i. |
||
< |
<syntaxhighlight lang="jq"># multiply two decimal strings, which may be signed (+ or -) |
||
def long_multiply(num1; num2): |
def long_multiply(num1; num2): |
||
Line 3,233: | Line 3,233: | ||
elif $a2[1] == "1" then $a1[1]|adjustsign( $a1[0] * $a2[0] ) |
elif $a2[1] == "1" then $a1[1]|adjustsign( $a1[0] * $a2[0] ) |
||
else mult($a1[1]; $a2[1]) | adjustsign( $a1[0] * $a2[0] ) |
else mult($a1[1]; $a2[1]) | adjustsign( $a1[0] * $a2[0] ) |
||
end;</ |
end;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq"># Emit (input)^i where input and i are non-negative decimal integers, |
||
# represented as numbers and/or strings. |
# represented as numbers and/or strings. |
||
def long_power(i): |
def long_power(i): |
||
Line 3,251: | Line 3,251: | ||
| ($i - $j*$j) as $k |
| ($i - $j*$j) as $k |
||
| long_multiply( power($j) | power($j) ; power($k) ) |
| long_multiply( power($j) | power($j) ; power($k) ) |
||
end ;</ |
end ;</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
< |
<syntaxhighlight lang="jq"> 2 | long_power(64) | long_multiply(.;.)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
$ jq -n -f Long_multiplication.jq |
$ jq -n -f Long_multiplication.jq |
||
Line 3,263: | Line 3,263: | ||
'''Module''': |
'''Module''': |
||
< |
<syntaxhighlight lang="julia">module LongMultiplication |
||
using Compat |
using Compat |
||
Line 3,307: | Line 3,307: | ||
end |
end |
||
end # module LongMultiplication</ |
end # module LongMultiplication</syntaxhighlight> |
||
'''Main''': |
'''Main''': |
||
< |
<syntaxhighlight lang="julia">@show LongMultiplication.longmult(big(2) ^ 64, big(2) ^ 64) |
||
@show LongMultiplication.longmult("18446744073709551616", "18446744073709551616")</ |
@show LongMultiplication.longmult("18446744073709551616", "18446744073709551616")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,319: | Line 3,319: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">fun String.toDigits() = mapIndexed { i, c -> |
||
if (!c.isDigit()) |
if (!c.isDigit()) |
||
throw IllegalArgumentException("Invalid digit $c found at position $i") |
throw IllegalArgumentException("Invalid digit $c found at position $i") |
||
Line 3,354: | Line 3,354: | ||
fun main(args: Array<out String>) { |
fun main(args: Array<out String>) { |
||
println("18446744073709551616" * "18446744073709551616") |
println("18446744073709551616" * "18446744073709551616") |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
Natural positive numbers are defined as strings, for instance 123 -> "123". |
Natural positive numbers are defined as strings, for instance 123 -> "123". |
||
{lambda talk} has a small set of primitives working on strings, [equal?, empty?, chars, charAt, substring] |
{lambda talk} has a small set of primitives working on strings, [equal?, empty?, chars, charAt, substring] |
||
Line 3,436: | Line 3,436: | ||
This can be tested in http://lambdaway.free.fr/lambdaspeech/?view=numbers8 |
This can be tested in http://lambdaway.free.fr/lambdaspeech/?view=numbers8 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang="lb"> |
|||
<lang lb> |
|||
'[RC] long multiplication |
'[RC] long multiplication |
||
Line 3,531: | Line 3,531: | ||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
||
{{trans|Java}} Translation of Java binary version, but with base 1000000000 |
{{trans|Java}} Translation of Java binary version, but with base 1000000000 |
||
< |
<syntaxhighlight lang="lobster">import std |
||
// Very basic arbitrary-precision integers |
// Very basic arbitrary-precision integers |
||
Line 3,648: | Line 3,648: | ||
var pro = one.bign_multiply(two) |
var pro = one.bign_multiply(two) |
||
print(bign2str(pro)) |
print(bign2str(pro)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,655: | Line 3,655: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
longmult := proc(a::integer,b::integer) |
longmult := proc(a::integer,b::integer) |
||
local A,B,m,n,i,j; |
local A,B,m,n,i,j; |
||
Line 3,668: | Line 3,668: | ||
> longmult( 2^64, 2^64 ); |
> longmult( 2^64, 2^64 ); |
||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
We define the long multiplication function: |
We define the long multiplication function: |
||
< |
<syntaxhighlight lang="mathematica"> LongMultiplication[a_,b_]:=Module[{d1,d2}, |
||
d1=IntegerDigits[a]//Reverse; |
d1=IntegerDigits[a]//Reverse; |
||
d2=IntegerDigits[b]//Reverse; |
d2=IntegerDigits[b]//Reverse; |
||
Sum[d1[[i]]d2[[j]]*10^(i+j-2),{i,1,Length[d1]},{j,1,Length[d2]}] |
Sum[d1[[i]]d2[[j]]*10^(i+j-2),{i,1,Length[d1]},{j,1,Length[d2]}] |
||
]</ |
]</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang="mathematica"> n1 = 2^64; |
||
n2 = 2^64; |
n2 = 2^64; |
||
LongMultiplication[n1, n2]</ |
LongMultiplication[n1, n2]</syntaxhighlight> |
||
gives back: |
gives back: |
||
<lang |
<syntaxhighlight lang="mathematica"> 340282366920938463463374607431768211456</syntaxhighlight> |
||
To check the speed difference between built-in multiplication (which is already arbitrary precision) we multiply two big numbers (2^8000 has '''2409''' digits!) and divide their timings: |
To check the speed difference between built-in multiplication (which is already arbitrary precision) we multiply two big numbers (2^8000 has '''2409''' digits!) and divide their timings: |
||
< |
<syntaxhighlight lang="mathematica"> n1=2^8000; |
||
n2=2^8000; |
n2=2^8000; |
||
Timing[LongMultiplication[n1,n2]][[1]] |
Timing[LongMultiplication[n1,n2]][[1]] |
||
Timing[n1 n2][[1]] |
Timing[n1 n2][[1]] |
||
Floor[%%/%]</ |
Floor[%%/%]</syntaxhighlight> |
||
gives back: |
gives back: |
||
< |
<syntaxhighlight lang="mathematica"> 72.9686 |
||
7.*10^-6 |
7.*10^-6 |
||
10424088</ |
10424088</syntaxhighlight> |
||
So our custom function takes about 73 second, the built-in function a couple of millionths of a second, so the long multiplication is about 10.5 million times slower! Mathematica uses Karatsuba multiplication for large integers, which is several magnitudes faster for really big numbers. Making it able to multiply <math>3^{(10^7)}\times3^{(10^7)}</math> in about a second; the final result has 9542426 digits; result omitted for obvious reasons. |
So our custom function takes about 73 second, the built-in function a couple of millionths of a second, so the long multiplication is about 10.5 million times slower! Mathematica uses Karatsuba multiplication for large integers, which is several magnitudes faster for really big numbers. Making it able to multiply <math>3^{(10^7)}\times3^{(10^7)}</math> in about a second; the final result has 9542426 digits; result omitted for obvious reasons. |
||
Line 3,703: | Line 3,703: | ||
{{trans|REXX}} |
{{trans|REXX}} |
||
A reworking of the example at Rexx Version 2. |
A reworking of the example at Rexx Version 2. |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 3,784: | Line 3,784: | ||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,814: | Line 3,814: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="nim">import strutils |
||
proc ti(a: char): int = ord(a) - ord('0') |
proc ti(a: char): int = ord(a) - ord('0') |
||
Line 3,854: | Line 3,854: | ||
result[0..result.high-1] = result[1..result.high] |
result[0..result.high-1] = result[1..result.high] |
||
echo longmulti("-18446744073709551616", "-18446744073709551616")</ |
echo longmulti("-18446744073709551616", "-18446744073709551616")</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>3402823669209384634633746074317682114566</pre> |
<pre>3402823669209384634633746074317682114566</pre> |
||
Line 3,876: | Line 3,876: | ||
Just multiplication is implemented here. |
Just multiplication is implemented here. |
||
< |
<syntaxhighlight lang="oforth">Number Class new: Natural(v) |
||
Natural method: initialize := v ; |
Natural method: initialize := v ; |
||
Line 3,903: | Line 3,903: | ||
| i | |
| i | |
||
@v last << |
@v last << |
||
@v size 1 - loop: i [ @v at(@v size i -) <<wjp(0, JUSTIFY_RIGHT, 8) ] ;</ |
@v size 1 - loop: i [ @v at(@v size i -) <<wjp(0, JUSTIFY_RIGHT, 8) ] ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,927: | Line 3,927: | ||
Ol already supports long numbers "out-of-the-box". |
Ol already supports long numbers "out-of-the-box". |
||
< |
<syntaxhighlight lang="scheme"> |
||
(define x (* 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)) ; 2^64 |
(define x (* 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)) ; 2^64 |
||
(print (* x x)) |
(print (* x x)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
Line 3,937: | Line 3,937: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">long(a,b)={ |
||
a=eval(Vec(a)); |
a=eval(Vec(a)); |
||
b=eval(Vec(b)); |
b=eval(Vec(b)); |
||
Line 3,956: | Line 3,956: | ||
"0" |
"0" |
||
}; |
}; |
||
long("18446744073709551616","18446744073709551616")</ |
long("18446744073709551616","18446744073709551616")</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>%1 = "340282366920938463463374607431768211456"</pre> |
<pre>%1 = "340282366920938463463374607431768211456"</pre> |
||
Line 3,962: | Line 3,962: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
Extracted from a programme to calculate and factor the number (two versions) in Frederick Pohl's book ''The Gold at the Starbow's End'', and compute Godel encodings of text. Compiles with the Free Pascal Compiler. The original would compile with Turbo Pascal (and used pointers to allow access to the "heap" storage scheme) except that does not allow functions to return a "big number" data aggregate, and it is so much nicer to be able to write X:=BigMult(A,B); The original has a special "square" calculation but this task is to exhibit long multiplication. However, raising to a power by iteration is painful, so a special routine for that. |
Extracted from a programme to calculate and factor the number (two versions) in Frederick Pohl's book ''The Gold at the Starbow's End'', and compute Godel encodings of text. Compiles with the Free Pascal Compiler. The original would compile with Turbo Pascal (and used pointers to allow access to the "heap" storage scheme) except that does not allow functions to return a "big number" data aggregate, and it is so much nicer to be able to write X:=BigMult(A,B); The original has a special "square" calculation but this task is to exhibit long multiplication. However, raising to a power by iteration is painful, so a special routine for that. |
||
<syntaxhighlight lang="pascal"> |
|||
<lang Pascal> |
|||
Program TwoUp; Uses DOS, crt; |
Program TwoUp; Uses DOS, crt; |
||
{Concocted by R.N.McLean (whom God preserve), Victoria university, NZ.} |
{Concocted by R.N.McLean (whom God preserve), Victoria university, NZ.} |
||
Line 4,100: | Line 4,100: | ||
Write ('x*x = ');BigShow(X); {Can't have Write('x*x = ',BigShow(BigMult(X,X))), after all. Oh well.} |
Write ('x*x = ');BigShow(X); {Can't have Write('x*x = ',BigShow(BigMult(X,X))), after all. Oh well.} |
||
END. |
END. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 4,108: | Line 4,108: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl -w |
||
use strict; |
use strict; |
||
Line 4,162: | Line 4,162: | ||
my $onetwentyeight = &longhand_multiplication($sixtyfour, $sixtyfour); |
my $onetwentyeight = &longhand_multiplication($sixtyfour, $sixtyfour); |
||
print "$onetwentyeight\n";</ |
print "$onetwentyeight\n";</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 4,170: | Line 4,170: | ||
If bcd1 is a number split into digits 0..9, bcd9 is a number split into "digits" 000,000,000..999,999,999, which fit in an integer.<br> |
If bcd1 is a number split into digits 0..9, bcd9 is a number split into "digits" 000,000,000..999,999,999, which fit in an integer.<br> |
||
They are held lsb-style mainly so that trimming a trailing 0 does not alter their value. |
They are held lsb-style mainly so that trimming a trailing 0 does not alter their value. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1_000_000_000</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1_000_000_000</span> |
||
Line 4,223: | Line 4,223: | ||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bcd9_mult</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bcd9_mult</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"a*a*a*a is %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">bcd9_to_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"a*a*a*a is %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">bcd9_to_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,232: | Line 4,232: | ||
=== string === |
=== string === |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">mul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">mul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
||
Line 4,261: | Line 4,261: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #000000;">mul</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">mul</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,270: | Line 4,270: | ||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
(same output as immediately above) |
(same output as immediately above) |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- or: |
<span style="color: #004080;">mpz</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"18446744073709551616"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- or: |
||
Line 4,276: | Line 4,276: | ||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
function longMult($a, $b) |
function longMult($a, $b) |
||
{ |
{ |
||
Line 4,347: | Line 4,347: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
<syntaxhighlight lang="picolisp"> |
|||
<lang PicoLisp> |
|||
(de multi (A B) |
(de multi (A B) |
||
(setq A (format A) B (reverse (chop B))) |
(setq A (format A) B (reverse (chop B))) |
||
Line 4,353: | Line 4,353: | ||
(for (I . X) B |
(for (I . X) B |
||
(setq Result (+ Result (* (format X) A (** 10 (dec I)))))) ) ) |
(setq Result (+ Result (* (format X) A (** 10 (dec I)))))) ) ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
< |
<syntaxhighlight lang="pli">/* Multiply a by b, giving c. */ |
||
multiply: procedure (a, b, c); |
multiply: procedure (a, b, c); |
||
declare (a, b, c) (*) fixed decimal (1); |
declare (a, b, c) (*) fixed decimal (1); |
||
Line 4,402: | Line 4,402: | ||
a(i) = s; |
a(i) = s; |
||
end; |
end; |
||
end complement;</ |
end complement;</syntaxhighlight> |
||
Calling sequence: |
Calling sequence: |
||
< |
<syntaxhighlight lang="pli"> a = 0; b = 0; c = 0; |
||
a(60) = 1; |
a(60) = 1; |
||
do i = 1 to 64; /* Generate 2**64 */ |
do i = 1 to 64; /* Generate 2**64 */ |
||
Line 4,414: | Line 4,414: | ||
call multiply (a, b, c); |
call multiply (a, b, c); |
||
put skip; |
put skip; |
||
call output (c);</ |
call output (c);</syntaxhighlight> |
||
Final output: |
Final output: |
||
<pre> |
<pre> |
||
Line 4,423: | Line 4,423: | ||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
Based on the Algol W sample, Uses bytes instead of integers to hold the digits. Ony handles positive numbers. |
Based on the Algol W sample, Uses bytes instead of integers to hold the digits. Ony handles positive numbers. |
||
< |
<syntaxhighlight lang="pli">100H: /* LONG MULTIPLICATION OF LARGE INTEGERS */ |
||
/* LARGE INTEGERS ARE REPRESENTED BY ARRAYS OF BYTES WHOSE VALUES ARE */ |
/* LARGE INTEGERS ARE REPRESENTED BY ARRAYS OF BYTES WHOSE VALUES ARE */ |
||
/* A SINGLE DECIMAL DIGIT OF THE NUMBER */ |
/* A SINGLE DECIMAL DIGIT OF THE NUMBER */ |
||
Line 4,518: | Line 4,518: | ||
CALL PRINT$LONG$INTEGER( .TWO$TO$128 ); |
CALL PRINT$LONG$INTEGER( .TWO$TO$128 ); |
||
CALL PRINT$NL; |
CALL PRINT$NL; |
||
EOF</ |
EOF</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,526: | Line 4,526: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
===Implementation=== |
===Implementation=== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
# LongAddition only supports Unsigned Integers represented as Strings/Character Arrays |
# LongAddition only supports Unsigned Integers represented as Strings/Character Arrays |
||
Function LongAddition ( [Char[]] $lhs, [Char[]] $rhs ) |
Function LongAddition ( [Char[]] $lhs, [Char[]] $rhs ) |
||
Line 4,606: | Line 4,606: | ||
} |
} |
||
LongMultiplication "18446744073709551616" "18446744073709551616"</ |
LongMultiplication "18446744073709551616" "18446744073709551616"</syntaxhighlight> |
||
===Library Method=== |
===Library Method=== |
||
{{works with|PowerShell|4.0}} |
{{works with|PowerShell|4.0}} |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
[BigInt]$n = [Math]::Pow(2,64) |
[BigInt]$n = [Math]::Pow(2,64) |
||
[BigInt]::Multiply($n,$n) |
[BigInt]::Multiply($n,$n) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 4,620: | Line 4,620: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Arbitrary precision arithmetic is native in most Prolog implementations. |
Arbitrary precision arithmetic is native in most Prolog implementations. |
||
< |
<syntaxhighlight lang="prolog"> ?- X is 2**64 * 2**64. |
||
X = 340282366920938463463374607431768211456.</ |
X = 340282366920938463463374607431768211456.</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
===Explicit Implementation=== |
===Explicit Implementation=== |
||
< |
<syntaxhighlight lang="purebasic">Structure decDigitFmt ;decimal digit format |
||
Array Digit.b(0) ;contains each digit of number, right-most digit is index 0 |
Array Digit.b(0) ;contains each digit of number, right-most digit is index 0 |
||
digitCount.i ;zero based |
digitCount.i ;zero based |
||
Line 4,813: | Line 4,813: | ||
Print(#crlf$ + #crlf$ + "Press ENTER to exit"): Input() |
Print(#crlf$ + #crlf$ + "Press ENTER to exit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>The result of 2^64 * 2^64 is 340282366920938463463374607431768211456</pre> |
<pre>The result of 2^64 * 2^64 is 340282366920938463463374607431768211456</pre> |
||
Line 4,821: | Line 4,821: | ||
Using [http://www.purebasic.fr/english/viewtopic.php?p=309763#p309763 Decimal.pbi] by Stargåte allows for calculation with long numbers, this is useful since version 4.41 of PureBasic mostly only supporter data types native to x86/x64/PPC etc processors. |
Using [http://www.purebasic.fr/english/viewtopic.php?p=309763#p309763 Decimal.pbi] by Stargåte allows for calculation with long numbers, this is useful since version 4.41 of PureBasic mostly only supporter data types native to x86/x64/PPC etc processors. |
||
< |
<syntaxhighlight lang="purebasic">XIncludeFile "decimal.pbi" |
||
Define.Decimal *a, *b |
Define.Decimal *a, *b |
||
Line 4,827: | Line 4,827: | ||
*b=TimesDecimal(*a,*a,#NoDecimal) |
*b=TimesDecimal(*a,*a,#NoDecimal) |
||
Print("2^64*2^64 = "+DecimalToString(*b))</ |
Print("2^64*2^64 = "+DecimalToString(*b))</syntaxhighlight> |
||
'''Outputs |
'''Outputs |
||
Line 4,835: | Line 4,835: | ||
(Note that Python comes with arbitrary length integers). |
(Note that Python comes with arbitrary length integers). |
||
< |
<syntaxhighlight lang="python">#!/usr/bin/env python |
||
print 2**64*2**64</ |
print 2**64*2**64</syntaxhighlight> |
||
{{works with|Python|3.0}} |
{{works with|Python|3.0}} |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="python">#!/usr/bin/env python |
||
def add_with_carry(result, addend, addendpos): |
def add_with_carry(result, addend, addendpos): |
||
Line 4,872: | Line 4,872: | ||
onetwentyeight = longhand_multiplication(sixtyfour, sixtyfour) |
onetwentyeight = longhand_multiplication(sixtyfour, sixtyfour) |
||
print(onetwentyeight)</ |
print(onetwentyeight)</syntaxhighlight> |
||
Shorter version: |
Shorter version: |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Long multiplication''' |
||
from functools import reduce |
from functools import reduce |
||
Line 4,919: | Line 4,919: | ||
print( |
print( |
||
longmult(2 ** 64, 2 ** 64) |
longmult(2 ** 64, 2 ** 64) |
||
)</ |
)</syntaxhighlight> |
||
Line 4,930: | Line 4,930: | ||
In addition to the specified task, we were always encouraged to show our workings. |
In addition to the specified task, we were always encouraged to show our workings. |
||
< |
<syntaxhighlight lang="quackery">( ------------- preamble to task, some i/o related words ------------- ) |
||
[ [] swap witheach |
[ [] swap witheach |
||
Line 5,066: | Line 5,066: | ||
cr cr |
cr cr |
||
say "(Show your workings.)" cr cr |
say "(Show your workings.)" cr cr |
||
2 64 ** long dup workings cr</ |
2 64 ** long dup workings cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,107: | Line 5,107: | ||
===Using GMP=== |
===Using GMP=== |
||
{{libheader|gmp}} |
{{libheader|gmp}} |
||
< |
<syntaxhighlight lang="r">library(gmp) |
||
a <- as.bigz("18446744073709551616") |
a <- as.bigz("18446744073709551616") |
||
mul.bigz(a,a)</ |
mul.bigz(a,a)</syntaxhighlight> |
||
"340282366920938463463374607431768211456" |
"340282366920938463463374607431768211456" |
||
===A native implementation=== |
===A native implementation=== |
||
This code is more verbose than necessary, for ease of understanding. |
This code is more verbose than necessary, for ease of understanding. |
||
< |
<syntaxhighlight lang="r">longmult <- function(xstr, ystr) |
||
{ |
{ |
||
#get the number described in each string |
#get the number described in each string |
||
Line 5,178: | Line 5,178: | ||
a <- "18446744073709551616" |
a <- "18446744073709551616" |
||
longmult(a, a)</ |
longmult(a, a)</syntaxhighlight> |
||
<pre> |
<pre> |
||
"340282366920938463463374607431768211456" |
"340282366920938463463374607431768211456" |
||
Line 5,184: | Line 5,184: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
Line 5,221: | Line 5,221: | ||
;; 340282366920938463463374607431768211456 |
;; 340282366920938463463374607431768211456 |
||
;; 340282366920938463463374607431768211456 |
;; 340282366920938463463374607431768211456 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 5,227: | Line 5,227: | ||
{{works with|rakudo|2015-09-17}} |
{{works with|rakudo|2015-09-17}} |
||
For efficiency (and novelty), this program explicitly implements long multiplication, but in base 10000. That base was chosen because multiplying two 5-digit numbers can overflow a 32-bit integer, but two 4-digit numbers cannot. |
For efficiency (and novelty), this program explicitly implements long multiplication, but in base 10000. That base was chosen because multiplying two 5-digit numbers can overflow a 32-bit integer, but two 4-digit numbers cannot. |
||
<lang |
<syntaxhighlight lang="raku" line>sub num_to_groups ( $num ) { $num.flip.comb(/.**1..4/)».flip }; |
||
sub groups_to_num ( @g ) { [~] flat @g.pop, @g.reverse».fmt('%04d') }; |
sub groups_to_num ( @g ) { [~] flat @g.pop, @g.reverse».fmt('%04d') }; |
||
Line 5,249: | Line 5,249: | ||
# cross-check with native implementation |
# cross-check with native implementation |
||
say +$str * +$str;</ |
say +$str * +$str;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,265: | Line 5,265: | ||
Programming note: <big>&&</big> is REXX's '''exclusive or''' operand. |
Programming note: <big>&&</big> is REXX's '''exclusive or''' operand. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program performs long multiplication on two numbers (without the "E"). */ |
||
numeric digits 300 /*be able to handle gihugeic input #s. */ |
numeric digits 300 /*be able to handle gihugeic input #s. */ |
||
parse arg x y . /*obtain optional arguments from the CL*/ |
parse arg x y . /*obtain optional arguments from the CL*/ |
||
Line 5,289: | Line 5,289: | ||
if f<0 then $=copies(0, abs(f) + 1)$ /*Negative? Add leading 0s for INSERT.*/ |
if f<0 then $=copies(0, abs(f) + 1)$ /*Negative? Add leading 0s for INSERT.*/ |
||
say 'long mult:' xx "*" yy '──►' sign || strip( insert(., $, length($) - #), 'T', .) |
say 'long mult:' xx "*" yy '──►' sign || strip( insert(., $, length($) - #), 'T', .) |
||
say ' built─in:' xx "*" yy '──►' xx*yy /*stick a fork in it, we're all done. */</ |
say ' built─in:' xx "*" yy '──►' xx*yy /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 5,307: | Line 5,307: | ||
===version 2=== |
===version 2=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX ************************************************************** |
||
* While REXX can multiply arbitrary large integers |
* While REXX can multiply arbitrary large integers |
||
* here is the algorithm asked for by the task description |
* here is the algorithm asked for by the task description |
||
Line 5,385: | Line 5,385: | ||
ol=ol||value(name'.z') |
ol=ol||value(name'.z') |
||
End |
End |
||
Return ol</ |
Return ol</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>soll = 15129 |
<pre>soll = 15129 |
||
Line 5,402: | Line 5,402: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
{{Incorrect|Ring|Task is "Implement long multiplication" not "Multiply two numbers using native operators"}} |
{{Incorrect|Ring|Task is "Implement long multiplication" not "Multiply two numbers using native operators"}} |
||
< |
<syntaxhighlight lang="ring"> |
||
decimals(0) |
decimals(0) |
||
see pow(2,64)*pow(2,64) + nl |
see pow(2,64)*pow(2,64) + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 5,413: | Line 5,413: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Tcl}} |
{{trans|Tcl}} |
||
< |
<syntaxhighlight lang="ruby">def longmult(x,y) |
||
result = [0] |
result = [0] |
||
j = 0 |
j = 0 |
||
Line 5,435: | Line 5,435: | ||
n=2**64 |
n=2**64 |
||
printf " %d * %d = %d\n", n, n, n*n |
printf " %d * %d = %d\n", n, n, n*n |
||
printf "longmult(%d, %d) = %d\n", n, n, longmult(n,n)</ |
printf "longmult(%d, %d) = %d\n", n, n, longmult(n,n)</syntaxhighlight> |
||
<pre> 18446744073709551616 * 18446744073709551616 = 340282366920938463463374607431768211456 |
<pre> 18446744073709551616 * 18446744073709551616 = 340282366920938463463374607431768211456 |
||
longmult(18446744073709551616, 18446744073709551616) = 340282366920938463463374607431768211456</pre> |
longmult(18446744073709551616, 18446744073709551616) = 340282366920938463463374607431768211456</pre> |
||
Line 5,443: | Line 5,443: | ||
are ever multiplied or added, and all partial results are kept as string. |
are ever multiplied or added, and all partial results are kept as string. |
||
< |
<syntaxhighlight lang="scala">def addNums(x: String, y: String) = { |
||
val padSize = x.length max y.length |
val padSize = x.length max y.length |
||
val paddedX = "0" * (padSize - x.length) + x |
val paddedX = "0" * (padSize - x.length) + x |
||
Line 5,465: | Line 5,465: | ||
def mult(x: String, y: String) = |
def mult(x: String, y: String) = |
||
y.foldLeft("")((acc, digit) => addNums(acc + "0", multByDigit(x, digit.asDigit)))</ |
y.foldLeft("")((acc, digit) => addNums(acc + "0", multByDigit(x, digit.asDigit)))</syntaxhighlight> |
||
Sample: |
Sample: |
||
Line 5,477: | Line 5,477: | ||
Scala 2.8 introduces `scanLeft` and `scanRight` which can be used to simplify this further: |
Scala 2.8 introduces `scanLeft` and `scanRight` which can be used to simplify this further: |
||
< |
<syntaxhighlight lang="scala">def adjustResult(result: IndexedSeq[Int]) = ( |
||
result |
result |
||
.map(_ % 10) // remove carry from each digit |
.map(_ % 10) // remove carry from each digit |
||
Line 5,499: | Line 5,499: | ||
def mult(x: String, y: String) = |
def mult(x: String, y: String) = |
||
y.foldLeft("")((acc, digit) => addNums(acc + "0", multByDigit(x, digit.asDigit))) |
y.foldLeft("")((acc, digit) => addNums(acc + "0", multByDigit(x, digit.asDigit))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
Since Scheme already supports arbitrary precision arithmetic, build it out of church numerals. Don't try converting these to native integers. You will die waiting for the answer. |
Since Scheme already supports arbitrary precision arithmetic, build it out of church numerals. Don't try converting these to native integers. You will die waiting for the answer. |
||
< |
<syntaxhighlight lang="scheme">(define one (lambda (f) (lambda (x) (f x)))) |
||
(define (add a b) (lambda (f) (lambda (x) ((a f) ((b f) x))))) |
(define (add a b) (lambda (f) (lambda (x) ((a f) ((b f) x))))) |
||
(define (mult a b) (lambda (f) (lambda (x) ((a (b f)) x)))) |
(define (mult a b) (lambda (f) (lambda (x) ((a (b f)) x)))) |
||
Line 5,511: | Line 5,511: | ||
(define six (add two (add two two))) |
(define six (add two (add two two))) |
||
(define sixty-four (expo two six)) |
(define sixty-four (expo two six)) |
||
(display (mult (expo two sixty-four) (expo two sixty-four)))</ |
(display (mult (expo two sixty-four) (expo two sixty-four)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<small>(as run on Chicken Scheme on tio)</small> |
<small>(as run on Chicken Scheme on tio)</small> |
||
Line 5,526: | Line 5,526: | ||
[http://seed7.sourceforge.net/libraries/bigint.htm#%28in_bigInteger%29*%28in_bigInteger%29 *]: |
[http://seed7.sourceforge.net/libraries/bigint.htm#%28in_bigInteger%29*%28in_bigInteger%29 *]: |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "bigint.s7i"; |
include "bigint.s7i"; |
||
Line 5,532: | Line 5,532: | ||
begin |
begin |
||
writeln(2_**64 * 2_**64); |
writeln(2_**64 * 2_**64); |
||
end func;</ |
end func;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,546: | Line 5,546: | ||
The multiplication example below uses the requested inferior implementation: |
The multiplication example below uses the requested inferior implementation: |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func string: (in string: a) * (in string: b) is func |
const func string: (in string: a) * (in string: b) is func |
||
Line 5,587: | Line 5,587: | ||
begin |
begin |
||
writeln("-18446744073709551616" * "-18446744073709551616"); |
writeln("-18446744073709551616" * "-18446744073709551616"); |
||
end func;</ |
end func;</syntaxhighlight> |
||
The output is the same as with the superior solution. |
The output is the same as with the superior solution. |
||
Line 5,593: | Line 5,593: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
(Note that arbitrary precision arithmetic is native in Sidef). |
(Note that arbitrary precision arithmetic is native in Sidef). |
||
< |
<syntaxhighlight lang="ruby">say (2**64 * 2**64);</syntaxhighlight> |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="ruby">func add_with_carry(result, addend, addendpos) { |
||
loop { |
loop { |
||
while (result.len < addendpos+1) { |
while (result.len < addendpos+1) { |
||
Line 5,631: | Line 5,631: | ||
} |
} |
||
say longhand_multiplication('18446744073709551616', '18446744073709551616')</ |
say longhand_multiplication('18446744073709551616', '18446744073709551616')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,639: | Line 5,639: | ||
=={{header|Slate}}== |
=={{header|Slate}}== |
||
< |
<syntaxhighlight lang="slate">(2 raisedTo: 64) * (2 raisedTo: 64).</syntaxhighlight> |
||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
Note that arbitrary precision arithmetic is native in Smalltalk, and no-one would reinvent the wheel. |
Note that arbitrary precision arithmetic is native in Smalltalk, and no-one would reinvent the wheel. |
||
< |
<syntaxhighlight lang="smalltalk">(2 raisedTo: 64) * (2 raisedTo: 64).</syntaxhighlight> |
||
or, to display it: |
or, to display it: |
||
< |
<syntaxhighlight lang="smalltalk">Transcript showCR:(2 raisedTo: 64) * (2 raisedTo: 64). |
||
"if ** is defined as alias: " Transcript showCR:(2 ** 64) * (2 ** 64).</ |
"if ** is defined as alias: " Transcript showCR:(2 ** 64) * (2 ** 64).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
Line 5,658: | Line 5,658: | ||
(not that I know of any Smalltalk ever ported to a Zuse 1 :-) |
(not that I know of any Smalltalk ever ported to a Zuse 1 :-) |
||
< |
<syntaxhighlight lang="smalltalk">"/ mhmh hard to avoid largeInteger arithmetic, |
||
"/ as the language does not specify, how many bits are used to represent |
"/ as the language does not specify, how many bits are used to represent |
||
"/ SmallIntegers, and when the VM uses LargeInts. |
"/ SmallIntegers, and when the VM uses LargeInts. |
||
Line 5,795: | Line 5,795: | ||
"/ verify... |
"/ verify... |
||
printedString := String streamContents:[:s | printOn value:rslt value:s]. |
printedString := String streamContents:[:s | printOn value:rslt value:s]. |
||
self assert:(printedString = (2**64) squared printString)</ |
self assert:(printedString = (2**64) squared printString)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
3402823669293846346337467431768211456 |
3402823669293846346337467431768211456 |
||
Line 5,801: | Line 5,801: | ||
The above code does not really integrate into the Smalltalk class library. For example, it will not allow mixed mode arithmetic between regular integers and ''Rosetta integers''. |
The above code does not really integrate into the Smalltalk class library. For example, it will not allow mixed mode arithmetic between regular integers and ''Rosetta integers''. |
||
Here is a full example in portable chunk file format which makes mixed mode arithmetic completely transparent (I implemented only addition and multiplication): |
Here is a full example in portable chunk file format which makes mixed mode arithmetic completely transparent (I implemented only addition and multiplication): |
||
< |
<syntaxhighlight lang="smalltalk">Integer |
||
subclass: #RosettaInteger |
subclass: #RosettaInteger |
||
instanceVariableNames:'digitArray' |
instanceVariableNames:'digitArray' |
||
Line 6,011: | Line 6,011: | ||
Transcript show:'once again: '. |
Transcript show:'once again: '. |
||
result := (2 asRosettaInteger raisedTo:64) squared. |
result := (2 asRosettaInteger raisedTo:64) squared. |
||
Transcript showCR:result.</ |
Transcript showCR:result.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>a is: 124 (RosettaInteger) |
<pre>a is: 124 (RosettaInteger) |
||
Line 6,027: | Line 6,027: | ||
{{works with|Tcl|8.5}} |
{{works with|Tcl|8.5}} |
||
Tcl 8.5 supports arbitrary-precision integers, which improves math operations on large integers. It is easy to define our own by following rules for long multiplication; we can then check this against the built-in's result: |
Tcl 8.5 supports arbitrary-precision integers, which improves math operations on large integers. It is easy to define our own by following rules for long multiplication; we can then check this against the built-in's result: |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc longmult {x y} { |
proc longmult {x y} { |
||
Line 6,054: | Line 6,054: | ||
puts [set n [expr {2**64}]] |
puts [set n [expr {2**64}]] |
||
puts [longmult $n $n] |
puts [longmult $n $n] |
||
puts [expr {$n * $n}]</ |
puts [expr {$n * $n}]</syntaxhighlight> |
||
outputs |
outputs |
||
<pre>18446744073709551616 |
<pre>18446744073709551616 |
||
Line 6,064: | Line 6,064: | ||
In real shell scripts, I would use either `bc` or `dc` for this: |
In real shell scripts, I would use either `bc` or `dc` for this: |
||
< |
<syntaxhighlight lang="sh">multiply() { echo "$1 $2 * p" | dc; }</syntaxhighlight> |
||
But you can also do it with bash's built-in arithmetic: |
But you can also do it with bash's built-in arithmetic: |
||
< |
<syntaxhighlight lang="bash">add() { # arbitrary-precision addition |
||
local a="$1" b="$2" sum= carry=0 |
local a="$1" b="$2" sum= carry=0 |
||
if (( ${#a} < ${#b} )); then |
if (( ${#a} < ${#b} )); then |
||
Line 6,110: | Line 6,110: | ||
done |
done |
||
echo "$product" |
echo "$product" |
||
}</ |
}</syntaxhighlight> |
||
Output is the same either way:<pre>$ multiply 18446744073709551616 18446744073709551616 |
Output is the same either way:<pre>$ multiply 18446744073709551616 18446744073709551616 |
||
Line 6,126: | Line 6,126: | ||
them in decimal. |
them in decimal. |
||
< |
<syntaxhighlight lang="ursala">successor = ~&a^?\1! ~&ah?/~&NfatPRC ~&NNXatPC |
||
sum = ~&B^?a\~&Y@a ~&B?abh/successor@alh2fabt2RC ~&Yabh2Ofabt2RC |
sum = ~&B^?a\~&Y@a ~&B?abh/successor@alh2fabt2RC ~&Yabh2Ofabt2RC |
||
Line 6,136: | Line 6,136: | ||
#show+ |
#show+ |
||
y = %nP product@iiX x</ |
y = %nP product@iiX x</syntaxhighlight> |
||
output: |
output: |
||
<pre>340282366920938463463374607431768211456</pre> |
<pre>340282366920938463463374607431768211456</pre> |
||
Line 6,142: | Line 6,142: | ||
=={{header|Vedit macro language}}== |
=={{header|Vedit macro language}}== |
||
This example multiplies the value on current line with the value on next line and stores result on the 3rd line. |
This example multiplies the value on current line with the value on next line and stores result on the 3rd line. |
||
< |
<syntaxhighlight lang="vedit">BOL |
||
#11 = EOL_Pos-Cur_Pos |
#11 = EOL_Pos-Cur_Pos |
||
#12 = EOL_Pos-1 |
#12 = EOL_Pos-1 |
||
Line 6,166: | Line 6,166: | ||
} |
} |
||
} |
} |
||
} </ |
} </syntaxhighlight> |
||
Sample input and output: |
Sample input and output: |
||
<pre> |
<pre> |
||
Line 6,177: | Line 6,177: | ||
{{trans|C#}}<br/> |
{{trans|C#}}<br/> |
||
This uses the '''decimal''' type, (which has a '''MaxValue''' of 79,228,162,514,264,337,593,543,950,335). By limiting it to '''10^28''', it allows 28 decimal digits for the ''hi'' part, and 28 decimal digits for the ''lo'' part, '''56 decimal digits''' total. A side computation of ''BigInteger'' assures that the results are accurate. |
This uses the '''decimal''' type, (which has a '''MaxValue''' of 79,228,162,514,264,337,593,543,950,335). By limiting it to '''10^28''', it allows 28 decimal digits for the ''hi'' part, and 28 decimal digits for the ''lo'' part, '''56 decimal digits''' total. A side computation of ''BigInteger'' assures that the results are accurate. |
||
< |
<syntaxhighlight lang="vbnet">Imports System |
||
Imports System.Console |
Imports System.Console |
||
Imports BI = System.Numerics.BigInteger |
Imports BI = System.Numerics.BigInteger |
||
Line 6,223: | Line 6,223: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}}Shown are the prescribed output and the maximum power of two that can be squared by this '''''bd''''' structure without overflowing. |
{{out}}Shown are the prescribed output and the maximum power of two that can be squared by this '''''bd''''' structure without overflowing. |
||
<pre>The square of (2^64): 18,446,744,073,709,551,616 |
<pre>The square of (2^64): 18,446,744,073,709,551,616 |
||
Line 6,234: | Line 6,234: | ||
{{trans|Go}} |
{{trans|Go}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
// argument validation |
// argument validation |
||
Line 6,297: | Line 6,297: | ||
var n = "18446744073709551616" |
var n = "18446744073709551616" |
||
Fmt.print("$,s", mul.call(n, n))</ |
Fmt.print("$,s", mul.call(n, n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,305: | Line 6,305: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">include c:\cxpl\stdlib; |
||
char Two64, Product(40); |
char Two64, Product(40); |
||
[Two64:= "18446744073709551616"; |
[Two64:= "18446744073709551616"; |
||
Line 6,311: | Line 6,311: | ||
Product(39):= Product(39)!$80; \terminate string |
Product(39):= Product(39)!$80; \terminate string |
||
Text(0, Product+1); \skip leading zero |
Text(0, Product+1); \skip leading zero |
||
]</ |
]</syntaxhighlight> |
||
Output: |
Output: |
||
Line 6,320: | Line 6,320: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
[gnu] BigNums are supported via an extension library |
[gnu] BigNums are supported via an extension library |
||
< |
<syntaxhighlight lang="zkl">var BN=Import("zklBigNum"); |
||
BN(2).pow(64) * BN(2).pow(64) |
BN(2).pow(64) * BN(2).pow(64) |
||
340282366920938463463374607431768211456 |
340282366920938463463374607431768211456 |
||
Line 6,329: | Line 6,329: | ||
//42!, also BN(42).factorial() |
//42!, also BN(42).factorial() |
||
[2..42].reduce(fcn(p,n){p*n},BN(1)) : "%,d".fmt(_) |
[2..42].reduce(fcn(p,n){p*n},BN(1)) : "%,d".fmt(_) |
||
1,405,006,117,752,879,898,543,142,606,244,511,569,936,384,000,000,000</ |
1,405,006,117,752,879,898,543,142,606,244,511,569,936,384,000,000,000</syntaxhighlight> |
||
{{omit from|Erlang|Erlang has this built in}} |
{{omit from|Erlang|Erlang has this built in}} |