Identify a irrational or complex number

Question

I am taking the square root of a number, and I want to find if it is irrational or complex, and return True or False

test cases, where taking the square root of the number is True for irrational / complex, and False if the square root is a float or int.

[IN 1] 20
[OUT 1] True
[IN 2] 25
[OUT 2] False
[IN 3] -1
[OUT 3] True
[IN 4] -20
[OUT 4] True
[IN 5] 6.25
[OUT 5] False

How can I make a function that achieves this?

Well, irrational numbers are complex, so there's no problem here. — ForceBru, Feb 17 '17 at 16:15
If you start with a negative number, the square root is imaginary (therefore complex). Any non-integer square root of an integer is irrational. If you're taking square roots of floats, I don't know how you could figure out if the result is rational or not. — khelwood, Feb 17 '17 at 16:15
The irrationality of the result isn't actually determinable, since floating-point numbers do not represent an exact value. Within the range of values that a given float could represent, some will have rational square roots, and some will have irrational roots. — jasonharper, Feb 17 '17 at 16:17
I clarified my question so it doesn't look like the interpreter. — lol, Feb 17 '17 at 16:18
@Mitch, irrational numbers are a subset of real numbers, and the latter are a subset of complex numbers. Thus, irrational numbers are (a subset of) complex numbers. — ForceBru, Feb 17 '17 at 16:19
@ForceBru Well pedantically yes, but by that argument 1 is complex. — khelwood, Feb 17 '17 at 16:20
@ForceBru Ehh yeah I suppose if we aren't implicitly assuming non-zero imaginary part, but that is generally implied. — miradulo, Feb 17 '17 at 16:21
I just mean if you have to say whether a number is irrational or complex, always say 'complex' and you'll always be correct. So, the question's a bit weird... — ForceBru, Feb 17 '17 at 16:23
I didn't understand that at first. Do you want me to change the question to remove the irrational part? — lol, Feb 17 '17 at 16:25
@ForceBru That would be a sassy answer on the homework ;) just have a function that returns True for everything. But that implication is pretty standard to be fair - think of the topics of real analysis vs complex analysis. — miradulo, Feb 17 '17 at 16:28
@lol, nobody wants you to do this. I wanted to say that _every_ number you can think of (be it 0 or -1 or 1.2 or 1/3 or Pi or sqrt(-1) or sqrt(2) or anything) _is complex_, including any irrational number too. So, I don't see what's the problem here: just reply 'complex' for any number and that's it. You can't determine if a number is irrational using a computer as it can store only finite amount of digits after decimal point. — ForceBru, Feb 17 '17 at 16:30

MSeifert · Accepted Answer · 2017-02-17T17:55:02.040

It's easy to check if a number has a complex square root, that's the case if you have a negative number:

def has_complex_sqrt(num):
    return num < 0

However it's harder to find out if a number has an irrational square root. There's a way that works if your number is a string because fractions.Fraction can then calculate the exact represention for this number.

Then one uses the fact that the square root of a number can only be rational if each prime factor of the numerator and denumerator of the fraction representing the number has an even exponent. (There is a lot of ressources on the web backing this up)

So the steps to solve this are:

get the exact fractional representation
find the prime-factors
and then check if each of them has an even exponent.

Implementing this in code:

from fractions import Fraction

def get_fraction_from_string(num):
    return Fraction(num)

def get_prime_factors(n):
    # Taken from http://stackoverflow.com/a/22808285/5393381
    # you might implement another algorithm here!
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

from collections import Counter

def has_even_exponents(primefactorized):
    return all(num % 2 == 0 for num in Counter(primefactorized).values())

And finally putting this all into one "super-function":

def has_irrational_sqrt(astring):
    fract = get_fraction_from_string(astring)
    primefactors_numerator = get_prime_factors(fract.numerator)
    if not has_even_exponents(primefactors_numerator):
        return True
    primefactors_denominator = get_prime_factors(fract.denominator)
    if not has_even_exponents(primefactors_denominator):
        return True
    return False

and for convenience another function that checks if any of both is True:

def has_irrational_or_complex_sqrt(num):
    return has_complex_sqrt(float(num)) or has_irrational_sqrt(num)

And now the interactive test:

>>> has_irrational_or_complex_sqrt('20')
True
>>> has_irrational_or_complex_sqrt('25')
False
>>> has_irrational_or_complex_sqrt('-1')
True
>>> has_irrational_or_complex_sqrt('-20')
True
>>> has_irrational_or_complex_sqrt('6.25')
False

That produces the expected values. Hurray!

If your input is already a float this approach might not work!

>>> has_irrational_or_complex_sqrt('0.01')
False
>>> has_irrational_or_complex_sqrt(0.01)  # Oups!
True

But in your example it works because 6.25 can be represented exactly as float:

>>> has_irrational_or_complex_sqrt(6.25)
False

I'm confused as to why `0.01` doesn't work but `'0.01` does. should I just change the number to a string to avoid this problem? — lol, Feb 17 '17 at 18:00
Because `Fraction('0.01') == Fraction(1, 100)` but `Fraction(0.01) == Fraction(5764607523034235, 576460752303423488)`. That's because you can't represent `0.01` _exactly_ as `float`. And `Fraction` can't recover what you meant, it simply uses what you provide as input. So yes, if you want it to work correctly you need to use `strings`. — MSeifert, Feb 17 '17 at 18:02
I have a much simpler way of writing it, only `22` lines total. — lol, Feb 17 '17 at 23:24
@lol That's great! You can simply add it as another answer to your question :) Self-answering is fine as long as it happens as answer. However you won't get any reputation from accepting your own answer. — MSeifert, Feb 17 '17 at 23:29
I know this is an old answer, but I just wanted to point out that no prime factoring is required, it is sufficient to show that both the numerator and denominator are perfect squares, which you can do fairly quickly and simply, either by checking that `int(n**0.5)**2 == n`, or by iterating through every perfect square less than n and then checking if n is equal to the first perfect square that is not less than n. — Broseph, Mar 19 '18 at 21:48
Not quite that easy because ** 0.5 triggers floating point arithmetic and is subject to inaccuracies which could lead to wrong results. — MSeifert, Mar 19 '18 at 21:55
But the iteration should work. Could also be faster than my prime factorizaton. — MSeifert, Mar 19 '18 at 22:02

score 0 · Answer 2 · answered Feb 17 '17 at 23:48

Based off the answer from @MSeifert, but written more simply:

import collections, fractions
def get_prime_factors(n):
    #http://stackoverflow.com/a/22808285/5393381
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors  
def has_irrational_square_root(num):
    #http://stackoverflow.com/questions/42302488/identify-a-irrational-or-complex-number
    frac = fractions.Fraction(str(num))
    top_primes = get_prime_factors(frac.numerator)
    bottom_primes = get_prime_factors(frac.denominator)
    all_even_top = all(num % 2 == 0 for num in collections.Counter(top_primes).values())
    all_even_bottom = all(num % 2 == 0 for num in collections.Counter(bottom_primes).values())
    if all_even_top and all_even_bottom:
        return False
    return True

Identify a irrational or complex number

2 Answers2