Wherein we force fancy machinery to embrace its primitive roots, discovering along the way that silicon is just another part of the rocks around us and how hidden powers lurk beneath the mathematical surface of the world...
THE WEEKLY CHALLENGE – PERL & RAKU #66
TASK #1 › Divide Integers
Submitted by: Mohammad S Anwar
You are given two integers $M and $N.
Write a script to divide the given two integers i.e. $M / $N without using multiplication, division and mod operator and return the floor of the result of the division.
Example 1:
Input: $M = 5, $N = 2
Output: 2
Example 2:
Input: $M = -5, $N = 2
Output: -3
Example 3:
Input: $M = -5, $N = -2
Output: 2
Method
A fairly common technique employed by artists and creatives is artificially constraining your toolset; to mix things up by removing a color from your comfortable palette, or perhaps put your brushes away completely and use your hands or something. Or write an entire novel without using the letter ‘e’. Given the tools you have, you learn to make do, which makes you do things you wouldn’t normally do, which makes you try new things and, hopefully, learn something you can use later.
That said, it may not be exactly clear why one would ever wish to do division without using any of the higher level operators made just to do that. Well, it’s worth noting that at a binary level, division is pretty much implemented within the machine by subtraction, which, being binary, is greatly simplified and looks a lot like textbook long division. Simulating this would make for a very interesting way to solve this problem. But we’re not going to do that.
The first time I worked out the logic for this challenge I did it for positive numbers, by subtracting out the denominator, keeping track of the iterations as the quotient. This is bog standard integer division, and pretty straightforward stuff. So far so good. Then, when adapting the method to include negative numbers, things got a little complicated: I noticed that I had misread the problem. You see, we aren’t in fact being asked to do division, or even integer division. What we are a being asked to do is create is a floor function for integer division, which is a little different.
The floor looks to find the largest integer such that floor(x) + {x} = x, where 0 ≤ {x} ≤ 1 and represents the fractional component of a real number. This is an important distinction from simple integer division as shown in example 2 above, as
floor(-5/2) = -3
not -2, being the integer part of -2.5, the real solution.
The easiest way to deal with negative input would be to adapt the method for individual cases. After all, there are only four. But it was more interesting to draw out the underlying logic for the various cases and adjust for the signs when they appear. We aren’t explicitly denied use of the abs() function, but on the face of it it it looks a lot like selectively multiplying by -1. In the spirit of the challenge I made my own, returning the absolute value by subtracting from 0 when the number is negative and in addition returning a flag set to 1 notifying us that it has done something. By applying our home-brew absolute() function to both inputs, we can use our subtractive method as outlined above for the integer division for positive numbers, and collect the flags to decide what to do with the result.
As it works out, integer division works fine as the floor for two positive numbers, or two negative, which yields a positive value. When we collect the sum of the flags from the absolute() function, these cases are signified by values of 0 or 2. Only when the sum adds to 1 do we need to reverse the sign of the result, with the complications that brings.
You see, the following equality hold true:
- ⎣x⎦ = ⎡-x⎤Which is to say when we reverse the sign on the floor of a function, we get the ceiling of the negative of the value. We can reverse the sign by subtracting from 0, but still have the ceiling rather than the floor. The ceiling is the smallest integer greater than a real number x.
Conversion is a little complicated, but not too bad. To convert between the two, we need to reference the equality:
⎡x⎤ - ⎣x⎦ = ⎧ 0 : x ∈ ℤ
⎩ 1 : x ∉ ℤwhich means we cannot simply subtract 1 from the result, but first must make sure the floor does not equal the ceiling, as is the case when the value is an integer. We can determine this by looking at the remainder of our subtracting out process; if it is 0, we have divided evenly and and the real quotient is an integer.
And that is how, using only the simplest of tools, we bring division to the floor.
Perl Solution
[colincrain:~/PWC]$ perl 66_1_sewing_division.pl -5 2
floor -5 ÷ 2 = -3use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my ($n, $d) = @ARGV;
my $qf = divide_to_floor( $n, $d );
printf "floor %d ÷ %d = %d\n", $n, $d, $qf;
## ## ## ## ## SUBS:
sub absolute {
## return array: (absolute value of $num, bool is negative)
my $num = shift;
if ($num < 0) {
return ((0 - $num), 1)
}
return ($num, 0)
}
sub divide_to_floor {
## integer division floor function
my ($numerator, $denominator) = @_;
my $remainder;
my $quotient_floor = 0;
my $sign_negative = 0;
my $negate = 0;
($remainder, $sign_negative) = absolute($numerator);
$negate += $sign_negative;
($denominator, $sign_negative ) = absolute($denominator);
$negate += $sign_negative;
## do integer division on two positive values
while ($remainder - $denominator >= 0) {
$remainder = $remainder - $denominator;
$quotient_floor++;
}
## convert to floor for negative results
## negate can only be 0, 1 or 2, so we have only one negative
if ($negate == 1) {
## the negative of the floor of x i the ceiling of -x
## - ⎣x⎦ = ⎡-x⎤
## so subtract 1 unless ⎣x⎦ = ⎡x⎤, which is when {x} = 0
## or in other words when the remainder is 0
$quotient_floor = 0 - $quotient_floor;
$quotient_floor-- if $remainder != 0;
}
return $quotient_floor;
}Raku Solution
I can’t decide whether this exercise in simple coding is more or less ridiculous in the thoroughly 21st century language that is Raku. As it is by definition simple, the code is largely unchanged. However the divide-by-zero error is more easily avoided in the signature, and the logic behind the negation is simplified by having a single boolean value passed into the absolute() function and changed in-place as required.
sub MAIN (Int $numerator, Int $denominator where { $denominator != 0 }) {
my $quotient_floor = divide_to_floor( $numerator, $denominator );
"floor $numerator ÷ $denominator = $quotient_floor".say;
}
sub absolute (Int $num, Bool $negate is rw) {
## Int -> (Int absolute value of $num, Int is negative)
return $num if $num >= 0;
$negate = ! $negate;
0 - $num;
}
sub divide_to_floor (Int $numerator, Int $denominator is copy) {
## integer division floor function
my $remainder;
my $quotient_floor = 0;
my $negate = False;
$remainder = absolute($numerator, $negate);
$denominator = absolute($denominator, $negate);
## do integer division on two positive values
while ($remainder - $denominator >= 0) {
$remainder -= $denominator;
$quotient_floor++;
}
## convert to floor for negative results
if $negate {
## the negative of the floor of x i the ceiling of -x
## - ⎣x⎦ = ⎡-x⎤
## so subtract 1 unless ⎣x⎦ = ⎡x⎤, which is when {x} = 0
## or in other words when the remainder is 0
$quotient_floor = 0 - $quotient_floor;
$quotient_floor-- if $remainder != 0;
}
return $quotient_floor;
}
TASK #2 › Power Integers
Submitted by: Mohammad S Anwar
You are given an integer $N.
Write a script to check if the given number can be expressed as mn where m and n are positive integers. Otherwise print 0.
Please make sure m > 1 and n > 1.
BONUS: If there are more than one ways to express the given number then print all possible solutions.
Example 1:
For given $N = 9, it should print 32 or 3^2.
Example 2:
For given $N = 45, it should print 0.
Example 3:
For given $N = 64, it should print all or one of 8^2 or 2^6 or 4^3.
Method
This challenge deals with numbers that multiply solely amongst themselves to make new, larger numbers, so obviously, working backwards from the end product, any solution to this puzzle will involve factoring. It’s important to note that for the problem as stated, the number raised to the power need not be prime, but if it is not, that number will in turn be able to be factored into components that are themselves prime. So essentially we can conclude that the problem will involve prime factoring, those atomic units at the multiplicative base. This is good, because we know how to do that.
So we go ahead and reduce a number to its prime factors; now what qualities of that set shows it to be conducive to rearranging into the form nm? Rather than the bog-standard exercise in factoring that we’ve done here before, I think this speaks to the fundamental question at the root of the challenge. Let’s have a look.
Well for one, in order to be a component of an expression mn = m * m … * m = N, any factor f of m must be present in every occurrence of m in the expression, which is at least two, which means there must be more than one. This brings us to our first observation:
- For a set of factors f1, f2, f3 … = N , each with count c associated with it, any set containing a factor with count 1 is excluded.
Very good. Now we’re getting somewhere.
- The second observation is that in such a breakdown as outlined above, the power to be raised to is determined by the factor with the smallest count.
For example, for the set of prime factors {2, 2, 3, 3, 3, 3} for the number 324, we have (2) x 2s and (4) x 3s. As such the exponent will be the smaller, or 2.
- The third observation is that in order for the factors to be written in the form mn, the count of each of the remaining factors must be a multiple of the power.
The factors for 108 are {2, 2, 3, 3, 3}. We have (2) x 2s and (3) x 3s. The count of the 3s is not a multiple of the count of the 2s, and so the number cannot be expressed as a single base raised to a power. This can easily found to be correct, as there is no way to divide that particular set of factors into two equal groups.
- Finally, the base for the power is determined by the the product of the factors times their count divided by the power.
In the first example above, for 324, the power is 2. The starting counts are divided by the power, which results in new counts of (1) x 2 and (2) x 3s. Multiplying this out we get 2 * 3 * 3 = 18. So the base is 18, the exponent 2, and the final expression is 182 = 324, which, as it is, holds true. How nice.
So the method is:
- Determine the prime factors of the number
- Group the factors by value, keeping count of their incidence
- The smallest incidence is the power that can be factored out. We only care if this is greater than 1.
- If we have a power greater than 1, divide out the other incidences. If any or those divisions don’t come out even, we cannot continue.
- The base becomes the product of the individual factors raised to the power of their divided-out incidences.
Perl Solution
[colincrain:~/PWC]$ perl 66_2_embrace_the_power.pl 2401
2401 = 7^4use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my $input = shift @ARGV;
my $maxprime = int( sqrt($input) );
my @primes = make_prime_list($maxprime);
my %decomp;
%decomp = map { $_, ++$decomp{$_} } decompose($input, \@primes);
my ($power, $base_factors) = get_powers( \%decomp );
if (defined $base_factors) {
my $base = 1;
for (keys $base_factors->%*) {
$base *= $_ ** $base_factors->{$_};
}
say "$input = $base^$power";
}
else {
say 0;
}
## ## ## ## ## SUBS:
sub get_powers {
## divides a det of factors into a power and a collection of factors,
## or returns undef if impossible
my %decomp = $_[0]->%*;
my @factors = sort { $decomp{$a} <=> $decomp{$b}
|| $a <=> $b
} keys %decomp ;
return unless @factors;
my $power = $decomp{$factors[0]};
return if $power == 1;
my %base_factors = map { $decomp{$_} % $power == 0 ? ($_, $decomp{$_} / $power)
: return
} @factors;
return ($power, \%base_factors);
}
sub decompose {
## given a number and a list of primes less than n/2,
## returns an array list of prime decomposition factors of the number
my ($num, $primes) = @_;
my @decomp;
my @primelist = $primes->@*;
my $prime = shift @primelist;
while ( $prime <= $num ) {
while ($num % $prime == 0) {
$num = $num / $prime;
push @decomp, $prime;
}
last if scalar @primelist == 0;
$prime = shift @primelist;
}
return @decomp;
}
sub make_prime_list {
## creates a list of all primes less than or equal to a given number
my $max = shift;
my @output = (2);
CANDIDATE: for( my $candidate = 3; $candidate <= $max; $candidate += 2 ) {
my $sqrt_candidate = sqrt( $candidate );
for( my $test = 3; $test <= $sqrt_candidate; $test += 2 ) {
next CANDIDATE if $candidate % $test == 0;
}
push @output, $candidate;
}
return @output;
}Raku Solution
The Raku we can do away with the need for the list of powers to check for factoring, as we are able to make that on the fly with
my @primelist = (2..(sqrt($num)).Int).grep({ .is-prime });The computation of the base is also streamlined with the use of the product metaoperator:
my $base = [*] %base_factors.keys.map: { $_ ** %base_factors{$_} }In other respects the logic is fundamentally the same. Nice to get rid of that subroutine, though.
sub MAIN ( Int $input = 324 ) {
my %decomp = decompose($input).map: { $_ => ++%decomp{$_} };
my ($power, %base_factors) = get_powers( %decomp );
if %base_factors.keys > 0 {
my $base = [*] %base_factors.keys.map: { $_ ** %base_factors{$_} }
say "$input = $base^$power";
}
else {
say 0;
}
}
sub decompose ( $num is copy ) {
## given a number
## returns an array list of prime decomposition factors of the number
my @decomp;
my @primelist = (2..(sqrt($num)).Int).grep({ .is-prime });
my $prime = shift @primelist;
while ( $prime <= $num ) {
while ($num %% $prime) {
$num /= $prime;
@decomp.push: $prime;
}
last unless @primelist.elems;
$prime = @primelist.shift;
}
return @decomp;
}
sub get_powers ( %decomp ) {
## divides a hash of factors and their incidences into a power and hash with new incidences
## or returns Nil if impossible
my @factors = %decomp.keys.sort: { %decomp{$^a} <=> %decomp{$^b}
|| $^a <=> $^b };
return if @factors.elems == 0; ## single factors for prime numbers aren't recorded,
## but we don't care
my $power = %decomp{@factors.head};
return if $power == 1;
my %base_factors = @factors.map: { %decomp{$_} %% $power ?? ($_ => %decomp{$_} / $power)
!! return } ;
return ($power, %base_factors);
}
Programming Excursions in Perl and Raku 