diff options
| -rw-r--r-- | challenge-090/jcrosswh/perl/ch-2.pl | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/challenge-090/jcrosswh/perl/ch-2.pl b/challenge-090/jcrosswh/perl/ch-2.pl new file mode 100644 index 0000000000..5ef3fe77ee --- /dev/null +++ b/challenge-090/jcrosswh/perl/ch-2.pl @@ -0,0 +1,147 @@ +#!/usr/bin/env perl + +use strict; +use warnings; + +=head1 NAME + +PWC 090 Challenge 2 + +=head1 SYNOPSIS + + $ ch-2.pl 25 7 + The initial twos table looks like: + 2^0 = 1 + 2^1 = 2 + 2^2 = 4 + 2^3 = 8 + 2^4 = 16 + 2^5 = 32 + + Decomposition looks like: + 25-16 = 9 + 9-8 = 1 + 1-1 = 0 + + The table of the second multiplicand times powers of 2 (* values will be used): + * 1 7 + 2 14 + 4 28 + * 8 56 + * 16 112 + 32 224 + + The solution using Ethiopian Multiplication looks like: + 112+56+7=175 + +=head1 DESCRIPTION + +Given two positive numbers, this script will demonstrate Ethiopian +Multiplication using the given numbers. + +=head1 AUTHORS + +Joel Crosswhite E<lt>joel.crosswhite@ix.netcom.comE<gt> + +=cut + +my ($first_input, $second_input) = validate_inputs(); + +my @twos_table = build_twos_table($first_input); +print_twos_table(\@twos_table); + +my @decomposition_places = + build_decomposition_table($first_input, \@twos_table); +print_decomposition_table($first_input, \@twos_table, \@decomposition_places); + +my @second_twos_table = ($second_input); +map { push(@second_twos_table, $second_twos_table[-1] * 2) } + (2..scalar(@twos_table)); +print_second_twos_table(\@second_twos_table, \@decomposition_places); + +print_solution(\@decomposition_places, \@second_twos_table); + +exit 0; + +sub validate_inputs { + my $first_input = $ARGV[0]; + my $second_input = $ARGV[1]; + if ((!defined($first_input) || $first_input !~ m/^[1-9]\d*$/) + || (!defined($second_input) || $second_input !~ m/^[1-9]\d*$/)) { + print "Usage: ch-2.pl <positive integer> <positive integer>\n"; + exit 1; + } + + if ($first_input < $second_input) { + my $tmp = $first_input; + $first_input = $second_input; + $second_input = $tmp; + } + + return ($first_input, $second_input); +} + +sub build_twos_table { + my ($first_input) = @_; + my @table = (1); + while ($first_input > $table[-1]) { + push(@table, 2 * $table[-1]); + } + splice(@table, -1); + return @table; +} + +sub print_twos_table { + my ($twos_table) = @_; + print "The initial twos table looks like:\n"; + for (my $i = 0; $i < scalar(@{$twos_table}); $i++) { + printf("2^%d = %d\n", $i, $twos_table->[$i]); + } + print "\n"; +} + +sub build_decomposition_table{ + my ($first_input, $twos_table) = @_; + my @table; + for (my $i = scalar(@{$twos_table}) - 1; $i >= 0; $i--) { + next if $first_input < $twos_table->[$i]; + push(@table, $i); + $first_input -= $twos_table->[$i]; + } + return @table; +} + +sub print_decomposition_table{ + my ($first_input, $twos_table, $decomposition_places) = @_; + print "Decomposition looks like:\n"; + foreach my $value (@{$decomposition_places}) { + printf("%d-%d = %d\n", $first_input, $twos_table->[$value], + ($first_input - $twos_table->[$value])); + $first_input -= $twos_table->[$value]; + } + print "\n"; +} + +sub print_second_twos_table{ + my ($second_table, $decomposition_places) = @_; + print "The table of the second multiplicand times powers of 2 (* values " + . "will be used):\n"; + for (my $i = 0; $i < scalar(@{$second_table}); $i++) { + print '* ' if (grep( /^$i/, @{$decomposition_places})); + printf("%d %d\n", 2 ** $i, $second_table->[$i]); + } + print "\n"; +} + +sub print_solution{ + my ($decomposition_places, $twos_table) = @_; + print "The solution using Ethiopian Multiplication looks like:\n"; + my $solution; + my $output = ''; + foreach my $index (@{$decomposition_places}) { + $output = sprintf($output . '%d+', $twos_table->[$index]); + $solution += $twos_table->[$index]; + } + chop($output); + print $output . '=' . $solution . "\n"; +} |