Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
check whether a number is a power of 3 [newbie]

Subject: check whether a number is a power of 3 [newbie]

From: Candide Voltaire

Date: 13 Aug, 2011 09:43:24

Message: 1 of 10

I need to check whether a number is a power of 3.
I tried the following:
isinteger(log(n)/log(3));

this doesn't work however (e.g. with n=27), probably because of the
floating point representation used internally in matlab.
Can anyone here suggest how to check whether n is a power of 3?

regards,
Candide

Subject: check whether a number is a power of 3 [newbie]

From: Bruno Luong

Date: 13 Aug, 2011 09:51:16

Message: 2 of 10

Candide Voltaire <candideguevara@gmail.com> wrote in message <b27a3300-683d-4b3a-a958-38fe65a31d5e@h7g2000yqm.googlegroups.com>...
> I need to check whether a number is a power of 3.
> I tried the following:
> isinteger(log(n)/log(3));

3^round(log(n)/log(3))==n

Bruno

Subject: check whether a number is a power of 3 [newbie]

From: Jan Simon

Date: 13 Aug, 2011 20:23:10

Message: 3 of 10

Dear Candide Voltaire,

> isinteger(log(n)/log(3));

This does not work for any other value also. ISINTEGER checks, if a variable is of type (U)INT8/16/32/64, but it does not care about the value.

Due to the limited precision you can check the values from 3^0 to 3^33 only. Therefore the most efficient method is:
  pool = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, ...
              1594323, 4782969, 14348907, 43046721, 129140163, 387420489, ...
               1162261467, 3486784401, 10460353203, 31381059609, ...
                94143178827, 282429536481, 847288609443, ...
                2541865828329, 7625597484987, 22876792454961, ...
                68630377364883, 205891132094649, 617673396283947, ...
                1853020188851841, 5559060566555523];
  isPower3 = any(n == pool);

Kind regards, Jan

Subject: check whether a number is a power of 3 [newbie]

From: Matt J

Date: 13 Aug, 2011 20:29:28

Message: 4 of 10

"Jan Simon" wrote in message <j26mfe$7cb$1@newscl01ah.mathworks.com>...
>
> Due to the limited precision you can check the values from 3^0 to 3^33 only. Therefore the most efficient method is:
> pool = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, ...
> 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, ...
> 1162261467, 3486784401, 10460353203, 31381059609, ...
> 94143178827, 282429536481, 847288609443, ...
> 2541865828329, 7625597484987, 22876792454961, ...
> 68630377364883, 205891132094649, 617673396283947, ...
> 1853020188851841, 5559060566555523];


If you're precomputing "pool", is there a reason not to do so via

 pool=3.^(0:33)


?

Subject: check whether a number is a power of 3 [newbie]

From: Jan Simon

Date: 13 Aug, 2011 21:06:13

Message: 5 of 10

Dear Matt J,

> If you're precomputing "pool", is there a reason not to do so via
> pool=3.^(0:33)

The power operator is expensive and two arrays of 34*8 Bytes are needed.
But most of all I wanted to point out, that the problem is limited to a very tiny set of values.

Kind regards, Jan

Subject: check whether a number is a power of 3 [newbie]

From: Jomar Bueyes

Date: 13 Aug, 2011 22:32:12

Message: 6 of 10

On Aug 13, 5:43 am, Candide Voltaire <candideguev...@gmail.com> wrote:
> I need to check whether a number is a power of 3.
> I tried the following:
> isinteger(log(n)/log(3));
>
> this doesn't work however (e.g. with n=27), probably because of the
> floating point representation used internally in matlab.
> Can anyone here suggest how to check whether n is a power of 3?
>
> regards,
> Candide

Hi Candide,

A combination of the 'factor' and 'all' functions might help:

all(factor(X) == 3)

returns true (i.e. 1) if all the factors of X are equal to 3 and
therefore X is a power of 3

HTH

Jomar

Subject: check whether a number is a power of 3 [newbie]

From: Jan Simon

Date: 13 Aug, 2011 23:16:11

Message: 7 of 10

Dear Jomar,

> all(factor(X) == 3)

Good idea! Based on this I've inlined the check in FACTOR:

function R = isPowerOf3(n)
while n >= 1 && n == round(n)
  if n == 1
    R = true;
  end
  n = n / 3;
end
R = false;

Kind regards, Jan

Subject: check whether a number is a power of 3 [newbie]

From: Bruno Luong

Date: 14 Aug, 2011 18:12:10

Message: 8 of 10

"Jan Simon" wrote in message <j270jr$5jf$1@newscl01ah.mathworks.com>...

>
> function R = isPowerOf3(n)
> while n >= 1 && n == round(n)
> if n == 1
> R = true;
> end
> n = n / 3;
> end
> R = false;
>

I believe the statement "R = false;" should be on top.

I modify your code so as it requires only one comparison by loop (instead of three). The price to pay is the need of one temporary variable.

function R = isPowerOf3_bis(n)
while n == round(n)
    m = n;
    n = n / 3;
end
R = m == 1;

% Bruno

Subject: check whether a number is a power of 3 [newbie]

From: Candide Voltaire

Date: 14 Aug, 2011 18:43:53

Message: 9 of 10

On Aug 14, 8:12 pm, "Bruno Luong" <b.lu...@fogale.findmycountry>
wrote:
> "Jan Simon" wrote in message <j270jr$5j...@newscl01ah.mathworks.com>...
>
> > function R = isPowerOf3(n)
> > while n >= 1 && n == round(n)
> >   if n == 1
> >     R = true;
> >   end
> >   n = n / 3;
> > end
> > R = false;
>
> I believe the statement "R = false;" should be on top.
>
> I modify your code so as it requires only one comparison by loop (instead of three). The price to pay is the need of one temporary variable.
>
> function R = isPowerOf3_bis(n)
> while n == round(n)
>     m = n;
>     n = n / 3;
> end
> R = m == 1;
>
> % Bruno

thanks to you and all the others for all your solutions

regards,
candide

Subject: check whether a number is a power of 3 [newbie]

From: Jan Simon

Date: 15 Aug, 2011 01:05:10

Message: 10 of 10

Dear Bruno,

> > function R = isPowerOf3(n)
> > while n >= 1 && n == round(n)
> > if n == 1
> > R = true;
> > end
> > n = n / 3;
> > end
> > R = false;
> >
>
> I believe the statement "R = false;" should be on top.

No, it is ok on the bottom, because it avoids overwriting R in case of a match.
 
> function R = isPowerOf3_bis(n)
> while n == round(n)
> m = n;
> n = n / 3;
> end
> R = m == 1;

Your code looks nicer, but it runs 14% longer on my computer. It crashs for non-integer values due to the undefined m. Next version:

  function R = isPowerOf3(n)
  while n > 1 && n == round(n)
    n = n / 3;
  end
  R = (n==1);

This is faster than my wooden hammer approach of the hard coded possible powers of 3, which can be represented exactly by DOUBLEs.

Kind regards, Jan

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us