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

  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".

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1