## Powers Of 3

### August 27, 2019

We extend the question to consider any modulus *m*, not just 3, and provide a recursive solution:

(define (power-of? m n) (if (zero? (modulo n m)) (power-of? m (/ n m)) (= n 1))) > (power-of? 3 27) #t > (power-of? 3 36) #f

I could never be a teacher of beginning programmers. The discussion thread (I won’t link it, to preserve anonymity) indicated that the beginning programmer understood neither the mathematics of the problem nor the concept of looping in a programming language. You can run the program at https://ideone.com/hpSaFA.

Advertisements

Cool drill, though not original. Actually, I’ve found a previously coded solution to it in my archive. Here is a new approach, using Julia 1.1:

function is_power_of_3_new(x::Int64)

if x < 0

return false

elseif (x == 0) || (x == 1)

return true

else

while x > 1

x /= 3

if x == 1; return true; end

end

end

end

Some testing:

Cheers!

@Zack – your code is very difficult to read & understand as the indentation has been lost – you really should try using the code formatting features described here: https://en.support.wordpress.com/wordpress-editor/blocks/syntax-highlighter-code-block/2/ – just leave out the “lang=..” bit for Julia or use “text” or find something else (“css”?) that looks OK.

Anyway, repeatedly dividing by three is slow for very large powers. Using Elric’s answer from https://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-a-power-of-3, we can do this: find the largest power of 3 greater or equal to input, then check remainder is 0. Of course, this will generally be slower for most numbers that aren’t powers of 3:

Doing that final % operation is pointless – we can just look for the closest power of 3 – need to be a little careful because of rounding problems with the logs:

The given solution neatly exposes the power of Scheme: it is written recursively, which makes it easy to reason about. But because it’s tail recursion, Scheme will execute it iteratively.

While I’m at it, the next application for tail recursion beyond looping is state machines. A state machine in a typical

programming language is a big while-loop with a mutable state variable and a big case statement branching on that variable. In Scheme, it’s just a bunch of procedure definitions, one per state. Each one transitions to the appropriate next state by tail-calling its successor, possibly passing some useful arguments. Alternatively, the definitions can be wrapped in a let-block to maintain any needed shared state. Proper tail calls guarantee that this is more efficient than the while loop, being just a bunch of register-to-register moves and gotos after the Scheme compiler is done with it.

@John: David Turner’s advice here is possibly relevant: https://www.cs.kent.ac.uk/people/staff/dat/miranda/manual/30.html

Some interesting solutions here: https://programmingpraxis.com/2016/03/01/powers-of-3/

Here’s a modification of one of them in Haskell:

@matthew. Thank you for the tip. I’ll check it out next time. Also, the algo your implemented is definitely better and it the same I used in my original solution, the previous time this exercise was mentioned. This time, however, I wanted to try out something new as a creativity exercise. Cheers!