I’ve been doing the Perl Weekly
Challenges. The
latest
involved dividing without dividing, and making a test of factors.
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.
Yay, it's not another BFS with FIFO buffer!
For the sake of not taking the mickey, I assumed that <<
was to be
regarded as multiplication for this purpose. Also that the first "and"
should read "or".
I did decide to build this off an existing test framework rather than
writing my own.
use Test::More tests => 3;
is(divide(5,2),2,'all positive');
is(divide(-5,2),-3,'partly negative');
is(divide(-5,-2),2,'all negative');
sub divide {
my ($dividend,$divisor)=@_;
if ($divisor==0) {
die "Division by zero\n";
}
The hard bit here is the use of negative numbers. So let's ignore them
and turn everything positive!
my $sign=1;
if ($dividend < 0) {
$sign=-$sign;
$dividend=-$dividend;
}
if ($divisor < 0) {
$sign=-$sign;
$divisor=-$divisor;
}
Now we can go for iterated subtraction.
my $quotient=0;
while ($dividend>$divisor) {
$dividend-=$divisor;
$quotient++;
}
If we do want a negative result, make it so; and implement floor
without using that function either (if there's a remainder, round the
quotient towards the negative).
if ($sign<0) {
$quotient=-$quotient;
if ($dividend>0) {
$quotient--;
}
}
return $quotient;
}
That's fine for small numbers, but what if the dividend is much larger
than the divisor? We're not allowed to use multiplication, but we can
do something like long division in base 2. After the inbound sign
fiddling:
my $q=1;
my @t=([$divisor,$q]);
while ($divisor < $dividend) {
$divisor+=$divisor;
$q+=$q;
unshift @t,[$divisor,$q];
}
my $quotient=0;
while (my $dq=shift @t) {
while ($dividend>$dq->[0]) {
$dividend-=$dq->[0];
$quotient+=$dq->[1];
}
}
And then on with the outbound sign-fiddling as before. (Technically
that inner while
could now be an if
, because in base 2 it'll only
ever be called once per outer loop.)
For Raku, though, I didn't feel like the load of extra work that Raku
makes out of putting lists in lists, so I stuck with the original
algorithm. It has a test framework built in:
use Test;
plan 3;
and the rest is basically as before.
You are given an integer $N
.
Write a script to check if the given number can be expressed as m^n
where m
and n
are positive integers. Otherwise print 0.
Example 1:
For given $N
= 9, it should print 3² or 3^2
.
Example 2:
For given $N
= 45, it should print 0.
There are various approaches one could take to this, but there's a
third test case worth bearing in mind: 36 decomposes to 6^2, but is
not a product of a single prime number as in case 1.
With that in mind, I ended up conducting a prime factorisation, then
testing the output.
sub singlefactor {
my $in=shift;
my $factor=2;
my %pf;
while (1) {
my $p=0;
while ($in % $factor == 0) {
$in/=$factor;
$p++;
}
if ($p>0) {
$pf{$factor}=$p;
}
if ($in < 2) {
last;
}
if ($factor==2) {
$factor++;
} else {
$factor+=2;
}
}
At this point, %p
consists of a series of base → exponent pairs. If
the (non-zero) exponents all have the same value, then we have a valid
decomposition, as for example (2 → 2, 3 → 2)
from 36. (product
is
from the wonderful List::Util
package, which is also where I get
min
and max
.)
if (max(values %pf) == min(values %pf)) {
return product(keys %pf) . '^' . min(values %pf);
} else {
return '0';
}
}
In Raku we can optimise slightly by using the is-prime test when
generating potential divisors.
if ($factor==2) {
$factor++;
} else {
repeat {
$factor+=2;
} until is-prime($factor);
}
But although min
and max
are now built in, there's apparently no
product
function that takes a list (though there is sum
), so we
have to do that iteratively.
my $f=1;
for keys %pf {
$f*=$_;
}
return $f ~ '^' ~ min(values %pf);