# RogerBW's Blog

Perl Weekly Challenge 66: dividing and factorising 29 June 2020

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->) {
\$dividend-=\$dq->;
\$quotient+=\$dq->;
}
}
``````

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);
``````

1. Posted by Dave D at 11:43am on 29 June 2020

Doesn't seem to work for 12^2 since it factors it down to 2^4 * 3^2 and then concludes the powers aren't all the same. I guess it would need to find the GCD for the powers ? Also, does it handle 1 correctly ? (Is there a correct output for 1 ?)

Don't all positive integers N qualify, using m=N, n=1 ?

2. Posted by RogerBW at 12:07pm on 29 June 2020

The second example invalidates your case of `\$N^1`. (I usually have to reverse-engineer parts of the problem specification from the examples.)

But yes, fair point where the exponents aren't equal. gcd on the exponents ought to do it.

If only there were any sort of practical use case for these things rather than just "do this because we said so".