Long multiplication: Difference between revisions
add RPL
(→{{header|ALGOL 60}}: Maybe this is easier for people unfamiliar with the language to understand.) |
(add RPL) |
||
Line 6,183:
</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}}==
{{trans|Tcl}}
| |||