Long multiplication: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 60}}: Maybe this is easier for people unfamiliar with the language to understand.) |
(add RPL) |
||
Line 6,183: | Line 6,183: | ||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
To solve the task, we need to develop part of a BigInt library which to handle very long integers as strings. Addition has been optimized with a 10-digit batch size, but multiplication is long (and slow), as required. |
|||
{| class="wikitable" |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ → a |
|||
≪ 1 '''WHILE''' a OVER DUP SUB "0" == '''REPEAT''' 1 + '''END''' |
|||
a SWAP OVER SIZE SUB |
|||
≫ ≫ ‘<span style="color:blue">NoZero’</span> STO |
|||
≪ '''WHILE''' DUP '''REPEAT''' "0" ROT + SWAP 1 - '''END''' DROP |
|||
≫ ‘<span style="color:blue">ZeroFill</span>' STO |
|||
≪ DUP2 SIZE SWAP SIZE → sb sa |
|||
≪ '''IF''' sa sb < '''THEN''' SWAP '''END''' |
|||
sa sb - ABS |
|||
≫ ≫ '<span style="color:blue">Swap→Zero</span>' STO |
|||
≪ <span style="color:blue">Swap→Zero ZeroFill</span> → a b |
|||
≪ "" 1 CF |
|||
a SIZE 1 '''FOR''' j |
|||
1 FS?C |
|||
a j 9 - j SUB STR→ + b j 9 - j SUB STR→ + |
|||
'''IF''' DUP 1E10 ≥ '''THEN''' 1E10 - 1 SF '''END''' |
|||
→STR 10 OVER SIZE - <span style="color:blue">ZeroFill</span> SWAP + |
|||
-10 '''STEP''' |
|||
1 FS? →STR SWAP + <span style="color:blue">NoZero </span> |
|||
≫ ≫ ‘<span style="color:blue">ADDbig</span>’ STO |
|||
≪ → a d |
|||
≪ "" 0 |
|||
a SIZE 1 '''FOR''' j |
|||
a j DUP SUB STR→ d * + |
|||
10 MOD LAST / IP |
|||
SWAP →STR ROT + SWAP |
|||
-1 '''STEP''' |
|||
'''IF THEN''' LAST →STR SWAP + '''END''' |
|||
≫ ≫ ‘<span style="color:blue">DigitMul</span>’ STO |
|||
≪ <span style="color:blue">Swap→Zero</span> DROP → a b |
|||
≪ "0" b SIZE 1 '''FOR''' j |
|||
a b j DUP SUB STR→ <span style="color:blue">DigitMul</span> |
|||
"" b SIZE j - <span style="color:blue">ZeroFill</span> + <span style="color:blue">ADDbig</span> |
|||
-1 '''STEP''' |
|||
≫ ≫ ‘<span style="color:blue">MULbig’ STO |
|||
| |
|||
<span style="color:blue">NoZero</span> ''( "0..0xyz" →"xyz" ) '' |
|||
count leading zeros |
|||
keep the rest |
|||
<span style="color:blue">ZeroFill</span> ''( "xyz" n →"0..0xyz" ) '' |
|||
<span style="color:blue">Swap→Zero</span> ''( a b →a b Δlength ) '' |
|||
swap a and b if length(a) < length(b) |
|||
return length difference |
|||
<span style="color:blue">ADDbig</span> ''( "a" "b" →"a+b" ) '' |
|||
res = "" ; carry = 0 |
|||
for j = length(a) downto 1 step 10 |
|||
digits = carry |
|||
digits += a[j-9..j] + b[j-9..j] |
|||
if b > 1E10 then digits -= 1E10 ; carry = 1 |
|||
convert digits to 10-char string with leading zeros |
|||
next |
|||
prepend carry and remove leading zeros |
|||
<span style="color:blue">DigitMul</span> ''( "a" d →"a*d" ) '' |
|||
res = "" ; carry = 0 |
|||
for j = length(a) downto 1 |
|||
digit = a[j]*d |
|||
carry = digit // 10 |
|||
digit %= 10 |
|||
next |
|||
prepend carry |
|||
<span style="color:blue">MULbig</span> ''( "a" "b" →"a*b" ) '' |
|||
sum = "0" ; for j = length(b) downto 1 |
|||
tmp = a * b[j] |
|||
shift left tmp length(b)-j times, then add to sum |
|||
next |
|||
|} |
|||
"18446744073709551616" DUP <span style="color:blue">MULbig</span> |
|||
{{out}} |
|||
<pre> |
|||
1: "340282366920938463463374607431768211456" |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Tcl}} |
{{trans|Tcl}} |