# 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); `````` 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 ? 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 10 per page 20 per page 50 per page 100 per page Archive Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics 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 science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance 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