Qbasicnews.com
September 19, 2019, 03:42:24 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1] 2 3 4
  Print  
Author Topic: Algorithm to determine if a number A is a power of B.  (Read 27100 times)
Moneo
Na_th_an
*****
Posts: 1971


« on: February 27, 2005, 11:13:38 PM »

Im sure we have seen algorithms to determine if a number is a power of 2.

Now, write an algorithm to determine if a number A is a power of a number B.

Example:
A=125
B=5
Is 125 a power of 5?

Both A and B must be positive whole numbers. The algorithm that I already wrote only handles a value of A up to 32k.

See what you can come up with!
*****
Logged
Mitth'raw'nuruodo
Ancient Guru
****
Posts: 515



WWW
« Reply #1 on: February 28, 2005, 01:06:48 AM »

I do programs like these at compitions. Took me not even 5 mins.

Code:

CLEAR
CLS
INPUT "Number: ", A
INPUT "Base: ", B
Value = 0
IsIt = 0
index = -1
DO
 IF Value > A THEN EXIT DO
 index = index + 1
 Value = B ^ index
 IF Value = A THEN IsIt = 1: EXIT DO
LOOP
Message$ = "No, it is not a power of" + STR$(B)
IF IsIt = 1 THEN Message$ = "Yes, it is a power of" + STR$(B)
PRINT Message$
END


There you go! Cheesy Challenge Complete!

BTW, Test your program: A = 1, B = anynumber. 1 is a power of ANY number! anynumber ^ 0 = 1.
Logged

i]"But...it was so beautifully done"[/i]
shiftLynx
Wandering Guru
***
Posts: 340



WWW
« Reply #2 on: February 28, 2005, 01:26:38 PM »

Using the laws of logs, consider:

a^y = x

Log both sides:

log(a^y) = log(x)

Using laws of logs:

ylog(a) = log(x)

Hence:

y = log(x) / log(a)

Written in code:


[syntax="QBASIC"]
cls

b# = -1
num# = -1
while (b# <= 0) and (num# <= 0)
   line input "Number: ", num$
   line input "Base: ", b$
   
   num# = val(num$)
   b# = val(b$)

   if b# <= 0 then
      print "Invalid base; must be greater than zero."
      print
   elseif num# <= 0 then
      print "Invalid number; must be greater than zero."
      print
   end if
wend

' calculate the exponent.
exponent# = log(num#) / log(b#)
print num$ + " is " + b$ + "^" + ltrim$(str$(exponent#))

end
[/syntax]


This will also work for negative indices. For example, try putting the number as '0.2' and the base as 5.

-shiftLynx
Logged

img]http://www.cdsoft.co.uk/misc/shiftlynx.png[/img]
aetherfox
Been there, done that
*****
Posts: 1071



WWW
« Reply #3 on: February 28, 2005, 02:29:12 PM »

Well the exponent due to the logs will be any number, even non integer.

See, 6 is a power of 5...just not an integer power.  I think that the original challenge was to see whether it was a whole power.
Logged

~''i|~thrFx~|i''~-  
avinash.vora - http://www.avinashv.net
Rattrapmax6
__/--\__
*****
Posts: 2577



WWW
« Reply #4 on: February 28, 2005, 02:51:43 PM »

Cheesy Not exactly sure if this is what you want, but it seems simular to the above ones so I'll go on and submit:

[syntax="qbasic"]CLS
INPUT "Input Number: ", num1
INPUT "Input its #th root to check: ", num2
tst! = (num1) ^ (1 / num2)
text$ = STR$(tst!)
cont = 0
DO
cont = cont + 1
IF cont = LEN(text$) THEN EXIT DO
IF MID$(text$, cont, 1) = "." THEN PRINT num2; " is not the #th root of"; num1: END
LOOP
PRINT num2; " is the #th root of "; num1[/syntax]

 Cheesy  Cheesy
Logged

Kevin (x.t.r.GRAPHICS)

shiftLynx
Wandering Guru
***
Posts: 340



WWW
« Reply #5 on: February 28, 2005, 03:14:35 PM »

Ah, yes, he does say they must be whole numbers.

New program:

[syntax="QBASIC"]
cls

b% = -1
num% = -1
while (b% <= 0) or (num% <= 0)
   line input "Number: ", num$
   line input "Base: ", b$
   
   num% = int(val(num$))
   b% = int(val(b$))

   if b% <= 0 then
      print "Invalid base; must be greater than zero."
      print
   elseif num% <= 0 then
      print "Invalid number; must be greater than zero."
      print
   end if
wend

' calculate the exponent.
exponent! = log(num%) / log(b%)
if exponent! <> fix(exponent!) then
   print num$ + " is not an integer power of " + b$
else
   print num$ + " is a power of " + b$ + " (exponent=" + ltrim$(str$(int(exponent!))) + ")"
end if


end
[/syntax]

Sample:

Code:

Number: 78125
Base: 5
78125 is a power of 5 (exponent=7)



-shiftLynx
Logged

img]http://www.cdsoft.co.uk/misc/shiftlynx.png[/img]
Mitth'raw'nuruodo
Ancient Guru
****
Posts: 515



WWW
« Reply #6 on: February 28, 2005, 06:34:28 PM »

negatives?
Logged

i]"But...it was so beautifully done"[/i]
shiftLynx
Wandering Guru
***
Posts: 340



WWW
« Reply #7 on: February 28, 2005, 07:11:06 PM »

Quote from: "Mitth'raw'nuruodo"
negatives?


Read:
Quote from: "Moneo"
Both A and B must be positive whole numbers.


