RogerBW's Blog

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