Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Roots Of Unity - Is It Primitive?

  1. Nov 20, 2006 #1
    All right, thanks to everybody's help, I've got the algorithm for determining the nth roots of unity.

    However, for determining which ones are primitive, I'm still having a little trouble.

    If n is odd, I can test if (n, k) are coprime. However, for even values of n, it seems that it doesn't work.

    I took a guess and tried to see if (n-k-1, n) are coprime, to determine if the nth root of unity is primitive. It seems to work for all known examples I've tried.

    Is that guess of mine incorrect? If not, what should I do for even values of n?

    Here's some Python code, demonstrating that an even value of n, 4, yields only primitive roots of unity, by testing if (n-k-1, n) are coprime. Highlighted in blue.

    Code (Text):
    import math

    def resolve_limit (value):
        if value < 0.00001 and value > - 0.00001:
            return 0
        if value > 0.49999 and value < 0.50001:
            return 0.5
        if value < -0.49999 and value > -0.50001:
            return -0.5
        return value

    def polar_to_complex (r, theta):
        a = math.cos (theta) * r
        b = math.sin (theta) * r
        a = resolve_limit (a)
        b = resolve_limit (b)
        return (a, b)

    def gcd (a, b):
        while b:
            a, b = b, a % b
        return a

    def coprime (a, b):
        if a == 0 or b == 0:
            return False
        return gcd (a, b) == 1

    def prime_nth_roots (n):
        is_even = (n%2 == 0)

        for k in range (n):

            if is_even:
                [b][color=blue]if coprime (n-k-1, n)[/color][/b]:
                    angle = k * 2 * math.pi / float(n)
                    yield polar_to_complex (-1, angle)

            else:
                if coprime (k, n):
                    angle = k * 2 * math.pi / float(n)
                    yield polar_to_complex (1, angle)

    print [root for root in prime_nth_roots (4)]
     
    Last edited: Nov 20, 2006
  2. jcsd
  3. Nov 20, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why do you think that?


    This code gives wrong answers.
     
  4. Nov 20, 2006 #3
    I think that because it wasn't outputting the correct answers, as suggested for certain situations. If you move my coprime function call test to the first dimension of the conditional statements, using the call "coprime (k, n)", and let n=4, it does not get the right answers.

    Are you positive? The code outputs:

    >>>
    [(-1.0, 0), (1.0, 0)]

    Which translates to +i and -i.

    According to Wikipedia, these are the correct primitive nth roots of unity where n = 4.

     
  5. Nov 20, 2006 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Traditionally, and how you've written your code,

    (a, b)

    corresponds to

    a + bi.
     
  6. Nov 20, 2006 #5
    Yeah, I smacked my forehead right after I made that post. No sooner than I made that statement, I made the connection that my conclusion wasn't even correct in the first place. :tongue:

    Oh geez. Hahah. So was it correct to only test coprime(n, k)?

    Furthermore, if I only need "a primitive nth root of unity", do I only need to calculate and return the first rotation, since (1, n) will always be coprime? Which reduces the algorithm to O(1) time? :biggrin:
     
  7. Nov 20, 2006 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I was hoping you'd see it just before you made your post. :wink:


    Why wouldn't it work?

    Incidentally, isn't it much faster than O(n) time? You're just doing a couple multiplies and computing one sine and one cosine.
     
    Last edited: Nov 20, 2006
  8. Nov 20, 2006 #7

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    this programmed approach seems silly to me. just think about it.
     
  9. Nov 20, 2006 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I assume computing the primitive 4-th roots was merely a test of his program, not the end goal.
     
  10. Nov 20, 2006 #9
    Hahaha, yes. I actually immediately edited it to O(1) after I made the post. I'm surprised that you managed to catch my original post. You must have been close by at the time I posted.

    It's O(1) because generally mathematical computations are expressed as a constant, even though they may themselves, take linear (or even polynomial) time.

    Just checking. That's great then! I just did not want to make a catastrophic mistake that could ressonate throughout my entire program!

    Precisely. The "Discrete Weighted Transform With An Irrational Base" (DWTIB) requires a primitive nth root of unity in the appropriate domain, where n is the chosen run time for the Algorithm W variant of the DWT.
     
    Last edited: Nov 20, 2006
  11. Nov 20, 2006 #10
    I believe I found out why I figured my algorithm to be incorrect (yet used a wrong example in my first post)...

    If n = 2, the only supposed primitive root is -1, yet my algorithm yields +1.

    Code (Text):
    import math

    def resolve_limit (value):
        if value < 0.00001 and value > - 0.00001:
            return 0
        if value > 0.49999 and value < 0.50001:
            return 0.5
        if value < -0.49999 and value > -0.50001:
            return -0.5
        return value

    def deg_to_rad (deg):
        return deg * math.pi / 180.0

    def complex_to_polar (a, b):
        r = (a**2.0 + b**2.0)**0.5
        theta = math.acos (a / r)
        return (r, theta)

    def polar_to_complex (r, theta):
        a = math.cos (theta) * r
        b = math.sin (theta) * r
        a = resolve_limit (a)
        b = resolve_limit (b)
        return (a, b)

    def gcd (a, b):
        while b:
            a, b = b, a % b
        return a

    def coprime (a, b):
        if a == 0 or b == 0:
            return False
        return gcd (a, b) == 1

    def prime_nth_roots (n):
        is_even = n%2 == 0
        for k in range (n):
            if coprime (k, n):
                angle = k * 2 * math.pi / float(n)
                yield polar_to_complex ((1, -1)[is_even], angle)

    def a_prime_nth_root (n):
        is_even = n%2 == 0
        angle = 2 * math.pi / float(n)
        return polar_to_complex ((1, -1)[is_even], angle)

    if __name__ == '__main__':
        n = 2
       
        print [root for root in prime_nth_roots (n)]
        print a_prime_nth_root (n)
     
     
  12. Nov 20, 2006 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When I ran your original algorithm on 2 (after removing the "is_even" check), it gives me -1 is the only primitive root of 1.

    When I run this new code, it says 1 is a primitive square root of 1.
     
  13. Nov 21, 2006 #12
    In my second code I used a length of negative 1 for an even value of n. While in the first code, if you removed the "is_even" check, it would have used positive 1.

    If a value of n is even, you need to either add pi to the angle, or set the length to negative 1.

    That's not for something else is it?
     
  14. Nov 21, 2006 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think you're thinking of the trick to turn a primitive n-th root into a primitive (2n)-th root. (with n odd)
     
  15. Nov 21, 2006 #14
    Oh my... so the algorithm dumbs down to something as little as...

    Code (Text):
    def a_prime_nth_root (n):
        return polar_to_complex (1, 2 * math.pi / float(n))
    Jesus christ, that's a lot simpler. Heh. Thanks for the help.
     
  16. Nov 22, 2006 #15

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    There's no way it's O(1). You're doing a division, which takes O(log(n)) absolute minimum -- and probably more like O(log(n)2).
     
  17. Nov 22, 2006 #16
    Division and multiplication of 16-32 bit numbers is often only one operation for most 32-64 bit processors. n will never be more than 2 bytes.
     
    Last edited: Nov 22, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Roots Of Unity - Is It Primitive?
  1. Roots of unity (Replies: 7)

  2. Roots of unity (Replies: 1)

Loading...