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

'Pseudocubality' - fast tests for large possible-cubes

  1. Aug 24, 2007 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    'Pseudocubality' -- fast tests for large possible-cubes

    I'm looking for a way to quickly show that a huge number is not a cube. The numbers are of the form a^b + c^d where a and c are less than a million and b and d are under a hundred (give or take on both). a and c are also known to be odd, and the exponents are at least 3.

    At the moment I'm checking a+c mod 8 (it must be 0) and the sum of the powers, calculated with fast modular exponentiation, mod 9, 13, and 19. (I'm also checking mod 7, but this doesn't seem to help -- any ideas on why that is the case?)

    What I want are more tests, since far too many non-cubes slip through these tests. Since most of the inputs will be handled by one of these, the test doesn't have to be blazingly fast -- although faster is better, to be sure.

    Is there a cubic reciprocity test that can practically handle numbers of this size? Can it be done (like modular exponentiation) without expanding the numbers?
     
  2. jcsd
  3. Aug 24, 2007 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

  4. Aug 24, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Is it not enough to simply check modulo more primes of the form 3k+1?

    I suspect you could do the computation faster if you didn't check 7, 9, 13, and 19 separately... but instead computed it once modulo 7*9*13*19, and uesd that to compute the residue modulo your other moduli. (Or even just stored an array indicating whether an element modulo 7*9*13*19 is a cube)
     
    Last edited: Aug 24, 2007
  5. Aug 24, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    To save on modular exponentiation, observe that

    (a^b) mod 13 = a^(b mod 12) mod 13

    Even better, you could avoid doing any multiplies at all -- just store a 13 by 12 lookup table of the value of a^b. (Note that, since you have a fixed modulus, there are clever ways to compute the remainder without doing any division)

    Even better -- why use a clever way to compute the remainder when you can just use a lookup table? :biggrin: You could store an array of the value of x mod 13 for every x under 2^20, and x mod 12 for x under 2^10. It's unclear to me which would win.
     
    Last edited: Aug 24, 2007
  6. Aug 25, 2007 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Not really; the higher the primes get the less useful they are, and the more modulus operations are needed.

    I'm already doing this, actually. It seemed like an obvious speedup, so I took it. The array hasn't proved useful yet, since the later tests don't come up much.
     
  7. Aug 25, 2007 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I've read that and a number of other sources on cubic reciprocity (although I'll blush to admit I didn't look it up in my Ireland & Rosen), but I'm actually having trouble figuring out how to implement that test quickly for large numbers.

    I'm still working on it.
     
    Last edited: Aug 25, 2007
  8. Aug 25, 2007 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This doesn't sound right -- a random number modulo a prime p = 3k+1 has a precisely one in three chance of being a cube, I would expect that each additional prime you tried kills off another 66% of the false positives. If either exponent you're using is relatively prime to 3k and the corresponding base is uniformly distributed mod p, then your final number should be uniformly distributed mod p!

    So, I'm surprised to hear that larger primes are less useful. Nor can I explain why 7 isn't helping. :frown: Admittedly, I'm more inclined to suspect a bug in the program than number theoretic reasons... I'm going to have to code this up later, so that I can see it for myself!
     
  9. Aug 25, 2007 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, but the larger the primes the more tests are needed to check the residue classes.

    What I'd really like is to find some conditions that knock out 'most' in some sense of the false positives, then a test that will remove 'almost all' of the false positives. The whole program is designed to search a very large space for cubes -- although this is of itself just a multi-day preprocessing step for a larger search for powers.
     
  10. Aug 25, 2007 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm not sure what you mean -- as long as you stick to small primes, once you have the residue modulo the prime, it's just a single table lookup to tell if you have a cube or not. It would take a small miracle to pass the first 100 tests, so it doesn't really matter if you take a millisecond to test the next few thousand primes. (Or whatever method you intend to use to decide if it really is a cube)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 'Pseudocubality' - fast tests for large possible-cubes
  1. Square Cubes (Replies: 7)

  2. Cube fitting (Replies: 0)

  3. Rotatations in a cube? (Replies: 16)

  4. Is it possible (Replies: 11)

  5. Cube Matrices (Replies: 3)

Loading...