Thread: Some help developing a super-fast integer test?

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Question Some help developing a super-fast integer test?

    Here's the deal: I'm a little burned out of late and so I'm hoping some of you here can help out in developing a really fast test using only (or mostly) bitwise operators. It's not that I can't figure it out or anything...just a bit too bleary to channel those creative forces to pull it all together.

    The mathematical description is actually quite simple (does vbulletin support math markup?). In pseudocode:

    Code:
    constraint(n){ 2^((n-1)/2) % n == (n-1) }
    
    special(n){ constraint(n) && constraint((n-1)/2) }
    Alternately (and probably more concisely), "constraint" could be defined as:

    Code:
    constraint(n){ sqrt(2^(n-1)) == -1 (mod n) }
    ...where the above is obviously a modular square root.

    Oh, and the implementation should ideally be bit-width-neutral (ie: not tailored to 32-bits or what have you).

    Any and all help would be greatly appreciated!
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Wait, don't most compilers automatically write to bitwise operations whenever possible? Have you tried compiling with -O3?

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by MutantJohn View Post
    Wait, don't most compilers automatically write to bitwise operations whenever possible? Have you tried compiling with -O3?
    In this case, it's not so simple. The problem here basically boils down to working out an efficient modular exponentiation scheme (that is, 'n' can be quite large).
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Well, I'm like 100% certain you know that 2^n is easily written in code as 1 << n.

    And then n/2 is easily n >> 1.

    n - 1 is a pretty quick operation as it's simply just removing setting the first in the binary series equal to 0. What I mean is, 1111 - 0001 is 1110 or 8+4+2+1 - 1 = 8+4+2 = 14. Oh, the only problem would be when you have 1110 - 0001. Ooh, that'd be lame. What is that, like 14-1 = 13 which is 8+5 = 8+4+1 so you get 1101. Idk, can computers follow the rules of binary addition and subtraction quickly?

    But for the modulo part, that's trickier. I'd imagine that division is still pretty quick but is this where your code is slow?

    Like, n mod m is supposed to just give the remainder. So you have n = x*m + y where x is a natural number. To get y, you want the x such that n is in-between x*m and (x+1)*m. Then y is simply n - x*m.

    Idk if any of this is helpful but can I just ask, why is the current code you have not fast enough? This seems like such a quick equation anyway.

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by MutantJohn View Post
    Well, I'm like 100% certain you know that 2^n is easily written in code as 1 << n.
    Right, but now imagine that n is say 347289636918. It's not really feasible to do 1 << (n >> 1) on that sort of magnitude, even if arbitrary-precision integers are available. The approach I'm using now is basically just exponentiation-by-squaring, which works okay for normal machine word sizes, but doesn't account for multiplicative overflow (essentially halving the effective machine word size) and doesn't scale too well to arbitrary-precision integers. Hence the need for a high-performance algorithm...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MutantJohn
    I'm like 100% certain you know that 2^n is easily written in code as 1 << n.
    True, but there's a caveat: n must be within a rather small range if you're working with a built-in integer type. Hence, performing modular exponentiation the straightforward way with this only works if n is sufficiently small. If you're working with an arbitrary precision math library, then it would work to compute modular exponentiation with a large n (within the limits of the library and hardware), but it would be suboptimal (thus a bignum library might provide separate functionality for computing modular exponentiation).

    Quote Originally Posted by MutantJohn
    And then n/2 is easily n >> 1.
    This optimisation is the kind that any optimising compiler will perform.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by laserlight View Post
    This optimisation is the kind that any optimising compiler will perform.
    hodorcc doesn't do it

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Hodor View Post
    hodorcc doesn't do it
    Actually wouldn't some optimizations be unavoidable in that the underlying instruction must be the same, even if you wrote n/2 or n >> 1? The number would never the less receive a new value the same way. (Another way to look at it is to say that there is no optimization)

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I believe a loop is in order. All models for efficient modular exponentiation I know about, including Montgomery Multiplications, involve a loop of some kind. It's efficient memory-wise and fast to compute. Wikipedia has an entry on a seemingly fast method under the Modular Exponentiation page.

    Is this for some work on cryptography you are doing? If so, You should check the entry to Montgomery Multiplication (MM) under the See Also section. Use this for modules 512 bit or larger. But not for smaller modules! It's considerably less efficient than the right-to-left binary method above. There is somewhere on the internet a paper on this method that uses a variant called Almost Montgomery Multiplication (AMM). It's more efficient than MM. I'm having trouble using google at the moment. Something to do with my ISP router. But you shouldn't have much difficulty finding it.
    Last edited by Mario F.; 11-21-2013 at 09:24 AM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Mario F. View Post
    Is this for some work on cryptography you are doing?
    No, it's a new mathematical conjecture of mine. Basically, the conjecture is that any number that passes the "special" test is definitely prime (some primes and all composites fail the test). No counterexamples found thus far (none below 2^64 at least).
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  11. #11
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Quote Originally Posted by Sebastiani View Post
    No, it's a new mathematical conjecture of mine. Basically, the conjecture is that any number that passes the "special" test is definitely prime (some primes and all composites fail the test). No counterexamples found thus far (none below 2^64 at least).
    So your new conjecture is a Mersenne primality test?

  12. #12
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Yarin View Post
    So your new conjecture is a Mersenne primality test?
    No, a Mersenne prime is always in the form 2^n-1 whereas the values that pass this test can be in many other forms.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Super fast tile rendering/scrolling in D3D
    By VirtualAce in forum Game Programming
    Replies: 7
    Last Post: 09-21-2006, 05:53 AM
  2. super fast question
    By kimimaro in forum C Programming
    Replies: 6
    Last Post: 03-15-2005, 09:47 AM
  3. Too fast to test!
    By Lurker in forum C++ Programming
    Replies: 12
    Last Post: 03-05-2003, 02:15 PM
  4. Super fast bilinear interpolation
    By VirtualAce in forum Game Programming
    Replies: 2
    Last Post: 06-18-2002, 09:35 PM