-shiftLynx
Logged

img]http://www.cdsoft.co.uk/misc/shiftlynx.png[/img]
Mitth'raw'nuruodo
Ancient Guru
****
Posts: 515



WWW
« Reply #8 on: March 01, 2005, 10:29:12 AM »

Oh, hehe..... :shifty: ....ummm...hehe. Cheesy
Logged

i]"But...it was so beautifully done"[/i]
Moneo
Na_th_an
*****
Posts: 1971


« Reply #9 on: March 01, 2005, 11:57:25 PM »

Quote from: "Mitth'raw'nuruodo"
Code:

CLEAR
CLS
INPUT "Number: ", A
INPUT "Base: ", B
Value = 0
IsIt = 0
index = -1
DO
 IF Value > A THEN EXIT DO
 index = index + 1
 Value = B ^ index
 IF Value = A THEN IsIt = 1: EXIT DO
LOOP
Message$ = "No, it is not a power of" + STR$(B)
IF IsIt = 1 THEN Message$ = "Yes, it is a power of" + STR$(B)
PRINT Message$
END

Your solution is actually a program or a routine, not an algorithm, because it has a loop.
However, it does work, with one exception. If you enter a number greater than 1 as the A number and then a 1 for the B or base value, it goes into an endless loop.

Nice work, anyway.
*****
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #10 on: March 02, 2005, 12:24:07 AM »

Quote from: "shiftLynx"
Ah, yes, he does say they must be whole numbers.
New program:
[syntax="QBASIC"]
cls

b% = -1
num% = -1
while (b% <= 0) or (num% <= 0)
   line input "Number: ", num$
   line input "Base: ", b$
   
   num% = int(val(num$))
   b% = int(val(b$))

   if b% <= 0 then
      print "Invalid base; must be greater than zero."
      print
   elseif num% <= 0 then
      print "Invalid number; must be greater than zero."
      print
   end if
wend

' calculate the exponent.
exponent! = log(num%) / log(b%)
if exponent! <> fix(exponent!) then
   print num$ + " is not an integer power of " + b$
else
   print num$ + " is a power of " + b$ + " (exponent=" + ltrim$(str$(int(exponent!))) + ")"
end if
end
[/syntax]

Sample:
Code:

Number: 78125
Base: 5
78125 is a power of 5 (exponent=7)

-shiftLynx

Yes, the laws of logs make for a good solution.
However, the output of your entry does not look like the sample above. It does not say if in fact it is a power of the base number. It just displays the exponent, which could have decimals when it is NOT a power.

Also, you input the values into strings and convert them to integers. If an input has a non-numeric character, the VAL will just ignore it and proceed with whatever is left. Not very clean code.

If the A value is greater that 1 and the B value is 1, you get a error of "division by zero".

All in all, your solution needs more work.
*****
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #11 on: March 02, 2005, 12:28:08 AM »

Quote from: "Rattrapmax6"
Cheesy Not exactly sure if this is what you want, but it seems simular to the above ones so I'll go on and submit:

Sorry, its late, give me a chance to try yours tomorrow.
*****
Logged
Mitth'raw'nuruodo
Ancient Guru
****
Posts: 515



WWW
« Reply #12 on: March 02, 2005, 01:11:03 AM »

And mine?
Logged

i]"But...it was so beautifully done"[/i]
shiftLynx
Wandering Guru
***
Posts: 340



WWW
« Reply #13 on: March 02, 2005, 01:22:01 PM »

Quote from: "Moneo"

Yes, the laws of logs make for a good solution.
However, the output of your entry does not look like the sample above. It does not say if in fact it is a power of the base number. It just displays the exponent, which could have decimals when it is NOT a power.

Also, you input the values into strings and convert them to integers. If an input has a non-numeric character, the VAL will just ignore it and proceed with whatever is left. Not very clean code.

If the A value is greater that 1 and the B value is 1, you get a error of "division by zero".

All in all, your solution needs more work.
*****


1) Did you actually run the program? It does tell you whether the number is a power of the base number. If it isn't it tells you that it isn't a power. If it does, it tells you what the power is.

2) Algorithms can contain loops.

3) Division-by-zero, fine that is an unforeseen consequence. But very simple to fix.

4) If you expected somebody to check that the input was actually a number and not that some incompetent fool input characters as a number, why didn't you say that? It's clean code because it's not unnecessarily cluttered.

5) All in all, I think your judging is flawed and this "challenge" is a joke. It is trivial to determine whether a number is a power of a given base, as shown by my program which implements extremely simple math.

Why didn't you make the challenge: "Write an algorithm to find out which number must be added to A to make B". It would be equally trivial.

These challenges are awful.


By the way, your original challenge stated to write an algorithm, so:

1) Given A^x = B where A and B are known, positive integers (where A > 1), use x = ln(B) / ln(A) to determine a value of x.
2) If x is an integer value then B is an integer power of A.

That actually meets your original challenge requirements.

-shiftLynx

[edit: typo]
Logged

img]http://www.cdsoft.co.uk/misc/shiftlynx.png[/img]
Mitth'raw'nuruodo
Ancient Guru
****
Posts: 515



WWW
« Reply #14 on: March 02, 2005, 07:22:57 PM »

Oh, ya thanks...Unnecessarially Cluttered, my FOOT! Tongue

There's a way to check for an intger in 1 line, Z!re knows it, I forgot it, Z!re left, its on Pete's somewhere.

If you don't like this challege then shut up, and go on your way! :evil:
Logged

i]"But...it was so beautifully done"[/i]
Pages: [1] 2 3 4
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!