Qbasicnews.com
February 17, 2020, 03:05:00 PM
 Pages: [1] 2 3 4
 Author Topic: Algorithm to determine if a number A is a power of B.  (Read 27709 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

 « 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! 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

 « 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

 « 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|¡~æthérFòx~¡|i¹'°¨°'¹~·-
avinash.vora - http://www.avinashv.net
Rattrapmax6
__/--\__

Posts: 2577

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

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]

 Logged

Kevin (x.t.r.GRAPHICS)

shiftLynx
Wandering Guru

Posts: 340

 « 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

 « 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

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

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

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

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

Oh, hehe..... :shifty: ....ummm...hehe.
 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"
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

 « 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

 « 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

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

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

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