Long multiplication: Difference between revisions
Content added Content deleted
(add RPL) |
m (→{{header|RPL}}: typos) |
||
Line 6,184: | Line 6,184: | ||
=={{header|RPL}}== |
=={{header|RPL}}== |
||
To solve the task, we need to develop part of a BigInt library |
To solve the task, we need to develop part of a BigInt library 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" |
{| class="wikitable" |
||
! RPL code |
! RPL code |
||
Line 6,231: | Line 6,231: | ||
≫ ≫ ‘<span style="color:blue">MULbig’ STO |
≫ ≫ ‘<span style="color:blue">MULbig’ STO |
||
| |
| |
||
<span style="color:blue">NoZero</span> ''( "0..0xyz" |
<span style="color:blue">NoZero</span> ''( "0..0xyz" → "xyz" ) '' |
||
count leading zeros |
count leading zeros |
||
keep the rest |
keep the rest |
||
<span style="color:blue">ZeroFill</span> ''( "xyz" n |
<span style="color:blue">ZeroFill</span> ''( "xyz" n → "0..0xyz" ) '' |
||
<span style="color:blue">Swap→Zero</span> ''( a b |
<span style="color:blue">Swap→Zero</span> ''( a b → a b Δlength ) '' |
||
swap a and b if length(a) < length(b) |
swap a and b if length(a) < length(b) |
||
return length difference |
return length difference |
||
<span style="color:blue">ADDbig</span> ''( "a" "b" |
<span style="color:blue">ADDbig</span> ''( "a" "b" → "a+b" ) '' |
||
res = "" ; carry = 0 |
res = "" ; carry = 0 |
||
for j = length(a) downto 1 step 10 |
for j = length(a) downto 1 step 10 |
||
Line 6,251: | Line 6,251: | ||
if b > 1E10 then digits -= 1E10 ; carry = 1 |
if b > 1E10 then digits -= 1E10 ; carry = 1 |
||
convert digits to 10-char string with leading zeros |
convert digits to 10-char string with leading zeros |
||
next |
next j |
||
prepend carry and remove leading zeros |
prepend carry and remove leading zeros |
||
<span style="color:blue">DigitMul</span> ''( "a" d |
<span style="color:blue">DigitMul</span> ''( "a" d → "a*d" ) '' |
||
res = "" ; carry = 0 |
res = "" ; carry = 0 |
||
for j = length(a) downto 1 |
for j = length(a) downto 1 |
||
Line 6,261: | Line 6,261: | ||
carry = digit // 10 |
carry = digit // 10 |
||
digit %= 10 |
digit %= 10 |
||
next |
next j |
||
prepend carry |
prepend carry |
||
<span style="color:blue">MULbig</span> ''( "a" "b" |
<span style="color:blue">MULbig</span> ''( "a" "b" → "a*b" ) '' |
||
sum = "0" ; for j = length(b) downto 1 |
sum = "0" ; for j = length(b) downto 1 |
||
tmp = a * b[j] |
tmp = a * b[j] |
||
shift left tmp length(b)-j times, then add to sum |
shift left tmp length(b)-j times, then add to sum |
||
next |
next j |
||
|} |
|} |
||
Line 6,277: | Line 6,277: | ||
1: "340282366920938463463374607431768211456" |
1: "340282366920938463463374607431768211456" |
||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Tcl}} |
{{trans|Tcl}} |