Long multiplication: Difference between revisions
(added J) |
|||
Line 142: | Line 142: | ||
onetwentyeight = longhand_multiplication(sixtyfour, sixtyfour) |
onetwentyeight = longhand_multiplication(sixtyfour, sixtyfour) |
||
print(onetwentyeight)</lang> |
print(onetwentyeight)</lang> |
||
Shorter version: |
|||
{{trans|Haskell}} |
|||
<lang python>#!/usr/bin/env python |
|||
def digits(x): |
|||
return [int(c) for c in str(x)] |
|||
def mult_table(xs, ys): |
|||
return [[x * y for x in xs] for y in ys] |
|||
def polymul(xs, ys): |
|||
return map(lambda *vs: sum(filter(None, vs)), |
|||
*[[0] * i + zs for i, zs in enumerate(mult_table(xs, ys))]) |
|||
def longmult(x, y): |
|||
result = 0 |
|||
for v in polymul(digits(x), digits(y)): |
|||
result = result * 10 + v |
|||
return result |
|||
if __name__ == "__main__": |
|||
print longmult(2**64, 2**64)</lang> |
Revision as of 02:55, 26 February 2009
You are encouraged to solve this task according to the task description, using any language you may know.
In this task, explicitly implement long multiplication. This is one possible approach to arbitrary-precision integer algebra.
For output, display the result of 2^64 * 2^64. The decimal representation of 2^64 is:
18446744073709551616
The output of 2^64 * 2^64 is 2^128, and that is:
340282366920938463463374607431768211456
Haskell
<lang haskell>digits :: Integer -> [Integer] digits = map (fromIntegral.digitToInt) . show
lZZ = inits $ repeat 0
table f = map . flip (map . f)
polymul = ((map sum . transpose . zipWith (++) lZZ) .) . table (*)
longmult = (foldl1 ((+) . (10 *)) .) . (. digits) . polymul . digits</lang> Output: <lang haskell>*Main> (2^64) `longmult` (2^64) 340282366920938463463374607431768211456</lang>
J
(([+10x*])/@|.@(,.&.":@[+//.@(*/),.&.":@]))/ ,~2x^64 340282366920938463463374607431768211456
- digits: ,.&.": y
,.&.": 123 1 2 3
- polynomial multiplication: x (+//.@(*/)) y ref. [1]
1 2 3 (+//.@(*/)) 1 2 3 1 4 10 12 9
- building the decimal result: ([+10x*])/|. y
([+10x*])/|. 1 4 10 12 9 15129
or using the primitive dyad #. instead of ([+10x*])/@|.
(10x #.,.&.":@[+//.@(*/),.&.":@])/ ,~2x^64 340282366920938463463374607431768211456
Perl
<lang perl>#!/usr/bin/perl -w use strict;
- This should probably be done in a loop rather than be recursive.
sub add_with_carry {
my $resultref = shift; my $addend = shift; my $addendpos = shift;
push @$resultref, (0) while (scalar @$resultref < $addendpos + 1); my $addend_result = $addend + $resultref->[$addendpos]; my @addend_digits = reverse split //, $addend_result; $resultref->[$addendpos] = shift @addend_digits;
my $carry_digit = shift @addend_digits; &add_with_carry($resultref, $carry_digit, $addendpos + 1) if( defined $carry_digit )
}
sub longhand_multiplication {
my @multiplicand = reverse split //, shift; my @multiplier = reverse split //, shift; my @result = (); my $multiplicand_offset = 0; foreach my $multiplicand_digit (@multiplicand) { my $multiplier_offset = $multiplicand_offset; foreach my $multiplier_digit (@multiplier) { my $multiplication_result = $multiplicand_digit * $multiplier_digit; my @result_digit_addend_list = reverse split //, $multiplication_result;
my $addend_offset = $multiplier_offset; foreach my $result_digit_addend (@result_digit_addend_list) { &add_with_carry(\@result, $result_digit_addend, $addend_offset++) }
++$multiplier_offset; }
++$multiplicand_offset; }
@result = reverse @result;
return join , @result;
}
my $sixtyfour = "18446744073709551616";
my $onetwentyeight = &longhand_multiplication($sixtyfour, $sixtyfour); print "$onetwentyeight\n";</lang>
Python
<lang python>#!/usr/bin/env python
def add_with_carry(result, addend, addendpos):
while True: while len(result) < addendpos + 1: result.append(0) addend_result = str(int(addend) + int(result[addendpos])) addend_digits = list(addend_result) result[addendpos] = addend_digits.pop()
if not addend_digits: break addend = addend_digits.pop() addendpos += 1
def longhand_multiplication(multiplicand, multiplier):
result = [] for multiplicand_offset, multiplicand_digit in enumerate(reversed(multiplicand)): for multiplier_offset, multiplier_digit in enumerate(reversed(multiplier), start=multiplicand_offset): multiplication_result = str(int(multiplicand_digit) * int(multiplier_digit))
for addend_offset, result_digit_addend in enumerate(reversed(multiplication_result), start=multiplier_offset): add_with_carry(result, result_digit_addend, addend_offset)
result.reverse()
return .join(result)
if __name__ == "__main__":
sixtyfour = "18446744073709551616"
onetwentyeight = longhand_multiplication(sixtyfour, sixtyfour) print(onetwentyeight)</lang>
Shorter version:
<lang python>#!/usr/bin/env python
def digits(x):
return [int(c) for c in str(x)]
def mult_table(xs, ys):
return [[x * y for x in xs] for y in ys]
def polymul(xs, ys):
return map(lambda *vs: sum(filter(None, vs)), *[[0] * i + zs for i, zs in enumerate(mult_table(xs, ys))])
def longmult(x, y):
result = 0 for v in polymul(digits(x), digits(y)): result = result * 10 + v return result
if __name__ == "__main__":
print longmult(2**64, 2**64)</lang>