Long multiplication: Difference between revisions

Content added Content deleted
(add RPL)
Line 6,184: Line 6,184:


=={{header|RPL}}==
=={{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.
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" →"xyz" ) ''
<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 →"0..0xyz" ) ''
<span style="color:blue">ZeroFill</span> ''( "xyz" n → "0..0xyz" ) ''
<span style="color:blue">Swap→Zero</span> ''( a b →a b Δlength ) ''
<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" →"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 →"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" →"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}}